### Monogon's blog

By Monogon, history, 5 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

• +178

 » 5 months ago, # |   +24 As someone who got WA pretest 8, was G doable with flows?
•  » » 5 months ago, # ^ |   +38 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.
 » 5 months ago, # |   -43 why f*cking tight time??????????????????????????
 » 5 months ago, # | ← Rev. 2 →   -29 fastest editorial ¿?
 » 5 months ago, # |   +202
 » 5 months ago, # |   +30 I solved upto E in the contest and have ready code for F to submit now lol. Amazing problems.
 » 5 months ago, # |   0 How to solve problem b for l and r less than equal to 10^9.
•  » » 5 months ago, # ^ |   -20 Maths
•  » » 5 months ago, # ^ |   -11 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
•  » » » 5 months ago, # ^ |   +6 This works only for l, r <= 2 * 10^5 no ? Correct me if i'm wrong.
•  » » » » 5 months ago, # ^ |   -18 Yes Bcoz test case is up to 10^4
•  » » » » » 5 months ago, # ^ |   +7 But ... "How to solve problem b for l and r less than equal to 10^9."
•  » » » » » » 5 months ago, # ^ |   -24 Do you literally think , Test case<= 10^4 And then l and r <= 10^9 Will this work bro?
•  » » » » » » » 5 months ago, # ^ |   +3 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 ?
•  » » » » » » » » 5 months ago, # ^ |   0 Then it'll work... Definately i guess... What you say according to your opinion?
•  » » » » » » » » » 5 months ago, # ^ |   0 IMO, your algorithm works only for l,r <= 2*10^5 no ?
•  » » » » » » » » » 5 months ago, # ^ |   0 Yes...
•  » » » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +5 so your algorithm doesn't work for 2*10^5 <= l, r <= 10^9UPD : sorry everyone for the long conversation
•  » » » » » » » » » 5 months ago, # ^ |   0 Yes Yes.... And thanks for clearing my confusion
•  » » » » » » 5 months ago, # ^ |   +1 we can calculate the number of set bits at jth position in [1,n] in O(log n)
•  » » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +1 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
•  » » » » » » » » 5 months ago, # ^ |   0 count of numbers in [1,x] having jth bit set is floor(x/(2^(j+1))) + max(0,x%(2^(j+1))-2^j).
•  » » » » » » » » » 3 months ago, # ^ |   0 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.
•  » » » » » » » » » 3 months ago, # ^ |   0 look closely i have written [x%(2^(j+1))]-2^j which can be negative
•  » » » » » » » » » 3 months ago, # ^ |   0 Sorry, my bad!
•  » » 5 months ago, # ^ | ← Rev. 2 →   +14 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; } 
•  » » » 5 months ago, # ^ |   +1 Congrats for being the Legendary Grandmaster : )
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   +1 Thanks ^-^, You too for becoming International Master. Merry Christmas Everyone :)
•  » » » » » 5 months ago, # ^ |   -11 your rating is around 1300 so how do you become red ??
•  » » » » » » 5 months ago, # ^ |   0 go to your profile page, and it's "MAGIC"!
•  » » » » » » » 5 months ago, # ^ |   0 thank u
•  » » » 5 months ago, # ^ |   +3 O(log(r))*
•  » » » » 5 months ago, # ^ |   0 Yeah sorry! It is of O(log2(r)).
•  » » » 5 months ago, # ^ |   0 Can you explain how your code for finding total numbers having Kth bit set is working
•  » » » 5 months ago, # ^ |   0 What is the logic for count function?
•  » » » » 5 months ago, # ^ |   0 You may find hereHope it helps :)
•  » » » 5 months ago, # ^ |   0 Bro, I did not understand how does your getcount function work. Could you please explain how does it work?
•  » » » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   0 Thanks a lot. that's a great solution.Merry Christmas everyone
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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 :)
•  » » » » » 5 months ago, # ^ |   0 Got it.Thanks a lot.
•  » » 5 months ago, # ^ |   +3
•  » » » 5 months ago, # ^ |   0 Can you explain a bit your solution? Thanks!
•  » » 5 months ago, # ^ |   +8
•  » » 5 months ago, # ^ | ← Rev. 4 →   0 Finally, I find a solution I can't find a solution on the contestthis function return number of combination of 0 for given number n and given bit position i int count0(int n, int i) { int q = std::pow(2, i); int m = (n + 1) - (n + 1) % q; int r = n + 1 - m; int mx = m / q; int count0; count0 = odd(mx) ? q * (mx + 1) /2 : m/2 + r; // int count1 = n - count0; return count0; } combination of l to r will be  int min = count0(r,0) - count0(l - 1,0); 
•  » » 5 months ago, # ^ |   0 i had same problem you can find ans for 1 to 2*1e5 and use it as ref to find 1e4 queries its that simple Here is my solution link for refrence
•  » » 5 months ago, # ^ |   0 Check my solution its O(1) time complexity. I didnt precompute anything.
 » 5 months ago, # |   0 Thanks for the fast editorial and merry Christmas
 » 5 months ago, # | ← Rev. 5 →   +20 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:$[10]_{new} = 1 + [00]_{old}$$[01]_{new} = [11]_{old}$$[11]_{new} = [01]_{old}$$[00]_{new} = [10]_{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 :)
