rng_58's blog

By rng_58, history, 6 years ago, In English

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.

  • Vote: I like it
  • +85
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +55 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +111 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -28 Vote: I do not like it

Ok

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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$$$.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for answering this!! Could you please elaborate on the point of alternate 0's and x's.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Every correct dividing is equal to the sequence of $$$p_i$$$ like $$$0,X,0, \ldots,$$$

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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$$$.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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$$$?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please, can someone provide links with good explanation of fast z transform?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +18 Vote: I do not like it
      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.