Try to log out from yandex contest and login back

We are asked to calculate the probabilities of choosing a sequence $$$q$$$ so that its $$$d$$$-th order statistic is $$$>$$$ than $$$k$$$. Let's calculate the probabilities of choosing a sequence $$$q$$$ so that its $$$d$$$-th order statistic is $$$\leq$$$ than $$$k$$$ instead, that means that there are at least $$$d$$$ integers which are $$$\leq k$$$ in $$$q$$$. We fix a position $$$i$$$ ($$$0$$$-indexation) of exactly $$$d$$$-th one from the left, then the probability is $$$\binom{i}{d - 1} \cdot (\frac{k}{n})^{d} \cdot (\frac{n - k}{n})^{i - d + 1}$$$ and it affects answers in the segment $$$[i; n]$$$ of lengths of $$$q$$$.

J — lets calc two functions: f(x), s(x) — f(x) is a number of different towers with x blocks, and s(x) is a number of symmetric towers with x blocks, that all floors are correct. There are easy reccurent formula: f(x) = f(x-1) + 3*f(x-2) + f(x-3), because we see to 1st floor, there is 5 options — 010, 110, 011, 101, 111.

And for s(x) we can use only 010, 101, 111. so s(x) = s(x-1)+s(x-2)+s(x-3)

OK, so answer for task will be ((f(n)+s(n))//2)+f(n-1). If the last floor is correct, it means that we have ((f(n)+s(n))//2, because non-simmetric towers was calculated in f two times. And if the last floor is incorecct, there is only 2 options — 100, 001. It means, that tower is non-simmetric, and variables for other floors is f(x-1). SO answer is ((f(n)+s(n))//2+f(n-1)

A: If we are using only the swap move, the answer only depends on the number of cycles in the permutation — if there are $$$c$$$ cycles, the answer is $$$a * (n - c)$$$. However, there is also a possibility that we do the random_shuffle move, where we get to a permutation with $$$c'$$$ cycles with $$$p(c')$$$ probability, where $$$p(c')$$$ can be easily calculated (look up Sterling numbers of the first kind). So, if $$$e(c)$$$ is a solution for the permutation of $$$c$$$ cycles, following equality must hold for each $$$c$$$: $$$e(c) = \min(a * (n - c), b + \sum_{i = 1}^{n} p(i) * e(i)) $$$. We can start with any random solution and iterate this until it converges (it will converge fast, trust me).

$$$G$$$. When $$$nm$$$ — 1 is not divisible by 4, answer is obviously no. Otherwise, both $$$n$$$ and $$$m$$$ are odd and equal modulo 4. Cases where $$$n$$$ = 1 or $$$m$$$ = 1 are trivial. For $$$n$$$ = $$$m$$$ = 3 it is easy to construct answer on paper, and because of this one can prove that answer always exists in this case. So let's do the following process: while we can cut top 4 rows (but not getting 1xM strip), cut them. Do same for bottom, left and right. So, now we have small field (up to 7x7). To solve this you can write recursion, that will consider all possible cases. To do this, our team hardcoded ~20 figures and their rotations, but maybe there is easier approach to do this.

D: The problem is basically about solving the system of linear equations $$$x^TA = (a_0)^T$$$ in $$$F_2$$$, where $$$A$$$ is constructed by stacking the binary representations of $$$a_1, a_2, \ldots, a_n$$$ vertically. $$$x$$$ can be found by computing $$$A^{-1}$$$ in $$$O(\frac{n^3}{64})$$$ with std::bitset. The modification of $$$a_p$$$ can be modeled as adding some $$$u$$$ to the $$$p$$$-th row of $$$A$$$, and the inverse of the modified matrix can be found, according to Sherman–Morrison formula, with some multiplications between matrices and vectors in $$$O(\frac{n^2}{64})$$$ time. The overall time complexity is $$$O(\frac{n^3+n^2m}{64})$$$.

G. Geometric shapes

During the contest I got accepted using the same awful(because of implementation) ideas, that were written higher, but found a nice way to solve it after.

Firstly we should fill first $$$n-1$$$ rows and $$$m-1$$$ columns with squares and everything else(except for cell $$${0, m - 1}$$$) with sticks and corners.

Let's think that $$$r \leq \frac{n}{2}$$$ and $$$c \leq \frac{m}{2}$$$ because other cases are simmetrical.

The last step is just consistently swap cells using one of two ways(choice depends on $$$c$$$ $$$mod$$$ $$$2$$$)

It's easy to check that all figures stay being tetraminos after all moves.

I believe that E can be solved with four scanlines (vertical, horizontal, two diagonal ones) and simple combinatorics, but during contest we thought that this is next to impossible to implement.

K: Let's fix the highest non-zero bit of $$$x$$$ at position $$$p$$$, then we can see that whether $$$a_i \oplus x$$$ is greater than $$$a_i$$$ is uniquely determined by the $$$p$$$-th bit of $$$a_i$$$. Therefore, we can calculate the contributions of each bit $$$j < p$$$ and mark the $$$k - 1$$$ largest bits (according to their contributions) in $$$x$$$ to be 1. With the enumeration of $$$p$$$, the time complexity is $$$O(m^2n)$$$.