828C: String Reconstruction(!!!)

A brute force way will timeout. What can we do to remove duplicate operations?

My idea

So we need to track of continuous intervals, and skip them if it is already filled.

We can keep each segment’s previous empty and next empty index, with path compression to help run time. However, this gives TLE?!

Official solution

Sort strings by index, and keep track of the index before which all has been seen. At each step, either increase index and fill partial strings, or ignore the current string because it is within the processed prefix

831C: Jury Marks

Calculate prefix sum of scores, and sort both deltas. We know the min value of B must match [0, k - n] of the delta array, so we can just brute froce on each potential match to see if it is feasible to backtrack, calculate the backtrack and add the calculated result to the result set

Note that once we fix ONE mapping between b(i) and a(j), the whole sequence becomes deterministic, i.e., the answer <= k - n + 1