CHRISCANDY - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Tester: yash_daga
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

N friends sit in a line. In the i-th seat sits friend A_i.
For each i \lt j, the person in the i-th seat will give one candy to the friend in the j-th seat if A_i \gt A_j.

How many people don’t receive any candies at all?

EXPLANATION:

Let’s look at this from the perspective of the receiver.
The person in the j-th seat receives one candy from every i \lt j such that A_i \gt A_j.

That is, if A_j is larger than all the A_i before it, they won’t receive any candies.
In other words, each A_j that is a prefix maximum won’t receive a candy.

To compute this quickly, keep a running maximum \text{mx}, initialized to 0.
Let \text{ct} denote the number of prefix maximums, initially 0.
Then, for each i from 1 to N:

  • Set \text{mx} = \max(\text{mx}, A_i).
  • If \text{mx} = A_i, add 1 to \text{ct}.

The final answer is just N - \text{ct}.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    mx = 0
    ans = n
    for x in a:
        mx = max(mx, x)
        ans -= mx == x
    print(ans)