697C: Lorenzo Von Matterhorn (!!!)

since node id < 10^18, each path has at most 64 nodes on the path i.e., there is at most 64 * 1000 entries we need to update for each node, we just record its edge length

When operation is update

start from the tail, update the edge cost one by one

When operation is query

start with the bigger number, because child id > parent id, calculate the path all the way to the LCA. Do the same thing for the small number

if small number is prefix of big number, return num1 - num2, otherwise num1 + num2

The bug I made in the code is that I used root instead of LCA! There were also function parameters where I used int instead of LL.

This problems shows again that in a tree, for the two nodes, the importance of LCA

723C: Polycarp at the Radio (!!!)

Idea 1 (my approach)

Assume all bands are within the m, then just take the average, that will be the target number, then swap until all counts are either floor(average) or floor(average) + 1

when some numbers are outside the 1..m range, we will replace them only if n - oor < average * m < n

Algorithm:

	1. count number of appearance for each number, and target

	2. scan through the array, if the band is oor, replace it with the next avaialbe one. If the band is one of the bigger ones, replace it with one of the underbudget ones. Note that we reduce oversied item to target + 1 instead of target at this step 

	3. scan through the array again, if there is any uninserted left, reduce the target + 1 to target

The mistake I made during coding is that the 2 rounds checking condition is inconsistent. One checks if the queue is empty, the other checks if the number is OOR. We need to check both in both places!

Idea 2 (official)

Notice that we just want to minimize the number of total operations, therefore, we can replace all overbudget ones first with under budget ones first, and then in a second loop, repalce out of the range ones.

This works because total # of operations is determined the total count of budget deficits, and has nothing to do the the order or selection of which over budget band to reduce

The main benefit of this approach is that we don’t have to worry about the nasty n+1 case, i.e., the final shape will have as many bands m with songs as possible, as a comparison, the shape of my solution is to have lowest highest count

723D: Lakes in Berland

DFS to find all connected waters, also for each water, mark if it is a lake or not, add it to the set of ids. Finally, scan through all cells, and fill the cells with marked ids

719C: Efim and Strange Grade

Suppose we have an optimal rounding plan, it should be applied from right to the left, because a rounding operation will kill off all digits to the right.

So we calculate c[i] = min cost to change d[i] to d[i] + 1

  1. if d[i + 1] >= 5, c[i] = 1

  2. if d[i + 1] < 4, c[i] = -1

  3. if d[i + 1] = 4, c[i] = c[i+1] + 1

In the end, we scan from left to right, and find the first c[i] <= t

747D: Winter Is Coming

What I did wrong during the contest

  1. Forget the impossible / -1 case, but the fact that have that check for the turing postive tail into negative case suggests such inconsistency is checking of calls means problem.

  2. My approach to the problem is slightly different. Instead of focusing on the negative segaments, and dirve formula based on that, and I just assume gap + 1 as number of segments, but this formula is wrong when there is no segments at all!

I realized that the special case of last element being negative or not, but instead of using the “last one positive” as base case, I used “last one negative”, but this one does not affect the code complexity

749C: Voting

  • What I did wrong during the contest
    1. I thought about simulation, but I was not able to prove it will terminate quickly given 200k input size
    2. I was not able to prove the optimal strategy is indeed optimal

Why simulation run time could work

For each vote, the total # of voters is decreased by one. Moreover, if a person is denied,we will remove that person from the line anyway. This means we will iterate through denied person O(n) times, and undenied person O(n) times

Why the official stragety is optimal

For the first element, assuming R, obviously need to deny one D before the next R.

Now suppose we have RDRDR as we go, with the first D ready to vote,

1.If veto the first R, then any D can be vetoed by the next R. Similar argument goes for vetoing the third R

2.If veto the second R, then any D has a chance to not get vetoed, because later D MAY deny further Rs

3. If there is no D after the first D, then it doesn't matter which way we choose, i.e., as long as we pick a strategy and we know it is optimal for this case