June 22, 2023 Single Round Match 844 Editorials

Padding

If each wall has P inches of padding, each internal dimension of the box is 2*P smaller than its external dimensions. In other words, inside the AxBxC box we will have (A-2P)x(B-2P)x(C-2P) empty space.

MemoryGameDemo

Whenever asked to make a ‘Y’ turn, simply reveal all three copies of the alphabetically smallest letter still in the game.

During ‘N’ turns we need to ensure two conditions. The complicated one is actually easy: if we never show the third (i.e., rightmost) copy of any card during the ‘N’ turns, we will never accidentally reveal a full triple.

Let A and B be the smallest two letters that haven’t been removed yet. In odd turns we reveal the first two As + the first B, in even turns we reveal the first two B + the first A. This way we never do the same thing twice in a row.

FeedADrake

When feeding a drake a set of cakes, we can always feed them in sorted order, as in that order the drake will become full as late as possible.

When feeding a drake a sorted sequence of cakes, we can replace the last (excess+1) cakes in that sequence with the (excess+1) globally largest cakes and still have a valid solution.

Greedily take the (excess+1) largest cakes and place them aside to be eaten last. With the remaining cakes do a knapsack DP to find the maximum non-full stomach we can produce.

Presents2023

We can essentially bruteforce the search, we just need to prune it sufficiently. We can note that a can be at most sqrt(paperArea/6) < 1,300,000. We can start from the largest valid a downwards, and for each a bruteforce the value for s=(b+c), starting with the largest s such that b=s/2 and c=s-s/2 is still valid, and going up. For each s we can determine the best pair (b,c). We can break each cycle once we know the current volume must be smaller than the best one found so far. More clever solutions exist but need proofs.

VisitEdges

Each possible state of the process can be described by the current set of edges + the current vertex. For each state we’ll have a variable stating the expected time from that state to the goal.

From any state, any move goes either to a state with the same set of edges, or to a state with one more edge. Hence, we can order the states according to their number of edges (in descending order) and within the same length we can divide them into groups that share the same set of edges and only differ in the current vertex.

As the set of edges is always connected and we need to explicitly consider only states with fewer than M edges, each set of edges has at most M vertices, and thus each group contains at most M states.

For each group we can write down a system of linear equations, one for each state. The linear equations have the same form: (expected time from this particular state) = (1 for the first move we surely have to make) + sum over all possible moves of (the probability of that move) times (the expected time from the new state produced by the move).

Some of the expected times on the right-hand side we already know (those that correspond to states with more edges), the rest are variables for other states in our group. It’s easy to show that the matrix of this system of linear equations is always regular and thus there’s always exactly one solution.