Here's the editorial. Hope you have a happy new year!

Code can be found here: https://www.dropbox.com/sh/i9cxj44tvv5pqvn/AACQs7LLNyTZT-Gt_AMf7UQFa?dl=0

**New Year and Counting Cards**

Let's start off a bit more abstractly. We would like to know if the statement "if P then Q" is true, where P and Q are some statements (in this case, P is "card has vowel", and Q is "card has even number"). To do determine this, we need to flip over any cards which could be counter-examples (i.e. could make the statement false).

Let's look at the truth table for if P then Q (see here: http://www.math.hawaii.edu/~ramsey/Logic/IfThen.html). The statement is only false when Q is false and P is true. Thus, it suffices to flip cards when P is true or Q is false.

To solve this problem, we need to print the count of vowels and odd digits in the string.

**stats**

First solve: ksun48 at 00:01:01

Breakdown of results for submissions that passed pretests

```
OK 6427 (98.74%)
CHALLENGED 60 (0.92%)
WRONG_ANSWER 22 (0.34%)
TOTAL 6509
```

**New Year and Buggy Bot**

This problem is intended as an implementation problem. The bounds are small enough that a brute force works. We can iterate through all mapping of numbers to directions (i.e. using next permutation in C++ or doing some recursive DFS if there is no built in next permutation in your language), and simulate the robot's movements. We have to be careful that if the robot ever gets in an invalid state, we break out early and say the mapping is invalid.

**stats**

First solve: jonathanirvings, dotorya at 00:05:16

Breakdown of results for submissions that passed pretests

```
OK 4192 (83.72%)
WRONG_ANSWER 652 (13.02%)
CHALLENGED 126 (2.52%)
RUNTIME_ERROR 33 (0.66%)
TIME_LIMIT_EXCEEDED 4 (0.08%)
TOTAL 5007
```

**New Year and Curling**

This is another simulation problem with some geometry. As we push a disk, we can iterate through all previous disks and see if their *x*-coordinates are ≤ 2*r*. If so, then that means these two circles can possibly touch.

If they do, we can compute the difference of heights between these two circles using pythagorean theorem. In particular, we want to know the change in *y* coordinate between the two touching circles. We know the hypotenuse (it is 2*r* since the circles are touching), and the change in *x*-coordinate is given, so the change in *y* coordinate is equal to , where *dx* is the change in *x*-coordinate.

We can then take the maximum over all of these cases to get our final *y*-coordinate, since this is where this disk will first stop. Overall, this takes *O*(*n*^{2}) time.

**stats**

First solve: henryx at 00:04:05

Breakdown of results for submissions that passed pretests

```
OK 2694 (63.81%)
WRONG_ANSWER 1064 (25.20%)
CHALLENGED 448 (10.61%)
RUNTIME_ERROR 11 (0.26%)
TIME_LIMIT_EXCEEDED 4 (0.09%)
MEMORY_LIMIT_EXCEEDED 1 (0.02%)
TOTAL 4222
```

**New Year and Arbitrary Arrangement**

The main trickiness of this problem is that the sequence could potentially get arbitrary long, but we want an exact answer. In particular, it helps to think about how to reduce this problem to figuring out what state we need to maintain from a prefix of the sequence we've built in order to simulate our algorithm correctly. This suggests a dynamic programming approach.

For our dp state, we need to keep track of something in our prefix. First, the most obvious candidate is we need to keep track of the number of times 'ab' occurs in the prefix (this is so we know when to stop). However, using only this is not enough, as we can't distinguish between the sequences 'ab' and 'abaaaa'. So, this suggests we also need to keep track of the number of 'a's.

Let *dp*[*i*][*j*] be the expected answer given that there are *i* subsequences of the form 'a' in the prefix and *j* subsequences of the form 'ab' in the prefix.

Then, we have something like *dp*[*i*][*j*] = (*p*_{a} * *dp*[*i* + 1][*j*] + *p*_{b} * *dp*[*i*][*i* + *j*]) / (*p*_{a} + *p*_{b}). The first term in this sum comes from adding another 'a' to our sequence, and the second comes from adding a 'b' to our sequence. We also have *dp*[*i*][*j*] = *j* if *j* ≥ *k* as a base case. The answer should be *dp*[0][0].

However, if we run this as is, we'll notice there are still some issues. One is that *i* can get arbitrarily large here, as we can keep adding 'a's indefinitely. Instead, we can modify our base case to when *i* + *j* ≥ *k*. In this case, the next time we get a 'b', we will stop, so we can find a closed form for this scenario. The second is that any 'b's that we get before any occurrences of 'a' can essentially be ignored. To fix this, we can adjust our answer to be *dp*[1][0].

**stats**

First solve: dotorya at 00:16:46

Breakdown of results for submissions that passed pretests

