rivalq's blog

Codeforces Round #832 (Div. 2) Editorial
By rivalq, history, 2 years ago, In English

I hope you all liked the round. Please share your feedback in the comments section.

1747A — Two Groups

Hint
Tutorial
Solution

1747B — BAN BAN

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1747C — Swap Game

Hint 1
Hint 2
Tutorial
Solution

1747D — Yet another Problem

Hint 1
Hint 2
Hint 3
Tutorial
Solution

1747E — List Generation

Hint 1
Hint 2
Tutorial
Solution
  • Vote: I like it
  • -43
  • Vote: I do not like it

Comments Comments (34)
| Write comment?
»
2 years ago, # |
← Rev. 4   Vote: I like it +31 Vote: I do not like it

problem A — Good problem cause it pretty easy as a normal A problem — in some contests problem A is too hard and this's bad cause people leave the competition without any submission and don't affect the distribution of seats although they could do it.

problem B — a standard constructive problem

problem C — I really liked it, some people said that it was an ad-hoc problem maybe it was really so but I found a small pretty proof at the contest so this problem wasn't ad-hoc for me.

problem D — Nice Div2D, not too easy, not too hard, I liked solving it at the contest.

problem E — Very hard problem, didn't solve it. But when there are only five problems in a contest a hard E is a normal and even necessary thing

Generally — A very good contest without any explicit mistakes, I liked it, thanks !

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C is easier than i expected :))

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

For D, I think this part is wrong: "So necessary conditions for answer to exist is that xor of array should be 0 and S1 should contains 0"

It should be "S0 should contain 0", because S1 can only contain odd XORs right?

Edit: Nevermind, I understand now. S1 doesn't mean the set of odd prefix XORs, S1 rather means the set of prefix XORs at the odd indices of the array.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How do we know this part is true for D?

"There will exists some odd size prefix j such that xor of its elements is 0."

Edit: Nevermind, I understand now.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Could you tell me how?

    Edit: Nevermind, I understand now too.

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

      Could you explain how?

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        This case happens only in the even subarrays.

        That means it will not matter if we begin from the right or the left because if we have an odd prefix whose xor equals 0, the remaining suffix is odd and its xor equals 0 as well. So it is the same thing if we find an odd prefix or an odd suffix.

        We will work on suffixes here

        Now suppose you have a subarray $$$X$$$ that consists of the subarrays $$$A$$$ and $$$B$$$ respectively.

        here the subarray $$$X$$$ is always a prefix of the whole array

        It's clear that $$$xor(X)$$$ equals $$$xor(A) \oplus xor(B)$$$, where $$$xor(y)$$$ equals the xor of all elements in y.

        Now suppose again that $$$xor(B)$$$ equals 0.

        $$$xor(X) = xor(A) \oplus xor(B) = xor(A) \oplus 0 = xor(A)$$$

        That's it

        we need to find the prefix array $A$ that has a cumulative xor equals to the xor of the whole subarray $$$X$$$

        You know that $$$xor(A)$$$ equals the cumulative xor of the last element of $$$A$$$. So this is our test, at every element we will check if there is a relative odd index to it that has the same cumulative xor. and we will get the last one because if it one holds, then all the right element of it holds but not vice versa. Note that we can change the beginning of the subarray at each query.

        we can store the last occurrences of all cumulative xors in a map. We will need to store evens and odds separately to check the relative odd distance

        That's all

        → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

"Let S0, S1 be sets of prefix XOR's of parities 0 and 1 respectively. After each operation new sets S′0, S′1 will be subsets of S0 and S1 respectively." Can you explain this part please? If I understood it correctly: suppose you have array $$$[1,2,1]$$$, then prefix xor are $$$[1,3,0]$$$, so the two sets $$$S_0, S_1$$$ are $$$[1,0]$$$ and $$$[3]$$$.

Now operate on the whole array to get $$$[2,2,2]$$$, and now the prefix xor are $$$[2,0,2]$$$, then clearly the $$$S_0',S_1'$$$ are not subset of $$$S_0,S_1$$$. Did I understand it wrongly?

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

    Initial Prefix Xor array is $$$[0,1,3,2]$$$.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why am I getting tle in D for exact same complexity. 179934064

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

tutorial for E pls

upd. thank you!

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it +31 Vote: I do not like it

Solution for 1747E - List Generation:

For a good pair $$$a, b$$$ define the following $$$s$$$ array. For each $$$i$$$ from $$$2$$$ to $$$k$$$ append $$$a_i-a_{i-1}$$$ zero, then $$$b_i-b_{i-1}$$$ one, and a two to the end of $$$s$$$.

For example: $$$a=[0, 3, 4]$$$ and $$$b=[0, 2, 2]$$$, than $$$s=[0, 0, 0, 1, 1, 2, 0, 2]$$$. What do we know about $$$s$$$? It starts with $$$0$$$ or with $$$1$$$, it ends with $$$2$$$ and there is no $$$[1, 0]$$$ and $$$[2, 2]$$$ substring.

