2020 ICPC North America Championship Solutions

Here are my solutions to NAC 2020.

Problem A - Another Coin Weighing Puzzle

Consider the decision tree. Suppose we get the sequence on weighings. Notice that only relative scale of the weights matter because we have no idea about the weight of fake coins, therefore we require to be to avoid overcounting. The maximum number of leaves the decision tree could have equals to the number of valid sequences where each element of lies in the range . (Signs indicate whether left / right is heavier)

We can show that such decision tree exists, because a sequence could also map to the number of coins to put on the left / right side of the scale each time, for coins in a fixed bag. Therefore the answer is exactly the number of valid sequences such that:

1. 
2. 

To compute this, we can use mobius function.

*The extra comes from the special case when all . When deriving the formula, we don't consider this case in the summation.

Overall runtime is .

Problem B - Mini Battleship

Simulation and search. Prune branches wherever possible.

Problem C - Bomas

Let's put queries offline and consider all queries circles together with existing circles.

The outlines of circles do not intersect, and thus the inclusion relationship of circles form a tree. We root the tree with the outside area. Compute and store the leftmost and rightmost border of circles, add an event of "Entering the circle" at the leftmost x-coordinate, and "Leaving the circle" at the rightmost x-coordinate. Sort and scan the events by x-coordinate, and maintain the upper and lower arc of the circle separately using an ordered set, because relative order of y-coordinates of arcs never change. We can know the parent of each circle by finding the arc right above it when we scan through its left border, and in this way constructs the tree structure.

The rest of the problem is just a classical DP problem - independent set on a tree.

Runtime is .

Problem D - All Kill

Let's begin with a solution that is not completely correct.

The problem can be interpreted as finding the number of ways that your friend comes up with the solution of each problem, such that all problems are solved in the end and your coding time is consecutive for each problem.

Since we know the number of minutes you're coding problems and the number of minutes you're idle, let's use a time slot for coding each problem and a time slot for each idle minute. Let , then the number of total time slots is . The problem becomes finding the number of ways to assign each problem a time slot.

Let's order the problems in ascending problem number. For the i-th problem, we can:

1. Assign an empty time slot. The number of ways to do this is .
2. Assign a problem to some time slots that is already occupied. In this case, the problem will be postponed to the next available slot. The number of ways to do this is .

Therefore, we can consider each problem indenpendently, and the answer would be the product of the number of ways to assign each problem a slot.

Noticed the issue? In the second case, there may not be one available slot if all later time slots are occupied. To fix this issue, we consider the time slots in a loop, i.e. the next time slot of the last one is the first one. In this way, we can always find one available time slot after skipping occupied ones. We'll need to break the loop somewhere, therefore we add one more time slot for the break, and at the end we multiple the answer by the number of ways to break the loop using one empty time slot, i.e. . Finally, we need to divide the answer by because we overcount rotations of the same loop.

Runtime:

Problem E - Grid Guardian

Notice that if either n or m is odd, then we can only place obstacles on even indexes of that dimension. Use pigeonhole principle for a formal proof. So the problem can be solved easily in such cases.

Let's only consider the case where n and m are both even. We divide the grid into squares, and for each square we must put exactly one obstacle. For each row, there is some k (possibly 0) such that the leftmost k squares have an obstable on the right column of the square and the rest have an obstacle on the left. (If not, there would be an empty square across the boundary of two squares in this row) Same for columns.

However, this is a necessary but insufficient condition. There are two cases that violates the constraint:

.x ..
.. .x
x. ..
.. x.

.. x.
x. ..
.. .x
.x ..

To take this into account, we need to do a state compression dynamic programming. Let be the number of ways to construct a grid without empty squares, where the k value of the last column is k, and the last column has state S. S is a binary number which uses its j-th bit to indicate whether the last square on the j-th row has the obstacle on its left column. If that is true, all later squares must have their obstacles on the left columns. These states are sufficient for dynamic programming while eliminating the violation case.

I think this problem is supposed to be solved by state compression dynamic programming based on contour lines which should give a better time complexity, but I'm too lazy to write that solution so I tried to compute a transition table and optimize my DP with prefix sums. This solution passes the test cases within time limit.

Problem F - Hopscotch 50

Let be the minimum distance traveled ending at the tile . We iterate over tiles in increasing order of their values and update DP values correspondingly.

Runtime is .

Problem G - ICPC Camp

Binary search on D. Then the problem becomes a decision problem - given D and s, is there a feasible selection of problems?

Sort the problems in ascending order of difficulties. Notice that for each classical problem, the range of creative problems that could be selected at the same time lie in a consecutive range. Therefore, the problem is equivalent to selecting maximum number of items so that each item matches a unique range. This requires a classical greedy algorithm.

Runtime is .

Problem H - Letter Wheels

Compute all feasible offsets for each pair of rows. Once done, try all possible offsets of second and third rows, check if this results in a valid letter wheel using the preprocessed results. When calculating minimum rotation, also take rotating the first row into account. Runtime: .

Problem I - Editing Explosion

Let denote the number of valid strings of length i, and S is a compressed state containing the edit distance from current string to the j-th prefix of the query string. i is upper bounded by |s|+d. Notice that the edit distance from current string to the 0-th prefix (length 0) is exactly i, and the edit distances to j-th and (j+1)-th prefix differ by at most 1. Thus we can use a 3-based integer to encode the difference which allows us to retrieve the entire edit distance array.

The rest of the transition is very similar to finding edit distance between two strings.

The total runtime is .

Problem J - Lunchtime Name Recall

Let be the maximum number of colleagues we can identify, given that on the i-th day, we can identify some groups of people encoded in S. Basically we can just do a brute force search on this since data range is small, but we need some optimizations:

1. We only need to know the size of each group in the state S. Thus we can sort groups in ascending order of group size and hash them.
2. When we try to distribute burgers to all groups we have, we need a recursive helper function. Since groups are already sorted, groups of equal sizes must be consecutive. For these groups, we force distributing no fewer burgers to prior groups to prune branches.

Runtime is , where is the partition number of integer n. Note that this is a very loose bound.

Problem K - Rooted Subtrees

For two roots r, p:

1. If either u or v is not on the path , then should be a subtree existing in both and ;
2. if both u and v are on the path , then would be a unique set as long as does not proceed on . Let the number of nodes on the path be x (inclusively), then the number of ways to choose u,v is .

Therefore, the answer is . To compute the distance between two nodes on a tree, we need to know their LCA. There are a lot of ways to do this and I used Tarjan's offline algorithm.

Runtime:

Problem L - Tomb Raider

For each gargoyle, we can find the first gargoyle or obstacle to each of its 4 faces with memoization search. Then, the direction of this gargoyle uniquely defines the direction of all related gargoyles, and this process repeats recursively. In other words, for each connected component of gargoyles, we choose the direction of an arbitrary gargoyle, then the directions of all other gargoyles inside the same component can be determined. Therefore, there are only two ways to place the gargoyles inside the same connected component, and we can choose the one requiring fewer rotations. Do this for each connected component to get the answer.

Runtime: .