agc031 - B: Reversi

Solved this during the contest. By default, DP[i] = DP[i - 1], i.e., do nothing case.

To calculate DP[i], maintain the sum of DP[j], s.t., c[j + 1] = c[i] and c[j] != c[i]

agc031 - C: Differ by 1 Bit

Rather standard pattern of guess what does not work/what proprties the solution has -> prove that it is actually sound AND complete by construction, which is often induction

Each number differs only by 1 bit. Therefore, the oddity of # of 1 bits in A and B must differ (in total 2^n - 1 steps)

Claim: we can always find such solution as long as A and B has different oddity in terms of # of 1 bits

Proof: by induction. N = 1: trivial. Suppose it is true for N = k;

when N = k + 1, We can construct a solution by taking a different bit between A and B out, find a C, and construct A_takeout ….C , C….B_takeout bits.

Because the position we take out is has 0 and 1 in A and B, respectively, we add the that missing bit back to the left and right half to restore the sequence.

The implementation can be done recursively. Note that we need to pass taken out bits and corresponding values during recursive calls

983B: XOR-pyramid

I had problem spotting the recursive relationships!!! The problem is trivial once you figure this part out. One thing i should do is to draw out the interation steps in the form of trees/pyramids

650B: Image Preview

Standard bsearch + two pointer

808D: Array Division

Find the lowset number s.t., prefix sum > half. We know that at least 1 number must be moved from the array

Option 1: just take it out, and move to suffix

Option 2: take one out, and replace it with the suffix

708B: Recover the String

Given the # of 00s and 11s, we know exactly number of 0s and 1s

The final answer form is 0000111101111000