Editorial for Canada Day Contest 2021 - 0-1

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Aaeria

Chapter 1

There are \binom n x = \frac{n!}{x!(n-x)!} ways of choosing x of the n bits. Each set of x bits has a \frac{x!(n-x)!}{n!} chance of being flipped.

For Subtask 1, use dynamic programming. Let dp[i][s] be the probability of having the string s after i moves. Use the transition dp[i][s]=\sum \frac{x!(n-x)!}{n!} dp[i-1][s'] for every s' generated by flipping x bits on s. Complexity: \mathcal O((2^n)^2 K)

For Subtask 2, generate a matrix p where p[s][t] is the chance of s becoming t in one second. Find the answer by calculating p^K. Complexity: \mathcal O((2^n)^3 \log K)

Chapter 2

Solution by arvindr9

p[s][t] depends only on the value of s xor t. Let p_i[x] be the probability going from any s to (s xor x) after i seconds. Now you've reduced p from a 2D matrix into a 1D array of length 2^n.

You can do an xor convolution of p_a and p_b to get p_{a+b}. Now you can find p_K and solve the problem with complexity \mathcal O((2^n)^2 \log K), solving Subtask 3.

To solve Subtask 4, use the Fast Walsh–Hadamard transform to speed up the xor convolutions and find the answer in \mathcal O(2^n n \log K).

Chapter 3

p[s] is the same for all s that share a value of \operatorname{popcount}(s). So you can actually compress p further into an array of length n. This optimization leads to an \mathcal O(n^2 K) DP solution which alone is enough to solve subtasks 1-3.

Next, you'll need to return to the matrix technique from subtask 2. But this time, you have an algorithm with a complexity of \mathcal O(n^3 \log K) - enough to complete the problem.

Bonus: Even now you can take advantage of symmetries in the matrix for constant time improvements.


There are no comments at the moment.