PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
N people sit in a row in the movie theater.
The i-th person from the left is P_i.
They will leave in decreasing order of label.
A person can leave from either the left or the right. They will choose whichever one disturbs the least number of people; where a person is considered disturbed if they’re still sitting when someone crosses them.
Find the total number of people who will be disturbed.
EXPLANATION:
This is a simple implementation task: it’s enough to do exactly what the statement asks for.
Let’s consider people from N down to 1, since that’s the order they exit in.
Suppose we’re currently looking at person x, and let pos_x be the position of person x.
We now need to count the number of people remaining both to the left and to the right of person x.
Recall that at this point, all people \gt x have left already.
So,
- The number of people remaining to the left, is given by the count of i such that i \lt pos_x and P_i \lt x.
Let this count be L. - The number of people remaining to the right, is given by the count of i such that i \gt pos_x and P_i \lt x.
Let this count be R. - Person x will then disturb either L or R people, depending on which direction is chosen.
We’re aiming to minimize the total disturbance, so clearly we choose whichever is smaller - that is \min(L,R).
Perform the above computation for each person, and add up all their answers to get the final answer.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
ans = 0
for x in reversed(range(1, n+1)):
pos = 0
while p[pos] != x: pos += 1
left, right = 0, 0
for i in range(pos):
if p[i] > 0: left += 1
for i in range(pos+1, n):
if p[i] > 0: right += 1
ans += min(left, right)
p[pos] = 0
print(ans)