954C: Matrix Walk

  1. scan through all diffs, they must be either 1, or a delta => which we find y

  2. now we can go through the steps again, and deduct x, i.e., just need to ensure that cols match

954D: Fight Against Traffic

Compute all dists from s, and all dist from t

For each pair (i,j), see if (s,i) + (j, t) + 1 or (s,j) +(t, i) + 1 is smaller

955C: Sad powers

Generate all possible answers for P >= 3, and discard all perfect squares!!!

At each query, can get the band range in two bsearchs, and perfect squares can be calculated via math

934D: A Determined Cleanup

Polynomial long division

957D: Riverside Curio

Hard problem for me!!!

  1. Note that total marks at each day t(i) = m(i) + d(i) + 1

  2. lower bound: t(i) >= max(t(i-1), m(i) + 1)

  3. Each day leaves at most 1 mark => t(i) >= t(j) - (j - i)

Claim: we will try finding a solution that satifies all 3 conditions, then we have a valid sequence of actions, and this solution is optimal

Proof: Going backwards, we reduce the current number by one - try lower the upper bound as much as we can, even to the point of too low, and lowerbound it with the current m(i) + 1 to satify condition 2.

After that we just run forward again to pad the lower bound we reduced too much in the first pass. This simulation process also ensured that the solution is valid