Obviously $$$|s|=|a|+n+m-1$$$.

If we fix the relative order of the $$$0$$$ and $$$1$$$ elements in $$$s$$$ ($$$s'$$$ array), than there are some $$$x$$$ positions where we must insert a $$$2$$$. (between the $$$[1, 0]$$$ parts). For the remaining $$$n+m-1-x$$$ positions we may insert a $$$2$$$ anywhere.

For example: $$$s'=[0, 0, 0, 1, 1, 0]$$$. We must insert a $$$2$$$ after the second $$$1$$$. And there are $$$4$$$ optional places.

So there are $$$2^{n+m-1-x}$$$ options, and $$$|s|=2+x+\frac{n+m-1-x}{2}$$$ on average. It is easy to calculate this in constant time.

The remaining part: how can we find the number of $$$s'$$$ arrays for a fixed $$$x$$$? If we fix the the ones, than there are $$$\frac{m!}{x! \cdot (m-x)!}$$$ options for the position of the zeroes, and we can place them in $$$\frac{n!}{x! \cdot (n-x)!}$$$ ways (some standard combinatorial problem).

So the final answer is $$$\sum_{x=0}^{m} binom_{m, x} \cdot binom_{n, x} \cdot (2+x+\frac{n+m-1-x}{2}) \cdot 2^{(n+m-1-x)}$$$

After the precalculation everything is linear.

Here is my solution: 180108716.

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

    Nice!, I never looked at this was, but it is similar to my solution.

    Can you solve for multiple dimensions?, such that sum over all dimensions is less than or equal to $$$10^5$$$.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, if $$$S_1$$$ doesn't contain $$$0$$$ and a[1] != 0, you can't convert a[1] to $$$0$$$.
With the condition: $$$S_1$$$ contains $$$0$$$ and the whole xor == $$$0$$$, you can construct a method to convert all elements to $$$0$$$, so the 2 conditions is enough. Am I right?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the editorial of problem E, if you jump to $$$(x,0)$$$ in your first move, does $$$(0,0)$$$ count as a breakpoint?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder whether the time limit of E is too strict?My friend and I were traped due to it,both writing linear solution.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

Solve E with generating functions (maybe without clever ideas?)

How many ways if we jump exactly $$$k$$$ times? $$$[x^ny^m](\frac{1}{(1-x)(1-y)}-1)^k$$$

So the answer is $$$Ans=[x^ny^m]\sum\limits_{k\geq 1} (\frac{1}{(1-x)(1-y)}-1)^k(k+1)$$$

As $$$\sum\limits_{k\geq 1}A^k(k+1)=(\sum\limits_{k\geq 1}A^{k+1})'=(\frac{1}{1-A}-1-A)'=(1-A)^{-2}-1$$$

So $$$Ans=[x^ny^m](2-\frac{1}{(1-x)(1-y)})^{-2}=[x^n y^m] {(1-x)}^2 (1-y)^2(1-2(x+y-xy))^{-2}$$$

Let

$$$\begin{aligned} f(n,m) &=[x^n y^m](1-2(x+y-xy))^{-2}\\ & = \sum\limits_{k\geq 0}\binom{-2}{k}{(-2)}^k[x^ny^m]{(x+y-xy)}^k\\ & = \sum\limits_{k\geq 0}(k+1){2}^k\binom{k}{n+m-k,k-n,k-m}(-1)^{n+m-k}\\ \end{aligned}$$$

We can calculate $$$f(n,m)$$$ in $$$O(n+m)$$$

Then $$$Ans=f(n,m)-2*f(n-1,m)-2*f(n,m-1)+4*f(n-1,m-1)+f(n-2,m-2)+f(n-2,m)+f(n,m-2)-2*f(n-2,m-1)-2*f(n-1,m-2)$$$

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution shows that in test 3 there are no preXORS in the array with similar value. Is it wrong? My solution is https://codeforces.net/contest/1747/submission/180203710.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem E hint 2 you haven't closed bracket

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, how to prove that if these conditions are not satisfied then answer doesn't exists

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

    If you admit the claim "S1 will always decrease", then if at the beginning there is no odd prefix with xor 0, then no matter how many operations you do, S1 will never contain 0, which means the entire subarray will never become 0.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are the constraints for E intended to make solutions with FFT not pass?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, I don't really understand why "S1 and S2 always decrease" unless I try some quite complicated case analysis. Could someone give a better way to see this?

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Can someone explain problem E in greater detail please? The tutorial has skipped so many steps, and poorly explained the most important part — what breakpoints are. "When we passes the breakpoint we turns right." What does this mean and and how are they defined? Why will the paths be grouped after that? Will apprecite any replies :)

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Jai Shree Ram — OP

→ Reply