 # Understanding Good Subarrays solution

link to problem:Problem - C - Codeforces
link to solution: https://usaco.guide/problems/cf-good-subarrays/solution

I am having trouble understanding the logic behind incrementing the map elements

	map<int, ll> sumDist;
for(int i=0; i<=n; i++){
sumDist[dp[i]-i]++;



Also, how does summing f (f-1)/2 give the final answer?

	for(pi p: sumDist){
ll f=p.second;
goodArrays+=f*(f-1)/2;
}



We want to compute the number of pairs (l,r) such that dp[l]-l = dp[r]-r.

sumDist maps a particular dp[i]-i to the number of indices that achieve that value. This is essentially a “frequency map” of all values dp[i]-i.

If f is the count that is associated with dp[i]-i, then f distinct indices achieve the said value. Any two of those f indices could work as l and r, since by definition of the map dp[l]-l = dp[r]-r = dp[i]-i.

Our task reduces to iterating through all counts f and choose two of them in \binom{f}{2} ways. Essentially, there are f choices for one element, then f-1 choices for the other element, and we must divide by 2 since (l,r) and (r,l) make no difference. That’s why \binom{f}{2} = \frac{f(f-1)}{2}.

why the loop is starting from 0 ?