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.com/contest/554/submission/11767578
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(n2) time to count the number of rows that are completely clean. There are n configurations in all, so this takes O(n3) 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.com/contest/554/submission/11767576
Let fi be the number of ways to solve the problem using only the first i colors. We want to compute fn.
Initially, we have f1 = 1, since we only have a single color, and balls of the same color are indistinguishable. Now, to go from fi to fi + 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 fn.
Thus, we need to precompute binomial coefficients then evaluate the product.
Example code: http://codeforces.com/contest/553/submission/11767584
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.com/contest/553/submission/11767583
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 a1, a2, a3, ..., ak. Then, in general, we must have ai loves a(i + 2), since ai, 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 ai and ai + 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.com/contest/553/submission/11767582
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.com/contest/553/submission/11767581
The Naive solution is O(MT2). Let Wj(t) be the optimal expected time given we are at node j, with t time units left. Also, let We(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(MT2).
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 Wv values are given in advance. Namely, the Wv values require us to compute the We 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 Pe, and a is Wv, and c is We). 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 a0, which will allow us to compute c1, which lets us get a1, which allows us to compute c2, 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 ai
When we get ai, we will first convolve it with the first two blocks, and add those to the appropriate entry. Now, suppose ai is multiple of a 2k for some k. Then, we will convolve ai - 2k .. ai - 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 c0, which then allows us to get a1
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 c1, which then allows us to get a2
a2 is now a power of 2, so this step will also additionally convolve a0, a1 with b3, b4
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 c2, which then allowus to get a3, 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.com/contest/553/submission/11767579