### ABalobanov's blog

By ABalobanov, history, 17 months ago,

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:

Announcement of Krosh Kaliningrad Contest 2

• +27

 » 14 months ago, # |   0 Auto comment: topic has been updated by ABalobanov (previous revision, new revision, compare).
 » 14 months ago, # |   0 Auto comment: topic has been updated by ABalobanov (previous revision, new revision, compare).
 » 14 months ago, # |   0 Auto comment: topic has been updated by ABalobanov (previous revision, new revision, compare).
 » 14 months ago, # |   0 Auto comment: topic has been updated by ABalobanov (previous revision, new revision, compare).
 » 14 months ago, # |   0 Auto comment: topic has been updated by ABalobanov (previous revision, new revision, compare).
 » 14 months ago, # | ← Rev. 5 →   +5 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? $O(n^3)$ solution: let's consider numbers in decreaing order, and we will accumulate our subsegment. We will count number of ways to make subsegment of length $len$ having value of this function is equal to $val$. Knowing this information it is easy to restore the answer. This will be our $dp(len, val)$ -- (amount of taken numbers to our subsegment, value). Let us start with one number: $dp(1, i) = 1$. When considering the second number, we iterate on it(let it be $j$) and go to $dp(2, i$ $mod$ $j)$. Also we can take any bigger number than $i$ without changing the $val$. What happens if we want to consider the next number? How to know which numbers have we already considered and which not? Let's consider some state (len, val). We can say that we didn't take any number less than or equal to $val$. What about numbers greater than $val$? We know than there are $n - val$ of them. Any of these numbers can be taken after last taken number without changing the $val$. And to change the $val$ we again iterate over new considered number that is less or equal than $val$. And this is the transitions! You have slightly different situation in the beggining when you did'n perform $mod$ operation, +-1 somewhere and you can handle it with flag.