### rivalq's blog

By rivalq, history, 18 months ago,

Hint
Tutorial
Solution

Hint 1
Hint 2
Hint 3
Tutorial
Solution

Hint 1
Hint 2
Tutorial
Solution

Hint 1
Hint 2
Hint 3
Tutorial
Solution

# 1747E — List Generation

Hint 1
Hint 2
Tutorial
Solution
• -43

| Write comment?
 » 18 months ago, # | ← Rev. 4 →   +31 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 problemproblem 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 thingGenerally — A very good contest without any explicit mistakes, I liked it, thanks !
 » 18 months ago, # |   0 Problem C is easier than i expected :))
 » 18 months ago, # | ← Rev. 3 →   0 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.
 » 18 months ago, # | ← Rev. 2 →   0 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.
•  » » 18 months ago, # ^ | ← Rev. 3 →   0 Could you tell me how?Edit: Nevermind, I understand now too.
•  » » » 18 months ago, # ^ |   0 Could you explain how?
• »
»
»
»
18 months ago, # ^ |
Rev. 5   0

### 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

•  » » » » » 17 months ago, # ^ | ← Rev. 2 →   +1 I tried almost the same implementation. Can't understand what went wrong. https://pastebin.ubuntu.com/p/7p59QPh59D/ update: Got it.
 » 18 months ago, # | ← Rev. 2 →   0 "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?
•  » » 18 months ago, # ^ |   0 Initial Prefix Xor array is $[0,1,3,2]$.
 » 18 months ago, # |   0 why am I getting tle in D for exact same complexity. 179934064
•  » » 18 months ago, # ^ |   0 Same did you find a solution to it?
•  » » » 18 months ago, # ^ |   0 No, even after copying the code given in the tutorial it's giving TLE XD 179938608
•  » » » » 18 months ago, # ^ |   +1 use fast input output you phool 179948078
•  » » » » » 18 months ago, # ^ |   0 yeah just read about it, didn't know before
 » 18 months ago, # | ← Rev. 2 →   +20 tutorial for E plsupd. thank you!
•  » » 18 months ago, # ^ |   -7 Sorry for delay!
 » 18 months ago, # | ← Rev. 3 →   +31 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.
•  » » 18 months ago, # ^ |   0 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$.
 » 18 months ago, # |   0 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?
 » 18 months ago, # |   0 In the editorial of problem E, if you jump to $(x,0)$ in your first move, does $(0,0)$ count as a breakpoint?
 » 18 months ago, # |   0 I wonder whether the time limit of E is too strict?My friend and I were traped due to it,both writing linear solution.
 » 18 months ago, # | ← Rev. 2 →   +22 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)$
 » 18 months ago, # |   0 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.com/contest/1747/submission/180203710.
•  » » 18 months ago, # ^ |   0 Pls help, if you don't understand my solution, i can explain it to you, i just don't know what's wrong with it.
•  » » 18 months ago, # ^ |   0 Take a look at Ticket 16424 from CF Stress for a counter example.
•  » » » 18 months ago, # ^ |   0 thank you, mate
 » 18 months ago, # |   0 For problem E hint 2 you haven't closed bracket
 » 18 months ago, # |   0 In problem D, how to prove that if these conditions are not satisfied then answer doesn't exists
•  » » 18 months ago, # ^ |   0 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.
 » 18 months ago, # |   0 Are the constraints for E intended to make solutions with FFT not pass?
 » 18 months ago, # |   0 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?
 » 18 months ago, # | ← Rev. 2 →   +18 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 :)
 » 9 months ago, # |   0 Problem B :- Why it's Wrong ??import java.util.Scanner;public class BANBAN { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tt = sc.nextInt(); while(tt-->0){ int n = sc.nextInt(); String s = "BAN".repeat(n); int count=0; if(n%3==0){ count= (n/3)*2; System.out.println(count); } else{ count=((n/3)*2)+1; } System.out.println(count); `int i=1 , j=n*3; //boolean bi=false , bj=false; while(i
 » 11 days ago, # |   0 Jai Shree Ram — OP