### Monogon's blog

By Monogon, history, 13 months ago, I hope you enjoyed the contest!

1615A - Closing The Gap

Author: PurpleCrayon

Tutorial

1615B - And It's Non-Zero

Author: PurpleCrayon

Tutorial

1615C - Menorah

Author: Monogon

Tutorial

1615D - X(or)-mas Tree

Author: PurpleCrayon

Tutorial

1615E - Purple Crayon

Author: PurpleCrayon

Tutorial

1615F - LEGOndary Grandmaster

Author: PurpleCrayon

Tutorial

Author: BledDest

Tutorial

1615H - Reindeer Games

Author: Monogon

Tutorial Tutorial of Codeforces Global Round 18 Comments (105)
| Write comment?
 » As someone who got WA pretest 8, was G doable with flows?
•  » » By making a test case like $(a_i$ $0$ $0$ $b_i$ $n)$ repeated $m$ times the answer is quite clearly $m+($size of maximum matching where edges are $a_i-b_i)$, so unless you can solve maximum matching with flows the answer is no.
 »
 » I solved upto E in the contest and have ready code for F to submit now lol. Amazing problems.
 » How to solve problem b for l and r less than equal to 10^9.
•  » » Maths
•  » » solve by doing pre-computation... and in this precomputation use prefix sum method to store no. of zeros bitwise ... so at the end you can get answer of each testcase in o(1) time
•  » » » This works only for l, r <= 2 * 10^5 no ? Correct me if i'm wrong.
•  » » » » Yes Bcoz test case is up to 10^4
•  » » » » » But ... "How to solve problem b for l and r less than equal to 10^9."
•  » » » » » » Do you literally think , Test case<= 10^4 And then l and r <= 10^9 Will this work bro?
•  » » » » » » » Correct me if I'm wrong, but you said : solve by doing pre-computation... and in this precomputation use prefix sum method to store no. of zeros bitwise ... so at the end you can get answer of each testcase in o(1) timeHave I misinterpreted something ?
•  » » » » » » » » Then it'll work... Definately i guess... What you say according to your opinion?
•  » » » » » » » » » IMO, your algorithm works only for l,r <= 2*10^5 no ?
•  » » » » » » » » » Yes...
•  » » » » » » » » » 13 months ago, # ^ | ← Rev. 2 →   so your algorithm doesn't work for 2*10^5 <= l, r <= 10^9UPD : sorry everyone for the long conversation
•  » » » » » » we can calculate the number of set bits at jth position in [1,n] in O(log n)
•  » » » » » » » 13 months ago, # ^ | ← Rev. 2 →   Yeaa... Sigma( 2^(i-1)) ;i = pos of set bits greater than Or equal to j in n. Correct? Edit- with some modifications for the equality thing
•  » » » » » » » » count of numbers in [1,x] having jth bit set is floor(x/(2^(j+1))) + max(0,x%(2^(j+1))-2^j).
•  » » » » » » » » » Can you please explain the purpose of max() func here? Because IMO x%(2^(j+1) — 2^j) would always result in +ve number which ultimately will be the maximum.
•  » » » » » » » » » look closely i have written [x%(2^(j+1))]-2^j which can be negative
•  » » » » » » » » » Sorry, my bad!
•  » » 13 months ago, # ^ | ← Rev. 2 →   It can be easily done in O(log2(r)) HintCount No of kth set bits in L to R in O(1). (Here you go) Code#include using namespace std; #define int long long int #define double long double #define rep(i, a, b) for (int i = a; i < b; i++) #define bck(i, a, b) for (int i = a - 1; i >= b; i--) int getcount(int n, int k) { int res = (n >> (k + 1)) << k; if ((n >> k) & 1) res += n & ((1LL << k) - 1); return res; } void solve() { int l, r; cin >> l >> r; int ans = r - l + 1; rep(i, 0, 30) { int x = getcount(l, i); int y = getcount(r + 1, i); ans = min(ans, (r - l + 1) - (y - x)); } cout << ans << endl; } int32_t main() { int ttc = 1; cin >> ttc; while (ttc--) solve(); return 0; } 
•  » » » Congrats for being the Legendary Grandmaster : )
•  » » » » 13 months ago, # ^ | ← Rev. 3 →   Thanks ^-^, You too for becoming International Master. Merry Christmas Everyone :)
•  » » » O(log(r))*
•  » » » » Yeah sorry! It is of O(log2(r)).
•  » » » Can you explain how your code for finding total numbers having Kth bit set is working
•  » » » What is the logic for count function?
•  » » » » You may find hereHope it helps :)
•  » » » Bro, I did not understand how does your getcount function work. Could you please explain how does it work?
•  » » » » For all the bits greater than kth bit, he shifted them right by 1 , and deleted all the smaller bits. Second expression is to add more stuff if kth bit itself is set in n.
•  » » » Can you please explain why you used l and r+1 in calculating x and y? I think it should be l-1 and r+1, but got WA using this.
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   Actually, this getcount(int N, int K) function returns the no of Kth set bits in [1, N-1]. So we have to give arguments getcount(N + 1, K) to get no of Kth set bits in [1, N]. You may find clear explanation hereSo to get the no of Kth set bits in [L, R] we can have x = getcount(L, K) that gives No of Kth set bits in [1, L-1] and y = getcount(R + 1, K) that gives No of Kth set bits in [1, R]so by substracting x from y we can get no of Kth set bits in [L, R].Hope you got it :)
•  » »
•  » »
 » 13 months ago, # | ← Rev. 5 →   Hey! I actually found some different solution for problem C and I guess it's supposed to work? I started with the same observation than the editorial: we will consider the count of different types of candles.The four types are: $10, 00, 01, 11$We can apply operations on types: $10$ and $11$ because these types are the only ones having the candle of string $a$ setted to $1$ (and we can only to operations on $1$ candles)Now, what will happen if we apply an operation on a char of type $10$ ? Let's call $[a_ib_i]_{old}$ the count of the type $a_ib_i$ before the operation and $[a_ib_i]_{new}$ the count of the type $a_ib_i$ after the operation.So if we apply an operation on a char of type $10$ we'll have:$_{new} = 1 + _{old}$$_{new} = _{old}$$_{new} = _{old}$$_{new} = _{old} - 1$In a similar way we can find how $[a_ib_i]$ will change if make an operation on a char of type $11$.Furthermore, doing the same operation twice is useless as we will comeback to the same string.As an operation only do a small local change (+/- 1) and let two counts invariant (it just swaps them) we may think there is not that much reachable strings.So one could implement a BFS where the nodes contains the count of each type and the transitions are: apply operation on $10$ or apply operation on $11$.It appears that it works quite fast. Here is my AC code (~90ms): 140494838I have some intuitive ideas of why it's fast. I'll try to think a bit more and I'll update this comment if I found something :)
