Editorial for DMOPC '19 Contest 1 P6 - Bob and Binary Strings
Submitting an official solution before solving the problem yourself is a bannable offence.
For subtask 1, it suffices to iterate over all pairs of binary strings of length and check if they are similar. Suppose the recursive function for checking similarity has complexity for comparing two strings of length . If we directly implement the procedure described in the problem statement, we get
For subtask 2, observe that if is odd, then the only way for two binary strings to be similar is if they are equal. Since each binary string can only be paired with itself, this gives a total of pairs. Since is quite large, we must use repeated squaring to calculate .
For subtask 3, we must form the crucial observation that the strings can be split into several equivalence classes. If some string is similar to , and string is similar to , then we can show that is also similar to . Therefore, all strings belonging to the same class are similar and strings belonging to different equivalence classes aren't similar. For each equivalence class, we can define the lexicographically smallest possible string that is reachable from every element in said class as the representative of the class. Now, it is a matter of assigning all strings to the corresponding class. This can be done by recursively minimizing the left and right halves and then minimizing the concatenation of the minimized left and right halves (i.e. if the left half is larger than the right half, swap them). Our recursive procedure now has complexity,
For subtask 4, we will speed up the procedure described in subtask 3. Suppose (if is odd we can use the algorithm for subtask 2). Instead of generating the equivalence classes for , we will do it instead for . In the recursive procedure, notice that the classes for will be generated by pairing up the classes for on the left with the classes for on the right. So we can consider a list, , which is the sizes of the equivalence classes for . Notice that when we multiply by where , we obtain the size of an equivalence class for . Be careful that when we must add this number to the resulting class when and are swapped instead of creating a new class. If we square the terms and modify this procedure slightly, we will get the sum of the squares of the equivalence classes for without actually generating the terms.
Consider pairing two terms and where . The equivalence class they form has size and the square of the size would be . Since they will be multiplied twice by the procedure, we must multiply their product again by in order to get the square of the resulting size to be correct.
We will generalize approach 1. Suppose . We will first generate the classes for . However, since must be odd, there are just groups of size 1. By using the explicit procedure we will generate the terms for . Since the size of the list squares itself each iteration, the first iterations will use up negligible time compared to the last iteration. Once again, we can use the implicit generation method to get the answer for without generating the actual terms.
For subtask 5, we observe that there are many duplicated group sizes and that the order of the groups doesn't actually matter. Therefore, we will store the number of groups of size instead of explicitly storing the groups. This works well if you observe that the sizes of the equivalence classes must be a power of 2. If all the terms going into a doubling operation are powers of two, then all resulting terms will also be powers of two since they must be a product of two input terms or two input terms multiplied by . With this form, note that the doubling operation we used in the previous subtask is similar to a convolution of this array. As with approach 2 from the previous subtask, if we will start with the representation of the classes of and double the representation until we get to . The representation doubles in size with each iteration and performing one iteration takes where is the size of the representation at the current iteration. Once again, the first iterations contribute very little to the complexity which gives per query.
For subtask 6, we will try to find a way of directly generating the answer instead of storing the number of each term as this will quickly become unmanageable. Observe that the final form we seek is the sum of the squares of the sizes of the equivalence classes for . Let be the sums of -th powers of the sizes of the groups for so the sum of squares for is just . The sum of squares of the sizes for is close to but we overcount. How much do we overcount by? Notice that we are overcounting the terms that are being multiplied by themselves so we should subtract times this sum. Suppose we call the sum of fourth powers of the classes of , . Then we have . The interesting thing is that this works exactly the same for higher powers so we have the general formula . The coefficients can be found in the same way as approach 1 in subtask 4.
Therefore, our algorithm becomes as follows: suppose . We start the procedure at where we know that since the sum of arbitrary powers of groups of s is always . We then repeat this procedure to generate the results for . Note that at iteration , we cannot generate since we don't have . But, if we start by generating for then we will have enough terms to generate which is the answer.