CF Good Subarrays

Problems and Contests
#1

Hello! I do not understand the math that was used to solve this problem. In the official editorial`, I understand everything until the last 2 sentences, which are " Thus, we have to group all prefix by value pi−i for i from 0 to n. And if the have x prefix with same value of pi−i then we have to add x(x−1)/2 to the answer."

Would anyone be able to explain this concept to me? Thanks!

#2

We need to add one for each pair of numbers with the same p_i - i. In a group of x numbers, there is (x choose 2) or x(x-1)/2 ways to choose a pair. This can be seen by choosing one number, then choosing a different number, then dividing by two since order doesn’t matter.

1 Like