Hi everyone! There is another bunch of problems I used in some programming school and want to share so here is Krosh Kaliningrad Contest 2 in gyms which starts Dec/04/2021 14:00 (Moscow time). Everyone is welcome. I suppose problem difficulty level is from cyan to orange though there will be harder problems. Duration of contest is 3 hours.

Upd: reminder: contest starts in 2 hours. Upd: contest starts in 8 minutes. Good luck!

Thanks everyone for participation! Congratulation to the winners:

Auto comment: topic has been updated by ABalobanov (previous revision, new revision, compare).Auto comment: topic has been updated by ABalobanov (previous revision, new revision, compare).Auto comment: topic has been updated by ABalobanov (previous revision, new revision, compare).Auto comment: topic has been updated by ABalobanov (previous revision, new revision, compare).Auto comment: topic has been updated by ABalobanov (previous revision, new revision, compare).EditorialA...

BCalculate the coefficient of $$$a_i$$$. It is number of ways to choose $$$k$$$ left brackets from the first $$$i$$$ positions * number of ways to choose $$$k$$$ right brackets from last $$$n - i$$$ positions. It is number of combitation with repetitions.

CBinary search on first non zero element which can be maximum. Denote $$$1$$$ is good position where $$$a_i \le x$$$ and $$$0$$$ otherwise where $$$x$$$ is some chosen maximum. Then you get some blocks each pair of adjacent blocks is divided by zero. Answer for block of size $$$k$$$ is $$$F_k$$$ -- Fibonacci number and the answer for this maximum is product of these numbers over all the blocks. Iterate on the maximum $$$x$$$ to calculate amount of ways to reach finish visiting only good positions. When increasing maximum you should merge some blocks and recalculate the answer. I used segment tree for this because modulo is not prime and you can not divide. Another approach is to use segment tree from the beggining also with increasing the maximum storing for each node some sort of dp value(where ends are on or out).

ELet $$$n = a_1 + a_2 + ... + a_k$$$.

Let $$$a_1 = x_1$$$ where $$$x_1 > 0$$$.

Let $$$a_2 = 2 * x_1 + x_2$$$ where $$$x_2 >= 0$$$.

Let $$$a_3 = 4 * x_1 + 2 * x_2 + x_3$$$ where $$$x_3 >= 0$$$.

... Let $$$a_k = 2^{k - 1} * x_1 + 2^{k - 2} * x_2 + ... + x_{k}$$$ where $$$x_{k - 1} >= 0$$$.

So $$$n = c_1 * x_1 + c_2 * x_2 + ... + c_k * x_k$$$ where $$$c_i = 2^i - 1$$$(reverse the order of summands for simplicity).

Notice that $$$k$$$ is $$$O(log n)$$$. Then you can write $$$dp(restsum, index of summand)$$$.

FBrief idea: $$$dp(a, b) = \sum_{n = 1}^{infty} C_n^a * C_n^b / 2^n$$$. Write down $$$C$$$ through Paskal's triangle to obtain dp formula. To get linear solution notice that this formula is almost actually number of ways to reach cell $$$(0, 0)$$$ from the cell $$$(a, b)$$$ if you can go left, up and left-up by diagonal.

GEditorial will appear slightly later. By the way how fast you can solve it? I think i have solution in $$$O(n^2 \sqrt{n})$$$. Is it possible to solve it better?