Proving the solution for Atcoder arc 193 problem B

[porotun]

Hi I was solving Atcoder arc 193 problem B.

In this editorial, the authors claim that the reason why they subtract out exactly 2 from the sums of three dynamic programming iterations is because only this case: “1, 1, 1, 1…1” will be counted in all 3 DPs.

Specifically, the DP transitions will should like this, with the orange denoting the new set, S2 at dp[i+1][S2] when transitioning from dp[i][S1].

However, when I saw this chart, I realized that the sequence with all degree 2 will also be counted 2 times if si = 1 for all i. In fact, it will be counted when the initial set is {<-, ->}, and when the initial set is {<-}.

This is because if you construct all degrees = 2, and all si = 1:
if you will start from {<-}, you will end up with {<-}.
if you start from {both}, you will end up with {both}.

That means that it will be added to both times you run the DP.

The only reason the editorial’s solution isn’t “wrong” is because in this case, “all degree = 1” case is counted only 2 times, instead of 3.

However, its claim that this is “counted in all three” is wrong. This makes we wonder, how can we prove that there will be exactly 2 overcounts across all three DP?

Thank you in advance!

[Benq]

Good catch, the editorial explanation looks wrong to me.

I believe there are always two overcounts. Basically,

1. d is counted in both \{\rightarrow\} and \{\leftarrow, \rightarrow\} iff d is all ones.
2. d is counted in both \{\leftarrow\} and \{\leftarrow, \rightarrow\} iff d_i=s_i+1 for all i.
3. It is impossible for d to be counted in \{\leftarrow\} and \{\rightarrow\} but not \{\leftarrow, \rightarrow\}.

So each of (1) and (2) always contribute one overcount. In the case where all s_i=0, (1) and (2) happen to coincide. When all s_i=1, then you get the all ones and all twos cases.