agc020_a: Move and Win

A naive DP-ish approach will not work, because you can move back and forth => creates cycles, thus should not use DP approach and think about an insight based approach

agc020_b: Ice Rink Game

I used a band-based approach to reverse and calc min-max values.

But note that at each step, f(x) = x - x mod a[i], i.e., f(x) is monotonic, and the whole sequence of actions can be though as a composition of monotonic functions. Thus, we can just bsearch min/max to see if the final answer >= 2 for lower bound, and <= 2 for upperbound!!!

The uppoerbound for k is 2 + K * max(A(i))

agc020_c: Median Sum

Consider any subsequence and its complements, we know that one must be =< total/2, one must be >= total 2, i.e., for any subsequence <= total/2, we can mirror its complemnet to the other side => total/2 IS the cut off value for median!!!

Therefore, we can DP to find the min value >= total/2. We can compress the DP state by keeping only a list of values, and scan from max value to min value

Official implementaion uses a bitset which I don’t quite understand!!!