Overview

This is a problem of counting the number of intervals (groups) where students with passing scores are lined up consecutively.

Analysis

Rephrasing the Problem

This problem asks us to count how many “intervals where elements satisfying a condition are consecutive” exist in a sequence.

Understanding with a Concrete Example

For example, consider the case where \(N=7\), \(K=60\), and the scores are [80, 70, 50, 90, 85, 40, 75].

• Student 1: 80 points ≥ 60 → Pass ✓
• Student 2: 70 points ≥ 60 → Pass ✓
• Student 3: 50 points < 60 → Fail
• Student 4: 90 points ≥ 60 → Pass ✓
• Student 5: 85 points ≥ 60 → Pass ✓
• Student 6: 40 points < 60 → Fail
• Student 7: 75 points ≥ 60 → Pass ✓

Representing passing students as ○ and failing students as ×: ○○×○○×○

The groups of consecutive passing students are: 1. Students 1, 2 (first group) 2. Students 4, 5 (second group) 3. Student 7 (third group)

Therefore, 3 award ceremonies are needed.

Key Insight

A new group starts only when “the previous student failed (or was outside a group) and the current student passes”. We just need to count these “group starting points”.

Algorithm

1. Initialize variable count (number of groups) to 0
2. Initialize variable in_group (whether we are currently inside a group) to False
3. Look at each student in order:
   • If passing (\(A_i \geq K\)):
     • If not yet in a group (in_group = False), a new group starts, so increment count by 1
     • Set in_group = True
   • If failing (\(A_i < K\)):
     • Set in_group = False (the group is broken)
4. The final count is the answer

This method is efficient because it only requires one pass through the array.

Complexity

• Time complexity: \(O(N)\) (only one pass through the array)
• Space complexity: \(O(N)\) (for storing the input array. Additional variables are \(O(1)\))

Implementation Notes

1. Using a flag variable: By using a boolean variable in_group, we can track “whether we are currently inside an interval of consecutive passing students”.

2. Detecting group starts: By incrementing the count only when not in_group and A[i] >= K, we can accurately count only the starting points of groups.

3. Alternative approach: After converting “pass” to 1 and “fail” to 0, you can count the number of times the transition “0 → 1” occurs between adjacent elements. This is essentially the same algorithm.

   Source Code

N, K = map(int, input().split())
A = list(map(int, input().split()))

count = 0
in_group = False

for i in range(N):
    if A[i] >= K:
        if not in_group:
            count += 1
            in_group = True
    else:
        in_group = False

print(count)

---

This editorial was generated by claude4.5opus.