799D: Field expansion

I tried a greedy approach, but couldn’t prove it. This is often the sign a greedy approach won’t work.

Insight

  1. Obviously, we only care highest factors

  2. The key insight I missed is that given the input is only 10^6, number of factors <= 34, i.e., we can do a brute force dp approach!!!

maxV[i][h] = max w value when we are at factor i, with h value h

max[i][h] = MAX(max[i-1][h] * f[i], max[i-1][h/f[i]])

when h, w is greater than the bound, we will use a dummy value for that!

140D: New Year Contest

Obviously, we pick the quickest problems, as long as total sum <= 720

Claim: we should solve problems in the order of length, that gives the best solution

Proof: consider the the last different choice. If the finish the time is before midnight, we can just make changes, and won’t affect the overall result. But if the finish time of that block is after midnight, let us move the longest unassigned one after the different choice

penalt after <= oldPentalty - min(diffFinishTime, longestLen) + 0, + 0 because the end time is the same => i.e., swapping such means optimal solution

229B: Planets (!!!)

Idea similar to dijkstra, the only different is that upon expanding, see if we need to wait

I tried re-inserting entry but got TLE, so we just wait until we can expand to next edge.

The speical case is when we are at n already