•  » » 13 months ago, # ^ | ← Rev. 2 →   The total number of nodes and edges is $O(n)$ due to the observations. Basically, we always have that $c(10)+c(00)$ and $c(01)+c(11)$ are fixed because the string $b$ doesn't change, and after an even number of operations we also have $c(10)+c(11)$ is fixed because two operations is just a swap. From these three equations, the count $c(10)$ uniquely determines the other counts.The nodes that correspond to an odd number of operations are just one step away from an even number of operations, so we conclude the size of the graph overall is $O(n)$.
•  » » I got the same idea, but without BFS part: https://codeforces.com/contest/1615/submission/140485290 so the idea is that it is enough to check only one action on each type
 » How to do B??? :(((( Can someone give an easy explanation plzzz!
•  » » This is how I solved B.Notice that the maximum value you can have in all test cases is 2 * 10^5, so let's precompute a prefix sum arrays ps[i][j], i is from 0 to 200000, j is from 0 to 19. ps[i][j] is the total count of bit 1 in bit position j for all numbers from 0 to i. Then each test case becomes checking the prefix sum in range [L, R] for all bit positions. In order to use minimum deletions, we want to take a bit position that has the most 1s.
•  » » » Sorry if this is a stupid question but can you tell me why j is from 0 to 19. An int is represented by 32 bits shouldn't it be 0 to 31
•  » » » » As 2^19 > 2 * 10^5 therefore if we check for larger values of j the count is always zero.
 » I'm not sure, but I think that it's possible to solve H using slope trick.
 » Just wanted to say, D was brilliant
 » Tasks are good but time to think about them no so much :(
 » Can anyone give the proof of bonus in problem C?
•  » » Take a look at the submission: 140511019. If we do operation on 10, we end up scoring (#00 + 1) * 2 + 1. If we do operation on 11, we end up scoring #00 * 2 + 1.And if #11 is 0, then doing operation on 10 won't work either, since #00 + 1 should be equal to #11, which is impossible.
•  » » » could you please elaborate how you concluded #00 + 1 should be equal to #11
•  » » » » 13 months ago, # ^ | ← Rev. 3 →   Here's a chunk of code that explains it: if (type > 0){ int newType01 = type; int newType10 = type + 1; if (newType01 == newType10) { result = min(result, newType10 * 2 + 1); } } For result to be updated, newType01 should be equal to newType10, thus #00 + 1 is equal to #11.
 » Problem D was very nice imho.
 » Hey ! I actually solved $C$ quite differently. First check if two strings are equal if yes answer is $0$. Otherwise, Consider two pairs: $E$ = (count of equal $0s$, count of equal $1s$) and $NE$ = (count of not equal $0s$, count of not equal $1s$). Consider these two pairs as starting state. Now, we can simply run $BFS/DFS$ to check if we can reach to goal state which is $E$ = ($0$, $1$) and $NE$ = ($x$, $y$) where $x + y = N - 1$. This is the goal state because last move we do will have this kind of form. At each step, we can either take $1$ from $E$ or $NE$ and then we swap $N$ and $NE$ (we also swap number of $0$s and $1$s in each pair while handling picked $1$ separately). If we can't reach goal state answer is obviously $-1$ otherwise we can simply output current level of $BFS/DFS$. I had an intuition that this process will not continue forever and will end in after some small number of steps (I didn't prove correctness do reply if you can prove it).My Submission
•  » » This is also my way. I also need someone to prove it. My submission
 » 13 months ago, # | ← Rev. 3 →   Another way to solve $C$:First of all, selecting the same candle twice will not change anything, so each candle will either be selected once or not at all.If we select $x$ candles, the number of ones in them must be $\lceil\frac{x}{2}\rceil$, because the sequence of selected candles must be those with initial values 1010101...If $x$ is even, at the end the selected candles will be inverted and the others will not. If $x$ is odd, the selected candles will not change and others will be inverted.As we know the invalid candles that need to be inverted having count $cnt$, if $cnt$ is even we can try to select the invalid candles, and if $n-cnt$ is odd, we can try to select the correct candles.At the end take the minimum answer found or -1 if both trials failed. If a trial succeeds, its answer is the count of selected candles.
•  » » $\lceil{\frac{n}{2}}\rceil$ should be $\lceil{\frac{x}{2}}\rceil$.
•  » » » Corrected, thanks.
•  » » 13 months ago, # ^ | ← Rev. 2 →   had very much same logic ...got 3 WA during contest bcz i made count of 1 >=ceil(x/2) istead of ==ceil(x/2) (sob)
 » I have solved so many problems similar to problem D and yet again during the contest struggles to do it
•  » » It will be helpful if you send the link to those similar ones. And also some good resources I should go through before solving them.
 » Problem E has an N*sqrtN*logN solution which is good enough to pass system tests but can be hacked. I hacked 1 and 2
•  » » The solution constructs some sort of a longest-path decomposition.A sketch of a proof why that's the complexity, as discussed with kostia244:There can be at most $O(\sqrt{n})$ paths of length $> \sqrt{n}$, so the dfs works $O(n \sqrt{n})$ times. For the shorter paths, consider the forest at some time instant. If you give a potential equal to the depth of a tree to each node in that tree, doing a dfs and taking away 1 from the potential of each affected node reduces the potential of each affected node to at least the actual potential of the affected node after the tree has been split into a forest by removing the longest path. So the total change in the potential is at most the initial potential, which is $O(n \sqrt{n})$, since only the short paths remain.The extra log comes from the usage of std::set.
 » Does anyone know the ratings for each of the problems?
 » In the editorial for problem F, $p_{ij}$ is defined as the number of ways to get $\sum_{i=1}^{k} |a_i-b_i| = j$. I think the $\sum_{i=1}^{k}$ shouldn't be there.
 » In problem BWhat I did is count the number of 0s of every array element at every bit position and the ans will be the minimum of all those counts My solutionIts complexity is O(32*n) which should pass the given constraints, isn't it?since the maximum constraints is 2*10^5.Am I wrong?
•  » » 13 months ago, # ^ | ← Rev. 24 →   It's $O(32\times \sum (r - l))$, and the sum of (r-l) will be $10^4 \times 2\times 10^5 = 2\times 10^9$, so you will get TLE.
•  » » » Thank you for the reply but why is this summation sign is coming. The 1st loop runs for 32 times and the second loop runs for (r-l) time times so all together it will be 32*(r-l) isn't it?
•  » » » » t test cases.
•  » » » » » That I was meaning to ask you in competitive programming do we have to consider the constraints of t(the number of test cases) also? Sorry, if its a stupid question I don't know about it.
•  » » » » » » 13 months ago, # ^ | ← Rev. 2 →   Always consider it unless there's a constraint of $\sum (r-l)$.
 » The Problem H is well-known in China... •  » » Maybe the G and H are both useless algorithms.
•  » » Really? I never heard about it ...
•  » » » Check this: https://www.luogu.com.cn/problem/P6621 .
•  » » » » Thanks .
 » 13 months ago, # | ← Rev. 2 →   Hello Monogon, I think there is a typo in your editorial.In problem H's editorial, If there is any node u such that $s \rightarrow u$ and $u \rightarrow v$ both have flow, make them both have 0 flow, and this won't change the cost. I think it's supposed to be $s \rightarrow u$ and $u \rightarrow t$, right?
•  » » Yes, I'll fix it
 » which problem was interactive ?
•  » » Every problem is interactive when you talk about it with friends.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   What if you don't have coding friends? :(
 » https://codeforces.com/contest/1615/submission/140504399 problem B. I dont know why i got a time limit error at pretest 3 .
•  » » you are doing 2e9 operations in 2 second which will surely give you TLE. note that in problem there is no limit on sum of all test cases.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   but for each test case the time limit is 2s right. i dont think my code takes more than that(for each test case) even in the worst case. or am i wrong?
•  » » » » you have 2s for t test cases not for each test case
 » Is there anyone can use DP to solve problem E? Thank you in advance.
 » 13 months ago, # | ← Rev. 6 →   [ignore, sorted] i was returning without taking complete input on a multi — test.
 » Problem D was not original. I think a similar problem appeared once on codechef PARITREE
 » Can someone explain why we only check bits 1-30 at problem B? Shouldnt we also include the 0th bit?
•  » » I think in explanation , 1-based indexing is considers.so 1 here is LSB- least significant bit
•  » » » You're still considering 30 bits, when an int has 31 bits (excluding the sign bit). Shouldnt it only make sense to check all 31 bits?
•  » » » » check constraint, 2*10^5, I only checked 20 bits, checking more bits than that is not required
•  » » » » » Thanks for the info!
 » could someone elaborate the bonus statement of problem C
 » I only want to know how to find the Key observation of 'F'? It is too difficult for me.
•  » » The most sensible way to reach the key observation is by noticing the invariant of the problem.An invariant is some property of the string which doesn't change under the operations available to you. For example, one possible invariant in this problem is the parity of the number of ones in the string: If we started with an even/odd amount, every operation will add/subtract two ones, therefore keeping its parity.However, we want to find a tighter invariant. We want to be able to say that if $s_1$ and $s_2$ have that property, then we can reach $s_2$ from $s_1$ (or vice versa, of course). It is not possible with the previous invariant, as $0101$ is not reachable from $1010$.The correct invariant to look at is the number of zeros on even positions plus the number of ones in odd positions. It is indeed an invariant (check). Now we construct $s\prime$ which will act as a "dual" problem: for every bit $i$, if $s_i$ adds to the score of the string (so either $i$ is odd and $s_i$ is 1 or $i$ is even and $s_i$ is 0), we choose $s\prime_i = 1$, otherwise $s\prime_i = 0$. Also, every operation on $s\prime$ would be to flip two adjacent different bits (check that it indeed corresponds to a basic operation on $s$). Notice that: $s_2$ is reachable from $s_1$ if and only if $s\prime_2$ is reachable from $s\prime_1$, if and only if the bitcount of $s\prime_2$ equals the bitcount of $s\prime_1$ The way we constructed $s\prime$ from $s$ is exactly the key observation!
 » where is D problem standard code?
 » Problem C : MenorahMy Code with explanation : click here // we will change 1-1 and 1-0 alternatively because // if we changes same pair twice or more times consecutively than it will nullify the previous change // for ex. changing 1-1 (odd number of times consecutively) is equivalent to changing 1-1 (only once). // same for changing even no. of times which is equivalent to changing 0 times; int go(int a, int b, int c, int d, bool flag) { // if flag == 1 : it's time to choose 1-0 else 1-1 // c1 : 1-1 // c0 : 0-0 // w1 : 1-0 // w0 : 0-1 // x-y : x is the ith character of first string and y is the ith character of second(destination) string // a = c0, b = c1, c = w0, d = w1; if(c == 0 && d == 0) return 0; // no wrongs, only corrects if(flag) { // change 1-0 pair if(d == 0) return 1e9; // no more 1-0 left to change int c1 = c; int c0 = d - 1; int w1 = a + 1; int w0 = b; return 1 + go(c0, c1, w0, w1, 0); } else { // change 1-1 pair if(b==0) return 1e9; // no more 1-1 left to change int c1 = c + 1; int c0 = d; int w1 = a; int w0 = b - 1; return 1 + go(c0, c1, w0, w1, 1); } } void solve() { string a, b; cin >> n >> a >> b; if(a==b) { cout << 0 << endl; return; } int mn = 1e9; int c1 = 0, c0 = 0, w1 = 0, w0 = 0; fr(i,0,n) { if(a[i] == '1') { if(b[i] == '1') c1++; // 1-1 else w1++; // 1-0 } else { if(b[i] == '1') w0++; // 0-1 else c0++; // 0-0 } } mn = go(c0, c1, w0, w1, 0); mn = min(mn, go(c0, c1, w0, w1, 1)); if(mn > n) mn = -1; cout << mn << endl; } 
 » 13 months ago, # | ← Rev. 3 →   I'm not sure whether the proof in E is called contradiction or exchange argument. Can somebody elaborate?Edit: Oh, the editorial is updated! There was the word "contradiction" sometime and I commented on that. I also had too many doubts about the first revision of the proof but everything is now clear to me. Thanks!
 » In problem D,how can I find out the final r_i for each node? Could anyone please show me a sample of the code to problem D?Thank you!
 » Nice contest!!
 » Can anyone share their code for C that worked? Thanks in advance
 » Why are we able to add a direct edge between nodes $a$ and $b$? Or more precisely, how is a path relationship converted into a parent-child relationship?Also if we add direct edges, won't we be creating a graph rather than a tree? PurpleCrayon
•  » » An edge between $(a, b)$ is just a path of length $1$ between $a$ and $b$, so you can just treat it the same way as you do for any other path. Yes, you are creating an undirected graph, not a tree. However the graph you create isn't what you output. The graph is used to establish relationships between the different $r_i$ values. This information can be used to figure out all of the $r_i$ values, which you can then use to find the original values of each edge.
•  » » » Got it, thank you so much!
 » How to Solve the Challenge Problem given in Editorial in Problem B Challenge: solve the problem with 1≤l≤r≤109.
•  » » You can count the number of bits set as $1$ in the $i-$th bit from $[0,n]$ inclusive by noticing that the number of set bits alternates every $2^i$ numbers. For example for $i=1$, and the range $[0,7]$, the numbers are $000,001,010,011,100,101,110,111$. Notice that $i=1$ (the second bit from right) changes like this: $0,0,1,1,0,0,1,1$, it alternates between $0$ and $1$ every $2^i=2$ numbers. So you can use this pattern to count the number of ones in the range $[0,n]$ by dividing $\lfloor (n+1)/(2^{i+1}) \rfloor$ and handling the remainder separately. See submission here: https://codeforces.com/contest/1615/submission/151272206