```
OK 449 (99.78%)
WRONG_ANSWER 1 (0.22%)
TOTAL 450
```

**New Year and Entity Enumeration**

Let's ignore *T* for now, and try to characterize good sets *S*.

For every bit position *i*, consider the bitwise AND of all elements of *S* which have the *i*-th bit on (note, there is at least one element in *S* which has the *i*-th bit on, since we can always by *m*). We can see that this is equivalent to the smallest element of *S* that contains the *i*-th bit. Denote the resulting number as *f*(*i*).

We can notice that this forms a partition of the bit positions, based on the final element that we get. In particular, there can't be a scenario where there is two positions *x*, *y* with such that . To show this, let , and without loss of generality, let's assume (it can't be simultaneously equal to *f*(*x*), *f*(*y*) since ). If the *x*-th bit in *b* is on, we get a contradiction, since *b* is a smaller element than *f*(*x*) that contains the *x*-th bit. If the *x*-th bit in *b* is off, then, is a smaller element of *S* that contains the *x*-th bit.

So, we can guess at this point that good sets *S* correspond to partitions of {1, 2, ..., *m*} one to one.

Given a partition, we can construct a valid good set as follows. We can observe that a good set *S* must be closed under bitwise OR also. To prove this, for any two elements , . Since the latter is some composition of XORs and ANDs, it it also in *S*. So, given a partition, we can take all unions of some subset of the partitions to get *S*.

For an actual solution, partitions can be computed with bell numbers, which is an *O*(*m*^{2}) dp (see this: http://mathworld.wolfram.com/BellNumber.html ).

Now, back to *T*, we can see that this decides some partitions beforehand. In particular, for each bit position, we can make a *n*-bit mask denoting what its value is in each of the *n* given values. The partitions are based on what these masks are. We can find what the sizes of these splits are, then multiply the ways to partition each individual split together to get the answer.

**stats**

First solve: Petr at 00:26:54

Breakdown of results for submissions that passed pretests

```
OK 166 (100.00%)
TOTAL 166
```

**New Year and Rainbow Roads**

Let's make a few simplifying observations

- It is not optimal to connect a red and blue point directly: Neither Roy or Biv will see this edge.
- If we have a sequence like red green red (or similarly blue green blue), it is not optimal to connect the outer two red nodes. We can replace the outer edge with two edges that have the same weight. This replacement will form some cycle in the red-green points, so we can remove one of these edges for a cheaper cost.

With these two observations, we can construct a solution as follows. First, split the points by the green points. Each section is now independent. There are then two cases, the outer green points are not directly connected, in which case, we must connect all the red/blue points in the line (for 2 * length of segment weight), or the outer green points are directly connected, in which case, we can omit the heaviest red and blue segment (for 3 * length of segment — heaviest red — heaviest blue). Thus, this problem can be solved in linear time.

Be careful about the case with no green points.

**stats**

First solve: Petr at 00:38:32

Breakdown of results for submissions that passed pretests

```
OK 246 (90.44%)
WRONG_ANSWER 24 (8.82%)
RUNTIME_ERROR 2 (0.74%)
TOTAL 272
```

**New Year and Original Order**

This is a digit dp problem. Let's try to solve the subproblem "How many ways can the i-th digit be at least j?". Let's fix j, and solve this with dp. We have a dp state dp[a][b][c] = number of ways given we've considered the first *a* digits of *X*, we need *b* more occurrences of digits at least *j*, and *c* is a boolean saying whether or not we are strictly less than *X* or not yet.

For a fixed digit, we can compute this dp table in *O*(*n*^{2}) time, and then compute the answers to our subproblem for each *i* (i.e. by varying *b* in our table).

**stats**

First solve: dotorya at 00:49:58

Breakdown of results for submissions that passed pretests

```
OK 46 (100.00%)
TOTAL 46
```

**New Year and Boolean Bridges**

First, let's find connected components using only AND edges. If there are any XOR edges between two nodes in the same component, the answer is -1.

Now, we can place all components in a line. However, it may be optimal to merge some components together. It only makes sense to merge components of size 2 or more, of which there are at most *k* = *n* / 2 of them.

We can make a new graph with these *k* components. Two components have an edge if all of the edges between them are OR edges, otherwise, there is no edge.

We want to know what is the minimum number of cliques needed to cover all the nodes in this graph. To solve this, we can precompute which subsets of nodes forms a clique and put this into some array. Then, we can use the fast walsh hadamard transform to multiply this array onto itself until the element 2^{k} - 1 is nonzero. Naively, this is *O*(2^{k} * *k*^{2}), but we can save a factor of *k* by noticing we only need to compute the last element, and we don't need to re-transform our input array at each iteration.

**stats**

First solve: dotorya at 01:49:01

Breakdown of results for submissions that passed pretests

```
OK 10 (100.00%)
TOTAL 10
```