•  » » 5 months ago, # ^ | ← Rev. 2 →   +26 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)$.
•  » » 5 months ago, # ^ |   0 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
 » 5 months ago, # |   0 How to do B??? :(((( Can someone give an easy explanation plzzz!
•  » » 5 months ago, # ^ |   +1 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.
•  » » » 5 months ago, # ^ |   0 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
•  » » » » 5 months ago, # ^ |   0 As 2^19 > 2 * 10^5 therefore if we check for larger values of j the count is always zero.
•  » » » » » 5 months ago, # ^ |   0 ohh ok thank you for the help
•  » » » » 5 months ago, # ^ |   0 because our max constraint is 2*10^5 , and most significant bit we wiil found upto 18 or 19.
•  » » » » » 5 months ago, # ^ |   0 Thank you for clarifying
 » 5 months ago, # |   +16 I'm not sure, but I think that it's possible to solve H using slope trick.
 » 5 months ago, # |   +11 Just wanted to say, D was brilliant
 » 5 months ago, # |   0 since im not able to solve problems (just solved A nd B today) in contest and also not understanding the solutions from editorial what must i do to see myself solving these problems in contest like if i keep doing this how would i improve ? advice needed!!
 » 5 months ago, # |   0 Tasks are good but time to think about them no so much :(
 » 5 months ago, # |   0 can somebody please recommend some blogs or references to read about bitmask? it'll be great help.
•  » » 5 months ago, # ^ |   0
 » 5 months ago, # |   0 Can anyone give the proof of bonus in problem C?
•  » » 5 months ago, # ^ |   +6 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.
•  » » » 5 months ago, # ^ |   0 Beautiful solution thanks for sharing.
•  » » » 5 months ago, # ^ |   0 could you please elaborate how you concluded #00 + 1 should be equal to #11
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   0 Here's a chunk of code that explains it: if (type[1][0] > 0){ int newType01 = type[1][1]; int newType10 = type[0][0] + 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.
 » 5 months ago, # |   +22 Problem D was very nice imho.
 » 5 months ago, # |   0 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
•  » » 5 months ago, # ^ |   0 This is also my way. I also need someone to prove it. My submission
 » 5 months ago, # | ← Rev. 3 →   +8 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.
•  » » 5 months ago, # ^ |   +3 $\lceil{\frac{n}{2}}\rceil$ should be $\lceil{\frac{x}{2}}\rceil$.
•  » » » 5 months ago, # ^ |   +3 Corrected, thanks.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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)
 » 5 months ago, # |   0 I have solved so many problems similar to problem D and yet again during the contest struggles to do it
•  » » 5 months ago, # ^ |   +9 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.
 » 5 months ago, # |   +30 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
•  » » 5 months ago, # ^ |   +6 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.
 » 5 months ago, # |   0 Does anyone know the ratings for each of the problems?
 » 5 months ago, # | ← Rev. 2 →   0 i went to youtube to see the explanation of problem C and i saw ityoutube.com/watch?v=B9Xr3tm5_K4
 » 5 months ago, # |   +21 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.
 » 5 months ago, # |   0 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?
•  » » 5 months ago, # ^ | ← Rev. 24 →   0 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.
•  » » » 5 months ago, # ^ |   0 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?
•  » » » » 5 months ago, # ^ |   +10 t test cases.
•  » » » » » 5 months ago, # ^ |   0 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.
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +10 Always consider it unless there's a constraint of $\sum (r-l)$.
•  » » » » » » » 5 months ago, # ^ |   0 ohhhhhhhhhhhh ok thank you for the help.
 » 5 months ago, # |   +92 The Problem H is well-known in China...
•  » » 5 months ago, # ^ |   +26 Maybe the G and H are both useless algorithms.
•  » » 5 months ago, # ^ |   0 Really? I never heard about it ...
•  » » » 5 months ago, # ^ |   +20 Check this: https://www.luogu.com.cn/problem/P6621 .
•  » » » » 5 months ago, # ^ |   0 Thanks .
 » 5 months ago, # | ← Rev. 2 →   +8 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?
•  » » 5 months ago, # ^ |   0 Yes, I'll fix it
 » 5 months ago, # |   0 which problem was interactive ?
•  » » 5 months ago, # ^ |   +86 Every problem is interactive when you talk about it with friends.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +10 What if you don't have coding friends? :(
 » 5 months ago, # |   +8 https://codeforces.com/contest/1615/submission/140504399 problem B. I dont know why i got a time limit error at pretest 3 .
