Div2A: Kyoya and Photobooks

Solving this problem just requires us to simulate adding every character at every position at the string, and removing any duplicates. For instance, we can use a HashSet of Strings in Java to do this (a set in C++ or Python works as well).

Bonus: Prove that the number of ways is always (length of string + 1) * 25 + 1.

Example code: http://codeforces.me/contest/554/submission/11767578

Div2B: Ohana Cleans Up

For each row, there is only one set of columns we can sweep so it becomes completely clean. So, there are only n configurations of sweeping columns to look at. Checking a configuration takes O(n²) time to count the number of rows that are completely clean. There are n configurations in all, so this takes O(n³) time total.

Alternatively, another way of solving this problem is finding the maximum number of rows that are all the same.

Example code: http://codeforces.me/contest/554/submission/11767576

Div2C/Div1A: Kyoya and Colored Balls

Let f_i be the number of ways to solve the problem using only the first i colors. We want to compute f_n.

Initially, we have f₁  =  1, since we only have a single color, and balls of the same color are indistinguishable. Now, to go from f_i to f_i + 1, we note that we need to put at a ball of color i + 1 at the very end, but the other balls of color i + 1 can go anywhere in the sequence. The number of ways to arrange the balls of color i + 1 is (minus one because we need to put one ball at the very end). Using this recurrence, we can solve for f_n.

Thus, we need to precompute binomial coefficients then evaluate the product.

Example code: http://codeforces.me/contest/553/submission/11767584

Div2D/Div1B: Kyoya and Permutation

Solving this requires making the observation that only swaps between adjacent elements are allowed, and all of these swaps must be disjoint. This can be discovered by writing a brute force program, or just noticing the pattern for small n.

Here's a proof for why this is. Consider the cycle that contains n. Since n is the largest number, it must be the last cycle in the sequence, and it's the first element of the sequence. If this cycle is length 1, then we're obviously ok (we can always append (n) to the end). If the cycle is of length 2, we need n to be involved in a cycle with n - 1. Lastly, if the cycle is of length 3 or more, we will see we run into a problem. We'll only show this for a cycle of length 3 (though this argument does generalize to cycles of larger length). Let (nxy) be the cycle. So that means, n is replaced by x, x is replaced by y and y is replaced by n. So, in other words, the original permutation involving this cycle must look like

position:   ... y x n
number  :   ... n y x

However, we need it to look like (nxy) so this case is impossible.

So, once we know that n is a in a cycle of length 1 or 2, we can ignore the last 1 or 2 elements of the permutation and repeat our reasoning. Thus, the only valid cases are when we swap adjacent elements, and all swaps are disjoint. After making this observation, we can see the number of valid permutations of length n is fib(n+1). (to see this, write try writing a recurrence).

To reconstruct the kth permutation in the list, we can do this recursively as follows: If k is less than fib(n), then 1 must be the very first element, and append the kth permutation on {1,...,n-1} with 1 added everywhere. Otherwise, add 2, 1 to the very front and append the k-fib(n)th permutation on {1,...,n-2} with 2 added everywhere.

Example code: http://codeforces.me/contest/553/submission/11767583

Div2E/Div1C: Love Triangles

Let's look at the graph of characters who love each other. Each love-connected component can be collapsed into a single node, since we know that all characters in the same connected component must love each other.

Now, we claim that the resulting collapsed graph with the hate edges has a solution if and only if the resulting graph is bipartite.

To show this, suppose the graph is not bipartite. Then, there is an odd cycle. If the cycle is of length 1, it is a self edge, which clearly isn't allowed (since a node must love itself). For any odd cycle of length more than 1, let's label the nodes in the cycle a₁, a₂, a₃, ..., a_k. Then, in general, we must have a_i loves a_(i + 2), since a_i, a_(i + 1) hate each other and a_(i + 1), a_(i + 2) hate each other (all indicies taken mod k). However, we can use the fact that the cycle is odd and eventually get that a_i and a_i + 1 love each other. However, this is a contradiction, since we said they must originally hate each other.

For the other direction, suppose the graph is bipartite. Let X, Y be an arbitrary bipartition of the graph. If we let all nodes in X love each other and all nodes in Y love each other, and every edge between X and Y hate each other, then we get a solution. (details are omitted, though I can elaborate if needed).

