612D: The Union of k-Segments

Do a standard event based approach. Note need to handle the tail.

877D: Olya and Energy Drinks

How to improve the naive BFS runtime?!!!

To root cause is there are too many wasted edges => therefore, we try not to store or traverse them.

For each row and col, we keep set of unvisited cells, at each step of BFS, we just keep using lower_bound() and upper_bound() to find and later remove the next cell to visit

442A: Borya and Hanabi

  1. Try all 2^10 guesses, maintain a colorCount for each card, and cardCount for each color, current know cards.

  2. for each hint, populate corresponding color/card. every time we fix a point, reduce the unknown count for each color-card, by 1. Note we need to skip the already populated case.

  3. Do a recurisve reduction, stops if current know cards = n, or this reduction finds none that can reduce, if only card is known, check if the card has only 1 type of unkown color, if so, mark it as known. if only color is known - similar. If both are unkown, we can try only if only 1 color has 1 unknown cards.

14D:Two Paths

Official solution

The two paths don’t intersect, so we can try each edge that cuts the tree into two, and calc the product the longest path in each subtree

891B: Gluttony

find the inverted index of all values, and shift them to the left by one, i.e., new inverted index for 1 is the old inverted index for 2.

Proof: such shift works because, consider the subset doesn’t include the old 1 index,i.e., the new n index, the subset sum of the new one is already greater than the old one

Otherwise, the subset sum is the total sum, which is a constant, mius the subset doesn’t include the old 1, which is already different

778B: Bitwise Formula

iterate them bit by bit, use dp to solve the value

514D: R2D2 and Droid Army

since its continous, just use a two pointer to calc shift, use a heap on each col to maintain the max value. not we will allow start = end + 1, to mark invalid ones

627B: Factory Repairs

looks like fenwicks tree problem

263D: Cycle in Graph

Consier the case where we can not expand the path in DFS ANY LONGER, then all its neighbors must be on the path generated by DFS already!!! so the first vertex on the path marks the start of the cycle, and the cycle has K+1 vertices, i.e., len k + 1

I got stuck here because

571B: Minimization

This follows the patterns of decoupling (1D -> 2D) into independent parts and then recoupling (2D -> 1D)

First, notice that we can decouple the whole array in a list of silo, the indicies from the same silo have the same value mod k. The best value for each silo is to sort inside it, i.e., the different between max and min.

Moreover, to achieve the optimal value, we should avoid overlaps between the max and min values. Therefore, the problem reduced to, given a sorted array, how do we partition them into S segments (no rotation either, otherwise we will introduce overlaps)!!!

Claim: we have k - (n mod k) groups of size n/k!!!

Proof: because we organize the groups by mod value, so we have k groups in total. Because each index is evenly distributed, group sizes are either n/k or n/k + 1. We can see that we have n mod k groups that has size n/k + 1, and thus the remaining ones are the smaller groups

Now, how do we do the partitioning? Note the placement order matters even with the same group count, because the gap between silos are ignored, so we need to place our small and large groups carefully. Therefore, we do a O(k^2) bottom up DP on the optimal placement, and keep update the dp[l+1][s] or dp[l][s+1] value