Codeforces Round 611 (Div 3) Solution & Reflection

December 29, 2019


Foreword

Speed solve contest... as usual?

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

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

B: Candies Division (00:02)

We always have to give some people nk\lfloor\frac{n}{k}\rfloor candies, and we can give at most k2\lfloor\frac{k}{2}\rfloor peole nk+1\lfloor\frac{n}{k}\rfloor + 1 candies, so the answer is min(nk(kk2)+(nk+1)k2,n)\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 MM 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 11 and only distance D+1D + 1 can be pushed after popping a possible location with distance DD.

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 xx first.

For minimum number of occupied houses, we know that houses can be combined into one if maxmin3max - 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 hh we can move it to any integer in [h1,h+1][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 [h1,h+1][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 i=0n12i=2n1<2n\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 33 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. a1a_1 is the root of the tree.
  2. For each aia_i, if ai+1a_{i+1} is not yet in the tree, add the edge aiai+1a_i \rightarrow a_{i+1}.
  3. Otherwise, add the edge aika_i \rightarrow k where kk is the largest node ID not already in the tree. Note that kk may appear later in the array xx.

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!

Codeforces Div.3 Round #611 Results