Thus, we can see that we have a solution if and only if the graph is bipartite. So, if the graph is not bipartite, the answer is zero. Otherwise, the second part of the proof gives us a way to count. We just need to count the number of different bipartitions of the graph. It's not too hard to see that this is just simply 2^(number of connected components — 1) (once you fix a node, you fix every node connected to it).

This entire algorithm takes O(N + M) time.

Example code: http://codeforces.me/contest/553/submission/11767582

Div1D: Nudist Beach

The algorithm idea works as follows:

Start with all allowed nodes. Remove the node with the smallest ratio. Repeat. Take the best ratio over all iterations. It's only necessary to consider these subsets. Proof for why.

We say this process finds a ratio of at least p if and only if there exists a subset with ratio at least p.

Exists a subset with ratio at least p => algorithm will find answer of at least p. First, observe that the ratio of any particular node only decreases throughout the algorithm. Thus, all nodes in this subset initally have ratio at least p. Then, the very first node that gets removed from this subset must not have ratio smaller than p, thus the above algorithm will record an answer of at least p.

Exists no subset with ratio at least p => algorithm finds answer at most p. No subset with ratio at least p implies every subset has ratio at most p. Thus, at every iteration of our algorithm, we'll get an answer of at most p, so we're done.

Thus, we can see these are necessary and sufficient conditions, so we're done.

Now for efficient implementation, we can use a variant of Dijkstra's. Recording the best subset must be done a bit more carefully as well.

Example code: http://codeforces.me/contest/553/submission/11767581

Div1E: Kyoya and Train

The Naive solution is O(MT²). Let W_j(t) be the optimal expected time given we are at node j, with t time units left. Also, let W_e(t) be the optimal expected time given we use edge e at time t.

Now, we have

And, if e = (u->v), we have

Doing all this naively takes O(MT²).

Now, we'll speed this up using FFT. We'll focus on only a single edge for now. The problem here, however, is that not all W_v values are given in advance. Namely, the W_v values require us to compute the W_e values for all edges at a particular time, and vice versa. So we need some sort of fast "online" version of FFT.

We do this as follows. Let's abstract away the original problem, and let's say we're given two arrays a,b, where a is only revealed one at a time to us, and b is given up front, and we need to compute c, their convolution (in the original problem b is P_e, and a is W_v, and c is W_e). Now, when we get the ith value of a, we need to return the ith value of the convolution of c. We can only get the ith value of a when we compute the i-1th values of c for all c.

Split up b into a block of size 1, a block of size 1, then a block of size 2, then a block of size 4, then 8, and so on.

Now, we get a₀, which will allow us to compute c₁, which lets us get a₁, which allows us to compute c₂, and so on.

So, now we have the following:

b_1 | b_2 | b_3 b_4 | b_5 b_6 b_7 b_8 | ...

We'll describe the processing of a single a_i

When we get a_i, we will first convolve it with the first two blocks, and add those to the appropriate entry. Now, suppose a_i is multiple of a 2^k for some k. Then, we will convolve a_i - 2^k .. a_i - 1 with the block in b with the same size.

As an example.

      b_1 | b_2 | b_3 b_4 | b_5 b_6 b_7 b_8 | ...
a_0   a0b1  
            a0b2

This gives us c₀, which then allows us to get a₁

      b_1 | b_2 | b_3 b_4 | b_5 b_6 b_7 b_8 | ...
a_0   a0b1  a1b1
a_1         a0b2 a1b2

This gives us c₁, which then allows us to get a₂

a₂ is now a power of 2, so this step will also additionally convolve a₀, a₁ with b₃, b₄

      b_1 | b_2 | b_3      b_4    | b_5 b_6 b_7 b_8 | ...
a_0   a0b1  a1b1  a2b1
a_1         a0b2  a1b2    a2b2
a_2               a0b3 (a1b3+a0b4)  a1b4

So, we can see this gives us c₂, which then allowus to get a₃, and so on and so forth.

Thus, this process of breaking into blocks works. As for runtime, we run FFT on a block size of B T/B times, so this term contributes (T/B) * B log B = T log B

So, we sum T log 2 + T log 4 + ... + T log 2\^(log T) <= T log\^2 T

Thus, the overall time per edge is , which gives us a total runtime of .

Example code: http://codeforces.me/contest/553/submission/11767579