July 21, 2020 2020 TCO Caribbean and South-Central America Regionals Algorithm Round Editorials

TCO20 Caribbean and South-Central America Regionals Algorithm Round

Qualification, 250 points: TimeLimit

The largest possible time limit that does not allow any of the bad solutions to pass is T = min(bad times) – 1.

If T allows all good solutions to pass, it is the answer. If it doesn’t, there is no answer.

Qualification, 500 points: OrderingTakeout

A classic shortest paths problem. Compute single-source shortest paths from 0 to all other nodes, then find the closest restaurant, then iterate over all restaurants and find the best one among those that are close enough.

Qualification, 1000 points: LetterS

Dynamic programming. Various implementations possible. The solution I prefer is to ignore the way a letter-S shape is defined and instead define it as a path that consists of five segments: at least one step left, at least two down, at least one right, at least two down, and at least one left. Once you do that, you can do dynamic programming on “in how many ways can I draw the first X segments of the path and end at coordinates (R,C)?”

The above DP can be implemented by iterating over all X. For a fixed X, you take the previous values, do their prefix sums in the direction of the next segment, and then look up the total number of paths that can reach a particular cell. For example, if you are processing the fourth segment (at least two steps down) and you want to end at (R,C), you need to sum all ways to draw the first three segments and end at (r,C) such that r <= R-2 and there are no blocked cells between (r,C) and (R,C).

As the number of segments (5) is a constant, the above solution is O(dimensions of the grid).

---

Points for problems in elimination rounds don’t really matter if we don’t allow them to challenge and give them just a single problem. I propose using 500 points for each of them. I also propose using 25-30 minutes for each round as the problems are too hard for shorter rounds.

Elimination round 1, 30 minutes: CardDrawOpponent

Minimax with two layers: the dealer picks the option that minimizes our chance to win, we pick the one that maximizes it. We can use brute force to examine all options, the only caveat is that we need to brute force the values of the cards redrawn and not individual cards.

Elimination round 2, 30 minutes: ChangePositions

If everybody is in place, 0 rounds. If nobody is in place, 1 round. If N == 3 and none of the previous cases applies, we have exactly one person in place and there is no solution (after each possible round there will be exactly one person in place again).

If we got this far, we need at least two rounds of dancing, and two rounds are always sufficient. Note that we have N >= 4, as all tests with N <= 3 are of the types handled above.

We need to find an intermediate state (after round 1) that differs in all positions both from the starting and from the final configuration. Such a state always exists. It can be constructed greedily (starting with splitting the start permutation into cycles), but a nice argument and a construction with no special cases follows from Hall’s marriage theorem.

Imagine a bipartite graph with positions on the left, dancers on the right, and edges representing “this dancer can stand on this position after round 1”.

For any set of positions P, let D(P) be the dancers who can stand at some position in P after round 1. (I.e., D(P) is the set of neighbors of P in our bipartite graph.)

If |P| <= N-2, we have |D(P)| >= N-2 because already each individual vertex in P has degree at least N-2.

If |P| >= N-1, we have |D(P)| = N because P has at least three elements and each dancer has at most two forbidden positions.

Thus, we have |D(P)| >= |P| for all P, and therefore the graph has a perfect matching.

(Of course, the brave solution is to implement a solution that just tries random permutations until it finds one that works, arguing that for small N it will eventually try all possibilities and for large N the probability that a random permutation works is big enough.)

Elimination round 3, 30 minutes:

BucketThief

Fairly straightforward DP problem. For buckets 0…N, we can either take any valid selection of buckets 0…N-1 and not take bucket N, or we can take any valid selection of buckets 0…N-2 along with bucket N.

ClickOnAll

A row of dimensions 1xC for C >= 5 can be solved by first clicking all cells in even-numbered columns (left to right) and then all cells in odd-numbered columns (left to right again).

These solutions stack on top of each other: if we have any RxC grid with C >= 5 we can simply solve each row separately using the pattern described above. Hence, any grid with at least 5 columns can be solved.

Any grid with at least 5 rows can be solved by transposing the solution described above.

This leaves us with just a constant number of special cases: the grids 1×1 to 4×4.

The 1×1 grid can be solved by clicking its only cell.

A solution for 1×4:

2031

A solution for 2×4:

4051

6273

Solutions for 3×4 and 4×4 can now be constructed by combining the solutions shown above.

All other grids (1×2, 1×3, 2×2, 2×3, and 3×3) are unsolvable. To see why, note that in each of them

we can find a cell that is a neighbour of every other cell.