### rng_58's blog

By rng_58, history, 16 months ago,

diverta 2019 Programming Contest will be held on Saturday (time). The writer is camypaper.

Contest Announcement

Contest duration: 120 minutes

Rated range: <2800

The point values will be announced later.

Let's discuss problems after the contest.

• +85

 » 16 months ago, # |   +55 The contest will be delayed by 15 minutes. We are sorry for the inconvenience.
 » 16 months ago, # |   +111 Sorry, because of the server trouble this contest will be unrated.
 » 16 months ago, # |   -28 Ok
 » 16 months ago, # |   +4 Can someone explain their solution to Problem-E. I have read the editorial but didn't get too much.
•  » » 16 months ago, # ^ |   0 Let's fix $x$ — xor of each block. So, for each $x$ we should calculate the number of ways to divide whole sequence into some number of non-empty blocks with given xor $x$. First of all, we can precompute the prefix xor-s for each $0 \le i \le n$, denote $p_i$ as the xor of all elements with index $j \le i$. Observe that dividing whole sequence into the blocks $\Leftrightarrow$ find such indexes $0 = i_1 < i_2 < \ldots < i_k = n$, that $\forall\ 1 < j \le k$ should be $p_{i_j} \oplus p_{i_{j-1}} = x$, also observe that because of $p_0 = 0$ then $p_{i_2} = x \Rightarrow p_{i_3} = 0$ etc. So we have sequence of alternating values $0$-s and $x$-s. Let's store all indexe's $i$, such that $p_i = x$ in array $b$, so $p_{b_i} = x$. We can calculate $dp_i$ — the number of sequences, such that finish in $b_i$. So, transition can be explained in the following way: $dp_i = \sum\limits_{i=1}^{i - 1}dp_j\cdot cnt_0[b_j, b_i]$, where $cnt_0[b_i, b_j]$ — the number of $t \in [b_i, b_j]$, such that $p_t = 0$. Such $dp$ can be calculated in $O(k)$. After that if $p_n = x$ then we should add $dp_k$ to the answer, otherwise we should add $\sum\limits_{i=1}^{k}dp_i$.
•  » » » 16 months ago, # ^ |   0 Thanks for answering this!! Could you please elaborate on the point of alternate 0's and x's.
•  » » » » 16 months ago, # ^ |   0 Every correct dividing is equal to the sequence of $p_i$ like $0,X,0, \ldots,$
•  » » » » » 16 months ago, # ^ |   0 Thanks Got this one. But there could be 2^20 different xors possible, so how we gonna iterate over that and moreover if you could explain your dp recurrence again that would be very helpful.
•  » » » » » » 16 months ago, # ^ |   0 Firstly, if we denote $c_x$ as the number of $p_i$'s, such that $p_i = x$ then $\sum\limits_{0}^{2^{20}-1}c_x = n \Rightarrow$ whole solution works in $O(n)$. Secondly, to understand such $dp$ you can try solve this problem, when all $p_i = 0$ or $p_i = x$.
 » 16 months ago, # |   0 Problem F. In the following statement from editorial: "When we recieves a white ball, the state changes to $(n + 1, b,(n + 1)c,(n + 2)s)$", why the sum from s goes to $(n + 2)s$?
•  » » 16 months ago, # ^ |   +28 I have realized. We can express $s$ as sum over all black balls and position $i$ multiplied by the number of sequences, such that given black ball located at the position $i$. Denote that the number of such sequences is $c \Rightarrow s = \sum\limits ic$, so if we add one more white ball then new sum over all sequences will be $s' = \sum{c(i(n + 1 - i) + i(i + 1))} = \sum{ci(n + 2))} = s(n + 2)$, because if we put new white ball on the right side of out black ball (there are $n + 1 - i$ ways to do that) than black ball will add $i$ to the global sum, on the other hand, if we put a new white ball on the left side of our black ball (there are $i$ ways), then black ball will add $(i + 1)$ to the global sum.
•  » » » 16 months ago, # ^ |   0 Please, can someone provide links with good explanation of fast z transform?
•  » » » » 16 months ago, # ^ |   +18
•  » » » » » 16 months ago, # ^ |   0 Thank you so much!
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 I calculated $a_i$ a different way. Let's use (N-1)-bit integers to represent subsets of the edges of the spanning tree.First, we can calculate for each edge $e_i = (u_i, v_i)$ outside of the spanning tree the (N-1)-bit integer representing the set of edges in the path from $u_i$ to $v_i$ within the spanning tree. Call it $path(e_i)$.Now, consider any subset $v$ of edges in the spanning tree. The sum of $a_i$ for all the edges in $v$ is equal to the number of edges $e_i$ such that $v \land path(e_i) \neq 0$. We can precompute all such sums in $O(2^N M)$ time. When performing the DP, individual $a_i$ can be found in $O(1)$ by taking the difference between two precomputed values.