387C: George and Number

  1. Suppose the numbers have no 0, then answer is either N or N -1, depending on the first two digits

  2. If the nubmers have 0 suffix, then it must be part of the number, if the prefix < the number, so we look for the right most occurance of prefix < the 0-suffix, then we know it must be a single number. To the right of it, all prefix > 0-suffix, so we can just add the numbers one by one!!!

570D: Tree Requests

Do a DFS, keep track of the following things

  1. upon visiting each node, add it to the end of the list which is for all nodes at that level - this is where I got stuck!!! The effect is that each list is a left-to-right scan of the tree, i.e., for each node, there exists [l, r] s.t., all nodes in that band are children of that root node.

  2. keep track of in/out time of each node, make sure add time by 1 at each in AND out

By 1) and 2), we can see that l >= in time of the root node, and r <= out time of the root node => so just bsearch twice. Use lower_bound!!!

Once we get bound, we can do a prefix sum on each letter, to decide if there is too much odd numbers.

487B: Strip

Just go greedy to expand band from left to right

Official solution

f(i) = min(f(j)) + 1, i - g(i) < j < i - l

260C: Balls and Boxes

The last index must have one of the lowest values.

For each candidate,

  1. if i = x, we are good

  2. if i > x, then there is no value = min value in the range of [1, i], [x + 1, n]

  3. if i < x, then there is min value in the range of [i+1, x]

so we need to keep track of

  1. left most min value

  2. right most min value

  3. rightmost min value to the left of x

Official solution

Consider the reverse of the operation, we remove balls one by one from right to the left, at one point, we will reach a 0, and that will be one feasible choice for the init index.

To speed up implementation, we can just reduce all values by minV - 1, and then finish the last incomplete loop

432C: Prime Swaps

Calculate all primes <= 10^5, and inverted index for each number. For each number, use bubble sort idea, except that pick the larget prime < distance, and repeats. The prime number is about 10% of all numbers, i.e., we can reduce the distance to 1/10 in each swap => good for 5N requirments

691D: Swaps in Permutation

get all chars and indices in a components, sort the chars and components

825D: Suitable Replacement

Do a bsearch on the final number, find the larget one s.t. number of ?s > missing chars we need to fill

305C: Ivan and Powers of Two

First, preprocess the inputs to remove all duplicates of powers, i.e., for each power, get the count, and then add each binary index to the count of binary + current power

Then we scan from v = 1 to maxV => answer is just ?!!!

524C: The Art of Dealing with ATM

For each request, for each bill, try k1 from 1 to 20, the k2 from 0 to 20 - K1, see if K2 is a possible solution

Official solution

Create < 5000 * 20 possible values, with least # of bills to get the value. For each of the 20 query, we iterate over the first part, and look up on the second part

873C: Strange Game On Matrix

for each column, the band size is fixed, so we can just two pointer to find the highest starting band with max value. The cost is the band sum in [0, optimalStart]

360A: Levko and Array Recovery

make an upper bound for each entry. For op type 1, update the delta array, for op type 2, update the upper bound for the band.

In the end, run the array through the sequence of action again to verify all op2s are still good.

615C: Running Track

Just brute force, try both forward and backwards for the longest substring that matches the current head. Note that by the greedy approach, it doesn’t matter if we matched more in the first then the second => O(n^2)

Official solution use a DP LCP(i, j), to calculate the longest common prefix of the suffixes, i to m, j to n, and longest comon prefx i to m, j to 1