Round 61: Paint the Fence

Even-based approach, looking for the fence with layer 0.

Partial-sum approach

we mark delta[L] = 1, delta[R +1] = -1, then the number of layers at i = sum of delta[0] + delta[1]….+delta[i]

Can do a second ps on if layer[i] = 1 or 0, so we can calculate # of solutions between [L, R] efficiently

Round 61: Strictly Increasing Array

If we are looking for a non-decreasing array, we just need to find LCS. However, we can not use it directly, as we know A(j) - A(i) >= j - i, in the LCS we found!!!

So we just do a reduction, i.e., A(j) -j >= A(i) - i, this reduces to our LCS problem.

Round 62: Simple Paths

Find the first path from A to B, mark all discovered edges as bad. Then run again, while ignoring the blacklist.

Official solution

For each edge, calculate if it is a bridge or not => i.e., if without this edge, the graph is still connected

Then for each query, try to find a path without containing any bridge!!!

Round 62: Partial Maximums

Do a rolling start, keep track of top 2 numbers. For each number, track if it is already max, only 1 greater, or 2 greater than that. If only 1 greater than the current number, that greater number count++.

In the end, we just looking the number with max count, plus all number that is already max.

Official solution

Claim: We can introduce new partial maximums only if we removed an existing one!!!

Proof: Suppose suppose a new partial maximum got introduced as a result. then the one removed must be > all before i, i.e, the removed on itself j (j < i), must be a partial maximum

so for each 3 consecutive local maximua, we can just remove the middle one and do a brute force search

Note that for the last partial maixumum, removing it will introduce at most 1 new one, so we can ignore that case