diverta 2019 Programming Contest will be held on Saturday (time). The writer is camypaper.
Contest duration: 120 minutes
Rated range: <2800
The point values will be announced later.
Let's discuss problems after the contest.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
diverta 2019 Programming Contest will be held on Saturday (time). The writer is camypaper.
Contest duration: 120 minutes
Rated range: <2800
The point values will be announced later.
Let's discuss problems after the contest.
Name |
---|
The contest will be delayed by 15 minutes. We are sorry for the inconvenience.
Sorry, because of the server trouble this contest will be unrated.
Ok
Can someone explain their solution to Problem-E. I have read the editorial but didn't get too much.
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$$$.
Thanks for answering this!! Could you please elaborate on the point of alternate 0's and x's.
Every correct dividing is equal to the sequence of $$$p_i$$$ like $$$0,X,0, \ldots,$$$
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.
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$$$.
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$$$?
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.
Please, can someone provide links with good explanation of fast z transform?
https://cp-algorithms.com/algebra/polynomial.html#toc-tgt-13
Thank you so much!
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.