Блог пользователя rng_58

Автор rng_58, история, 7 лет назад, По-английски

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
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +55 Проголосовать: не нравится

The contest will be delayed by 15 minutes. We are sorry for the inconvenience.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +111 Проголосовать: не нравится

Sorry, because of the server trouble this contest will be unrated.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится -28 Проголосовать: не нравится

Ok

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Can someone explain their solution to Problem-E. I have read the editorial but didn't get too much.

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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 \lt i_2 \lt \ldots \lt i_k = n$$$, that $$$\forall\ 1 \lt 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$$$.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 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$$$?

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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.