509C: Sums of Digits

need to know minGood[i], suppose we know minGood[i-1], need to find the miniumum number > minGood[i], and sum of digits = b[i], gine b(i), we know the min size of digits.

Then we know the length of string has at most two choices, size of string, size of string + 1, or sum of digits/9

In each case, we just brute force on each digit, and see if it is possible to fit that digit into, i.e., the remaining digit sum range can contain the remaining b[i]

O(n^3) run time, because we have to represent the number as a string

374C:Inna and Dima

Use 4 step BFS to find the edges between D nodes => 4 * 3 * 3 < 40 mil edges max

We can find an edge, we can can use a union find to see if the vs are within the same component, if so, then cycle.

In the end, calculate longest path in each tree

Official solution is confusing to read

264C:Choosing Balls

For each ball, calc the prevvious color index, then we have two choices, either use all values between the two balls,or just use the previous ball + current v * a(i)

353D:Queue

Observations

  1. Relatively orders of girls do not change

  2. t(i) >= final pos - init pos , call it D(i).

  3. t(i) >= t(i-1) + 1, because at t(i-1), D(i - 1) + 1 = D(i) is occupied by a boy !!!

  4. Because each one moves as fast possible, so each t(i) is the max of the two. Note such pattern seems not uncommon, i.e., giving list of reachable lower bounds, the minimal answer is the max of those reachable lower bounds

  5. Alternatively, we can use the blocking -> non-blocking + hold trick!!! That is, we don’t swap the F until we are sure that we will not be blocked by previous girl. This means startT(i) = startT(i-1) + 1, if i and i-1 are next to each other. or startT(i) = startT(i-1) - (numM between i and i-1) + 1 !!!

Final answer is max of startT(i) + D(i)

592D:Super M

Find the longest path in the tree, and the answer is len - longest path, just need to tweak the algo a bit the skip subtrees with no nodes to visit

141C: queue

Sort the pair by a(i), and assign n….0 to them. Then for each, just assign them to the existing vector at a[i]. Of course, if a[i] > current size, it is impossible

The insertion can be done by res.insert(res.begin() + a[i], man)!!!

142B:Help General

cases: n or m = 1, n or m = 2, n >=3 and m >= 3. Note that it is a known conclusion that in such case a knight path exists!!! Therefore, we just take every OTHER node of the path to avoid conflict

918C: The Monster

For each i, we start scannning from right to left, and keep track of how many free ?’s we have, and how many (, we have

if size of stack is empty, but we have ( incoming, reduce ?, if nothing to reduce, we know we are bad already if size of stack + free ? % 2 = 0, we add sum[i - j] to sum [i]

The final result is the sum[0] to sum[j]

918D: MADMAX

standard DAG dp, with state[A’v][B’s][last char][A moves now]

Note the first step is special, don’t include them in the DP state

770C:Online Courses In BSU

Standard DP on DAG problem. Also note the standard 3 state cycle check problem

613B:Skills

  1. check if possible to fill all skills to max level

  2. The final form is that some mininum are raises, and some are increased to max numbers, we know that

a. if incrase all mins by 1, the increased cm < cf

b. if increase a skill to A, then increase cf < increaseing the min cm

  1. Therefore, we can calculate the cost to make the min K aligned together

  2. After that, we try filling max number one by one, and given the pre-computatin, we know exactly the max min value we can reach, so each fill step can be calcualted in O(logN)

652C: Foe Pairs

keep track of current index at 0, maintain a heap that sorted by end and the start

Keep popling the heap

  1. if the curStart >= curIndex, add curEnd - startIndex, and then update curIndex to curStart + 1

  2. in the add add n - startIndex

919D: Substring

  1. if it has cycle, can be infinitely large

  2. otherwise, it becomes longest path on the tree problem, once for each letter

788B: Weird journey

Hard problem for me - uses facts about Euler graph

117C: Cycle

Do a dfs, while maintain an index on the current DFS path, every time we reach an “visiting” node, we can check if that node’s index = current Index - 2