Foreword

Speed solve contest... as usual?

A: Minutes Before the New Year (00:00)

Time to new year $= 1440 - h * 60 - m$.

B: Candies Division (00:02)

We always have to give some people $\lfloor\frac{n}{k}\rfloor$ candies, and we can give at most $\lfloor\frac{k}{2}\rfloor$ peole $\lfloor\frac{n}{k}\rfloor + 1$ candies, so the answer is $\min(\lfloor\frac{n}{k}\rfloor \cdot (k - \lfloor\frac{k}{2}\rfloor) + (\lfloor\frac{n}{k}\rfloor + 1) \cdot \lfloor\frac{k}{2}\rfloor, n)$.

C: Friends and Gifts (00:09)

As we know that the given information is consistent, the information consists of closed loops, unclosed loops and individual nodes. We can compute the list of heads and tails of unclosed loops and the list of individual nodes, then attempt to connect all individual nodes into one of the unclosed loops, then close all the loops. If there are no unclosed loops, we can build a loop from the list of individual nodes.

D: Christmas Trees (00:25, +1)

We should maintain a set of used locations, and a queue of pairs of location and distance from closest tree that can be used. For each Christmas tree, try to push the two locations adjacent to it into the queue, checking whether it is already pushed or not. Then, repeat $M$ times the following process:

Pop a pair of location and distance from the queue. Attempt to push the two locations adjacent to the location of the pair into the queue, checking whether they are already used or not. Add the distance to a counter.

Finally, output the total distance and the list of locations popped from the queue.

During the contest, I used priority_queue at the beginning, but it is not required as the distance pushed into the queue is monotonic. All possible location pushed at the beginning has distance $1$ and only distance $D + 1$ can be pushed after popping a possible location with distance $D$.

E: New Year Parties (00:40)

We should perform two separate greedy for minimum and maximum number of occupied houses. Before that, we should sort the array $x$ first.

For minimum number of occupied houses, we know that houses can be combined into one if $max - min \leq 3$. We can compute the list of used coordinates and greedily calculate the number of houses required, scanning from the left.

For maximum number of occupied houses, note that for each house $h$ we can move it to any integer in $[h - 1, h + 1]$, meaning that we have a list of segments. We can try to greedily put the house on the leftmost position in $[h - 1, h + 1]$ if possible, and ignore the segment if it is not possible. We only need to maintain the last position we put a house at while scanning the array.

F: DIY Garland (01:03)

This is a construction task. We should note the observation that:

• Wire connecting to a subtree with a larger maximum node ID must have larger importance than wire connecting to a subtree with a smaller maximum node ID, as $\sum_{i=0}^{n-1} 2^i = 2^{n}-1 < 2^n$

Then we can try to emulate the process by hand, using the given example. We notice that $3$ appeared two times, so that leads us to think that numbers between the same node describes a subtree. At the end, a constructive algorithm as below is derived:

1. $a_1$ is the root of the tree.
2. For each $a_i$, if $a_{i+1}$ is not yet in the tree, add the edge $a_i \rightarrow a_{i+1}$.
3. Otherwise, add the edge $a_i \rightarrow k$ where $k$ is the largest node ID not already in the tree. Note that $k$ may appear later in the array $x$.

While performing step 3, check that the list of unused node IDs isn't empty. (Not sure if required or not.)

At the end, perform a DFS to check that all nodes are connected into the tree. If it is, then we have successfully constructed the required solution. We can output the solution constructed.

Results

Yay!