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:
You’re given a permutation P of \{1, 2, \ldots, N\}.
For each index i, let L_i denote the number of elements smaller than P_i and to its left, and R_i denote the number of elements larger than P_i to its right.
Count the number of indices i such that L_i = R_i.
EXPLANATION:
The fact that the constraint on N is quite small (N \le 100) allows us to just not have to think much and simply brute force the answer.
That is, we are able to directly compute the values L_i and R_i for each index i in linear time, after which we can simply check if L_i = R_i or not.
This gives a solution in \mathcal{O}(N^2).
However, there exists a faster (and nicer) solution as well!
Consider the element P_i at index i.
Suppose we’ve already computed L_i for it.
Let’s try to figure out R_i.
- Since P is a permutation, there are P_i-1 elements smaller than P_i in total, those being 1, 2, \ldots, P_i-1.
- There are L_i elements smaller than P_i to its left.
This means the remaining (P_i-1-L_i) smaller elements are to the right of index i. - There are N-i elements to the right of index i.
(P_i-1-L_i) of them are smaller than P_i, so the rest must be larger than it.
The count of elements to the right of i that are larger than P_i is exactly R_i by definition. - Thus, we obtain R_i = N-i - (P_i-1-L_i).
So, R_i can be written in terms of L_i.
We want L_i = R_i, so equating them we see that:
Which reduces to
So we simply need to count the number of indices i for which P_i+i = N+1, which is easily done in linear time!
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
p = [0] + list(map(int, input().split()))
ans = 0
for i in range(1, n+1):
if i+p[i] == n+1: ans += 1
print(ans)