•  » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 5 months ago, # ^ |   +3 you have 2s for t test cases not for each test case
•  » » » » » 5 months ago, # ^ |   0 DAAAAMNNN!! Lol I made all my submissionns for the past 2 months without knowing this. Thanks man
 » 5 months ago, # |   0 Done A, B in 15 min. Took ~1.50 to solve C.
 » 5 months ago, # |   0 Is there anyone can use DP to solve problem E? Thank you in advance.
 » 5 months ago, # | ← Rev. 6 →   +16 [ignore, sorted] i was returning without taking complete input on a multi — test.
 » 5 months ago, # |   0 Problem D was not original. I think a similar problem appeared once on codechef PARITREE
 » 5 months ago, # |   0 time limit in test 2 in B how can i solve https://codeforces.com/contest/1615/submission/140474193
 » 5 months ago, # |   0 Could you show any reference to potential method O(nm log n) to calculate min cost flow in problem H?
 » 5 months ago, # |   0 Can someone explain why we only check bits 1-30 at problem B? Shouldnt we also include the 0th bit?
•  » » 5 months ago, # ^ |   0 I think in explanation , 1-based indexing is considers.so 1 here is LSB- least significant bit
•  » » » 5 months ago, # ^ |   0 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?
•  » » » » 5 months ago, # ^ |   0 check constraint, 2*10^5, I only checked 20 bits, checking more bits than that is not required
•  » » » » » 5 months ago, # ^ |   0 Thanks for the info!
 » 5 months ago, # |   0 could someone elaborate the bonus statement of problem C
 » 5 months ago, # |   +18 I only want to know how to find the Key observation of 'F'? It is too difficult for me.
•  » » 5 months ago, # ^ |   +8 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!
 » 5 months ago, # |   +3 where is D problem standard code?
 » 5 months ago, # |   -13 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; } 
 » 5 months ago, # | ← Rev. 3 →   0 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!
 » 5 months ago, # |   +3 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!
 » 5 months ago, # |   0 Nice contest!!
 » 5 months ago, # | ← Rev. 3 →   0 why am getting wrong ans? filling prefix array:-for (int i = 0; i < 32; ++i) {for (int j = 1; j < N; ++j) {if ((j << i) & 1) {prefix[j][i] = 1;}prefix[j][i] += prefix[j — 1][I] ;} }solve() functionvoid solve() { ll l, r; cin >> l >> r; ll ans = INT_MAX; for (int i = 0; i < 32; ++i) { ans = min(ans, ((r - l + 1) - (prefix[r][i] - prefix[l - 1][i]))); } put(ans);} '
•  » » 5 months ago, # ^ |   0 bruh ! You are calling solve function in each test case :| just calculate it once !
•  » » » 5 months ago, # ^ |   0 this is not the final code i am precalculating it but not getting correct ans
 » 5 months ago, # | ← Rev. 3 →   -10 The tutorial for problem A was not very clear to me. For one thing, I did not understand how the observation in the first sentence implies that the answer is always $\le 1$. And besides, it does not explain why the sum being divisible by $n$ is sufficient for the answer to be 0. So I came up with my own proof.Let $m$ be the mean value of the elements of the array. Note that $m$ is integer when the sum of the elements is divisible by $n$.If $m$ is integer, and not all the elements are equal to $m$ then there is an element that is less than $m$ and an element that is greater than $m$. We can apply the operation to these two elements and repeat until all the elements are equal to $m$.If $m$ is fractional we can use a similar approach to make all the elements equal to either $\lfloor m \rfloor$ or $\lceil m \rceil$. This is the general case that is also applicable to integer values of $m$ when $\lfloor m \rfloor = m = \lceil m \rceil$.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 If the downvotes are because of what I wrote about the tutorial — I got it. $max(a) - min(a)$ eventually decreases even if initially there are multiple values of both $min(a)$ and $max(a)$, and the sum cannot be divisible by $n$ if $max(a) - min(a) = 1$. Still, what I wrote after that is valid.
 » 5 months ago, # |   0 Nice Explanation
 » 5 months ago, # | ← Rev. 3 →   0 resolved
 » 5 months ago, # |   -10 Am I the only one, or you guys too think that problem C is a pain?
 » 4 months ago, # |   0 Can anyone share their code for C that worked? Thanks in advance
 » 4 months ago, # |   +8 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
•  » » 4 months ago, # ^ |   +48 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.
•  » » » 4 months ago, # ^ |   +8 Got it, thank you so much!
 » 3 months ago, # |   0 How to Solve the Challenge Problem given in Editorial in Problem B Challenge: solve the problem with 1≤l≤r≤109.
•  » » 2 months ago, # ^ |   0 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