КУ

Да

А также что делать, если финал респы 29 марта (после регистрации)

Нет, речь о белорусской республиканской олимпиаде. Всех остальных приглашаем участвовать в отборах.

Kodaline — Follow Your Fire и Feel the Fire — Pluko&Pronouncedyea

нет, не уходи из эфира

Try to log out from yandex contest and login back

Let's look at the cycles of the permutation. We can do swaps (first operation) in each cycle independently. For a cycle of length L we need L — 1 swaps. So for the permutation of length N with K cycles we need N — K swaps, and the cost will be A * (N — K). So only number of cycles matters.

Number of permutations of length N with K cycles is Stirling numbers of the first kind, you can precalc this with DP.

Now about our operations. Hypothesis is that you never do swaps (first operations) and then shuffle (second operation), because swaps would be useless then. So you either do only swaps, or do shuffle first.

We can assume that for permutations with many cycles we do only swaps. Let's say that for permutations with at least X (for some X) cycles we do only swaps – it's easy to find cost for them. For permutations with < X cycles we do shuffle until we get permutation with >= X cycles, and you can find excepted cost here with simple equation.

Let's find how many cycles input permutation has, then let's try all possible X values and take the minimum answer.

Code.

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)$$$.