Editorial for Canada Day Contest 2021 - 0-1
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Chapter 1
There are ways of choosing
of the
bits. Each set of
bits has a
chance of being flipped.
For Subtask 1, use dynamic programming. Let be the probability of having the string
after
moves. Use the transition
for every
generated by flipping
bits on
. Complexity:
For Subtask 2, generate a matrix where
is the chance of
becoming
in one second. Find the answer by calculating
. Complexity:
Chapter 2
Solution by
depends only on the value of
xor
. Let
be the probability going from any
to (
xor
) after
seconds. Now you've reduced
from a 2D matrix into a 1D array of length
.
You can do an xor convolution of and
to get
. Now you can find
and solve the problem with complexity
, solving Subtask 3.
To solve Subtask 4, use the Fast Walsh–Hadamard transform to speed up the xor convolutions and find the answer in .
Chapter 3
is the same for all
that share a value of
. So you can actually compress
further into an array of length
. This optimization leads to an
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 - enough to complete the problem.
Bonus: Even now you can take advantage of symmetries in the matrix for constant time improvements.
Comments