• Great contest:
• Good contest:
• Average contest:
• Bad contest:

The official lore is that he got lost in a forest of oddly colored Christmas trees (from problem F) and decided instead to write this editorial.

• Great problem:
• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

What can we say about the number of 'Yes's.

Consider the number of 'Yes's in the string, and what happens to this number during an operation.

Python, C++

• Great problem:
• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

You have a suspicious string. For a fixed u, suppose the closest s is two characters to the right. Where must the other s be?

You have a suspicious string. Suppose there are two consecutive u's. Let the closest s to the left u is three characters to the left. Where must the other s be? Where must the closest s's to the right u be?

Python, C++

• Great problem:
• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

The number of children on the naughty and nice lists combined will be $$$n-1$$$. However, not all assignments to the naughty and nice lists are possible. Try figuring out exactly which assignments are possible.

Exactly one child will not be chosen by Santa. If we fix/decide which child this will be, what can we say about the other children?

Python, C++

• Great problem:
• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

Fix the $$$m$$$ surviving elves. They must have attacked. Who are the targets of these attacks? What happens to those targets?

Find an upper bound on the number of elves that can survive.

Once the elves that survive are fixed, and the elves they attack are fixed, there may be some remaining elves, which should not survive. Find a way to deal with them.

$$$m=0$$$ must be handled separately (why?). The hardest part is killing the strongest elf. Figure out when it is possible and how to do so.

Python, C++ (by Auchenai01)

• Great problem:
• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

What are the properties/invariants of the flatten operation? Use this to find an invariant on $$$a$$$ and $$$b$$$.

Assume there are no flatten operations after the final concatenate (why?). Can we find where in the hidden array $$$a$$$ the final concatenate happened?

From the previous hint, the final array can be split into the two arrays before the final concatenate. Which array contains the maximum?

Recurse.

Python, C++ (by Auchenai01)

How would you write a validator for this problem? That is, given $$$n$$$ and an array $$$a$$$, determine if it can be generated by the described operations.

• Great problem:
• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

Try drawing the operation on some not small graphs!

What are the invariants of the operation?

The number of white vertices does not change. It also seems a lot of white vertices don't move or only move to a neighboring vertex.

In a single operation, what are some shared properties of the vertices whose color changed?

Color changes only occur within the detached subtree (why?) and it is a necessary condition that a vertex with a new color has a new parent.

Based on Hint 2, try to characterize the set of edges that cannot be removed no matter what operations are applied.

The parent edge of any black vertex cannot be removed (why?). Any other edge can be freely added and removed as long as T is a tree.

Consider the connected components formed by the parent edge of all black vertices (in other words, after cutting the parent edge of any white vertex). Which vertex is white within this component?

Exactly one vertex is white and it is the one closest to the root.

What does the conquered condition mean in terms of these connected components?

Python (by golomb), C++

• Great problem:
• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

Try to solve the problem for only $$$\ell=n$$$.

The problem forces you to incrementally compute the values for $$$\ell=1\ldots n$$$. Try to solve the problem in quadratic or cubic time while only allowing yourself to consider the chords in order (i.e. you're not allowed to go backwards to compute the number of chains starting at a given chord).

In addition to storing the parity of number of chains ending at chord $$$i$$$, also store the set of chords $$$k \lt i$$$ such that chord $$$k$$$ appears in an odd number of chains ending at chord $$$i$$$. Then, for a fixed $$$\ell$$$, we want to check whether every chord appears in an even number of sets (this can all be done with $$$n$$$ Fenwick trees, one for each chord).

You have yet to use the fact that we want every chord to appear an even number of times (that is, we do not need to know the specific parity for each chord). Use this to speed the solution up to $$$O(n\log n)$$$.

Python (by golomb), C++

• Great problem:
• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

The operation is clearly independent for each present. Solve the problem for a single type of present with value $$$a$$$.

Consider a graph with vertices $$$0\ldots m-1$$$. We draw an edge from $$$x \to (x+a) \text{ mod } m$$$ with cost $$$a$$$ and an edge from $$$x \to 2\cdot x \text{ mod } m$$$ with cost $$$k$$$. The desired answer is the shortest path from $$$a$$$ to $$$0$$$. However, it is not possible to combine the results for all three types without $$$O(n^2)$$$ $$$(\min, +)$$$ convolution.

There is one big idea that you need from here, the following small hints may help in getting you there.

C++ (model sol), C++ (by Auchenai01, with an optimization)

Solve the problem in $$$\mathcal{O}(m)$$$.

• Great problem:
• Good problem:
• Average problem:
• Bad problem:
• Did not solve:

The input essentially just creates a graph, where cities are connected if they are at distanct $$$\sqrt{k}$$$. Can you find any special properties that this graph has?

The input graph is bipartite.

One of the color classes of the bipartite graph must have size at most 15

Try finding an equivalent formulation to what the explosiveness can mean (in particular, try assigning some `value' to each node not in $$$T$$$

We can brute force over all possible subsets of the smaller bipartite class.

C++