### vovuh's blog

By vovuh, history, 5 weeks ago, , 1311A - Add Odd or Subtract Even

Idea: vovuh

Tutorial
Solution

1311B - WeirdSort

Idea: MikeMirzayanov

Tutorial
Solution (n^2)
Solution (n log n)

1311C - Perform the Combo

Idea: vovuh

Tutorial
Solution

1311D - Three Integers

Idea: MikeMirzayanov

Tutorial
Solution

1311E - Construct the Binary Tree

Idea: MikeMirzayanov

Tutorial
Solution

1311F - Moving Points

Idea: vovuh

Tutorial
Solution (Fenwick tree)
Solution (pbds) Tutorial of Codeforces Round #624 (Div. 3) 624, Comments (126)
 » B works in O(n), no sort needed. Code
•  » » nicely done :)
•  » » awsome spookywooky
•  » » » in problem A how we are geting only 1 & 2 as output .can any one please explain in easy way
•  » » » Lets call a position where we cannot swap the two elements a border. So, for every position there is a border nearest left of it. All elements left of the border cannot pass the border (because we cannot swap there).In var ma2 we maintain the maximum value left of the border. Then we compare the current element (which is right to the border) to ma2.The var ma is used to maintain the current maximum, which is moved to ma2 whenever we find a border position.
•  » » Problem B We can use map to see can we go from a point to another and see for every a[i] Here is The code : 71906289
•  » » nice!
 » 5 weeks ago, # | ← Rev. 2 →   If we use 2 pointers in E, complexity will be O(n). https://codeforces.com/contest/1311/submission/71823186
•  » » Can you explain your approach ? Thank advance ^_^!!
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   Statement 1: There is no exist the tree with sum of depths of all vertices more than unary tree.Statement 2: There is no exist the tree with sum of depths of all vertices less than balanced tree.Let's create unary tree for default. Sum of depth for this tree — is the sum of ariphmetic progression. We must decrease it to the d. Fix the deepest vertex. Fix the top vertex of the tree. If we can't attacth the lower vertex to the higher because the sum of depth will be smaller than d, it means that we must deepen the upper vertex. And as we go from top to bottom the difference on every step decreases exactly 1. It means that there isn't exist the better solution.Add to these the condition that every layer must be not greater than 2 size of previous layer and this will be a solution.
•  » » » » Wow!! Thank you for the detailed explanation. What a nice solution :>
 » F can be solved without pbds and fenwick tree, look at this submission.
•  » » I explained some reasoning behind this solution but I should have posted it here: this is it:First there is a trick to sum all $x_j-x_i$ for $i50$; we only want $x_j-x_i$ where $v_j>v_i$. Coincidentally this equals the net sum of the three terms above. The reason is that if $75$ has the same rank in both the sorted $x$ and the sorted $v$ versions, then there is a symmetry in how $[25,50,75,100]$ mutates into $[100,50,75,25]$: we can let other elements "jump over" 75 to anywhere on the other side, and the symmetry is that the number of jumps going right over 75 equals the number of jumps going left: 100 jumped left, but then 25 jumped right. So the rank of 75 is equal in both cases, and we don't need to correct the $+75,+75,-75$ in our final answer.Another case is $25$, which is rank 1 with respect to $x$, but rank 4 with respect to $v$: From the contribution method, we had $-25, -25, -25$due to 50-25, 75-25, and 100-25. But because the rank changed from 1 (w.r.t $x$) to 4 (w.r.t $v$), we must have had 3 jumping overs to the left: and every such jumping over means we shouldn't have included a $-25$, so we correct with $+25$ 3 times, and end up with $0\cdot 25$ in the final answer.
•  » » I managed to solve F using a modified version of Merge Sort and prefix sums. Code.
•  » » why after changing vector >vec(n); into vector >vec; then it will get a Runtime Error? Is the data type "pair" responsible for this? Thanks.
 » 5 weeks ago, # | ← Rev. 2 →   How to solve F if there is integer t or positive integer t restriction.could we reduce any one restriction to nlogn time or some optimal time.
 » 5 weeks ago, # | ← Rev. 2 →   On problem D, I understood why do we iterate A to maximum 2a but what is the reason behind checking all multiples of A to maximum 2b? Also if we don't check for C = (c / B) * B + B, can we get the true answer?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   (c / B) * B and (c / B) * B + B are the two consecutive multiples of B such that C lies in between them.(c/B) * B <= C <= (c/B) * B + BSo C could be closer to either of the multiples. We have to check both.
•  » » » I have a problem is that (c/B) * B it can't ensure the C >= B,but the ans need the B < C.So why we need to consider both? we can't get the wrong ans?Could you tell me about that?
•  » » » » Whether C will get larger than or equal to B or it won't, we will always find an answer such that A < B < C. This is because the distance |c-C| + |b-B| will be larger when B >= C compared to any other possible solution where B < C.Also, when B > c (remember the lower-case letters are input variables), then c/B < 1, which means floor(c/B) = 0 and thus C = 0 or C = B which are both not feasible and will fetch us larger total distance sum compared to any feasible solution. It's hard to prove why but you can kind of imagine that.
•  » » » » » Thank you so much!
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   Is there actually a prove to the problem that "There is feasible solution having a smaller distance comparing to the solution that C=0 or C=B?"?
•  » » » » » » I can kind of think about why it is so but cannot prove it. Maybe somebody good at Maths here can prove it
•  » » Could you please explain why do we iterate A to maximum 2a?thanks in advance.
•  » » » Because we can iterate A to 1 at the same cost as iterating A to 2a. And it's clear that 1 can divide more numbers than 2a can divide.
•  » » » » 5 weeks ago, # ^ | ← Rev. 4 →   Oh, I understand that now. Thanks a lot.I also have some ideas to share with you.Thinking carefully, you'll find that the the reason behind checking all multiples of A to maximum 2b is the same as iterating A to maximum 2a.while $A>=2*a-1$, it works the same as $a=1$（maybe $a=1$ works more）,but that costs more, so $A\in [1,2*a-1)$In the same way, iterating B to A costs the same as iterating B to b+b-A, but while $B=A$, it works more,so $B\in [A, 2*b-A)$
•  » » » » » You're welcome, thank you too.
•  » » » » » Thank u, I can understand now. I prefer visualizing the thinking. Because B divide by A, C divide by B, so C divide by A. If you take $B > 2b$, you always can take B = a and this choice even give c more chance to reach C, because B (with > 2b) has multiple point is subset of B (with = A).
 » Another solution for D: Let's precompute divisors and multiples (up to $2 \times 10^4$) for all numbers up to the $10^4$. Let's then fix a value of $B$, then $A$ has to be a divisor and $C$ a multiple. We find such $A$ closest to $a$ and $C$ closest to $c$ in $O(log n)$, compute the number of operations for that particular $B$, and repeat this for all possible $B$'s. Total complexity $O(n log n)$
•  » » nice <3
•  » » Great solution but I think if constraints had been n <= 1e5 or n <= 1e6, then memory limit would have exceeded because space complexity is O(N*sqrt(N))
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   As far as I know, the sum of the count of divisors of numbers from $1$ to $n$ is about $n \times \log n$. Please correct me if I am wrong.I had the same solution with limit on B set to 1e5 and it passed easily.
•  » » » » Looks like we both are making lesser accurate approximations : LinkIf i understood the proposed algorithm right then I calculated :1.The number of divisors of all numbers from 1 till n. Let this be f(n) f(1e4) = 93,668 f(1e5) = 1,166,750 f(1e6) = 13,970,034 2.The number of multiples of i till 2*n for all i from 1 to n. Let this be g(n) g(1e4) = 191,177 g(1e5) = 2,372,113 g(1e6) = 28,326,296 If these numbers are correctly calculated then there could have been a problem with memory limit.Also, I think your solution passed because the constrains were upto 1e4. I am unsure of it, so do correct me if I'm wrong.
•  » » » » » My submission.It considers $MAX = 10^{5}$ and precomputes all factors of numbers from 1 to $MAX$. There seems to be no problems with memory but problems with time, it nearly hit the TL(due to multiple tests), but memory is fine.And I think I know why, since according to me, it should take $MAX \log MAX$ memory which is about 1.6 million ~ 12 MBytes (assuming long long), this seems to be consistent with the memory my submission took(9.6 MB).
•  » » » » » » I did not calculate the actual memory upper bound but you are right here. And your calculations are consistent with mine also. For n = 1e5, I also estimated 1.6M numbers in total. Which is passable. For n <= 1e6 it should fit in the memory limit as well, it would take something as high as 150 MB which is fine.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   About the link you gave regarding the upper bound on divisors. I think the upper bound on divisors of a single number is not tight enough to give sum of count of divisors of all numbers in a range with good margin of error. (Some numbers have more factors, some less, so error accumulates)See this comment for details about my estimation comment
•  » » I thought that finding closest divisor of given number has the complexity of O(sqrt(n)) since you have to iterate all the divisors of given number and check the diff of them ?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   Is there a way to approach find closest divisor of given number in O(log n) ?
•  » » » In this particular problem you can precompute all divisors of all numbers up to $10^4$ and have them in memory, so finding the closest one to a given number is a binary search so $O(log n)$. Check this code.
•  » » » I dont understand, can you go in more detail. I mean the source of your algorithm ?
•  » » » » Precomputation is like sieve of prime factors, we iterate on numbers and push current number to all of its multiples. Overall complexity is given by harmonic series sum, $O(n + n / 2 + n / 3 + ... + 1)$ which reduces to $O(n \times \log n)$.With this, we get list of divisors of all numbers from $1$ to $n$ now use binary search to find closest divisor.
•  » » great solution! But I'm wrong because I think that the range of possible B is 1 to 10^4. In your answer, you set it up to 2 * 10 ^ 4. Can you tell me why? Thanks
•  » » » Take for eg 137 10000 10000, the optimal solution would be 137 10001 10001, so the value(s) of a,b and c can exceed 10000.But we know that the value can never exceed 20000, since we could always bring down a,b or c<=10000 to be equal in less than 10000 steps.
•  » » » » wow, thanks!
•  » » » why till 2*10^4 . How did you get this number ?
•  » » I did the same but why till 2e4 and in the editorial why till 2a, could u plz explain? I got some intuition but unable to formalize it.
•  » » » We consider only the values <= 2*a because the cost of transforming a into a value >2*a is greater than the cost of transforming it into 1, and 1 will always be solution as every number is divisible by 1
•  » » » » awesome, great explanation
•  » » » » great!!!
 » WoW, thanks for the tutorial.In problem B, thought if I approach find a -> find b -> find c. I have to iterator for (all possible a), for (all possible b), (find c), which run in O(q * a * b) then get TLE. But now I learn more that I just need to go for (all possible a), for (mutiples a), (find c). O(q * a log a)
 » IN D why editorial code O((n^2)*10^2) is working even after a<=10^4 and b <=10^4 ?
•  » » We are iterating over multiples of "a",to find "b" as b is a multiple of "a".Its a kind of sieve that through which we don't have to consider all the values of b<=2*10^4.for(int i=1;i<=20000;i++) for(int j=i;j<=20000;j+=i) (Here i represents "a" and j represents "b")So,the time complexity in O(t*n*log(n)).
•  » » » Thanks
 » Does anyone uses brute force algorithm like me in problem D?XD #define n (20000) int a,b,c;cin>>a>>b>>c; int ans=9999999,_a=0,_b=0,_c=0; for(int i=1;i<=n;++i) for(int j=1;j<=n/i;++j) for(int k=1;k<=n/i/j;++k) { int now=abs(i-a)+abs(i*j-b)+abs(i*j*k-c); if(now
•  » » I was hacked...
•  » » » That's bad :-(
•  » » » » I was rank 62 when I went to sleep,and rank 226 when I woke up,and found myself hacked.
•  » » why are we setting limit to 20000? I do not understand this, can you please explain. Thank you
•  » » » because i know that 10000 is not enough (for example 173 10000 10000)but i can't find the real limit so i just set the limit 20000.(it's easy to prove that 20000 is enough)maybe 15000 is enough
 » Greate problem!
 » On problem D, I understand why we iterate A to maximum 2a but what is the reason behind checking all multiples of A to maximum 2b?
•  » » Oh I understand that now. B must satisfy: |B-b|<=|A-b|, thus B<=2b.
•  » » » hi could you please elaborate a little more. Thanks in advance.
•  » » » » if |B-b|>|A-b|, then change B to A, and the result will be better
 » can anyone please tell me what is wrong in my solution for problem B : #include using namespace std; #define deb(x) cout << #x << " : " << x << endl; bool cmp(pair a, pair b){ return a.first < b.first; } int main() { const int N = 105; int t; cin >> t; while (t-->0) { int n, m; cin >> n >> m; vector b(N); vector > a(n); for (int i=0; i> a[i].first; a[i].second = i; } sort(a.begin(), a.end(), cmp); for (int i=0; i> val; b[val]++; } bool flag = true; for (int i=0; i
•  » » I also got wrong answer during the contest. And the wrong answer was always on test 4. After the contest, I found the problem is on the cmp function. You can delete the cmp function and change "sort(a.begin(), a.end(), cmp)" into "sort(a.begin(), a.end())". Then you will get accepted. But I still don't know the specific reason until now and want to know why this type of cmp will cause wrong answer. I hope this can help you.
•  » » » thankyouu :) williamwangx
•  » » » » Try changing your comp function to this: bool comp(pair a, pair b) { if (a.first != b.first) return a.first < b.first; else return a.second < b.second; } 
•  » » » » » AC. thank you for your precious time Ravenclaw_OIer !
 » " A cannot be bigger than 2a, " Proof please. (Problem D)
•  » » Let's say A is bigger than 2a, then in order to get A from a, we need A — a > a add operations. No matter what B we pick, we can always use a — 1 subtract operations to get A = 1 from a, which always meet the requirement B % A = 0. So going over 2a always yields a worse answer than simply decrease a all the way down to 1.
 » 5 weeks ago, # | ← Rev. 2 →   For D I have different approach. I brute force C up to 2c. We know that number of divisors for numbers up to 20000 maximum is 60. So, if you prebuild all divisors for all numbers up to 20000, then for each C you can try each B (divisor of C) and for each B try each A (divisor of B). So each test is done roughly in 2c * 60 * 60 tries.I didn't prove that C is not exceeding 2c. Is there proof? Or, perhaps hack? 71792331
 » can someone tell me why this submission got WA 71787302. and this AC 71788262. why could defining arrays in main is wrong?
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   you should have defined P with size of N not M as the set of positions is in range (1 ≤ pi < n)your code after defined P with size of N 71849815sorry for my bad english
•  » » » ooh! how stupid I'm XD .ty
 » In Problem B you can try the logic of Bubble sort.. 71787966
•  » » In the tutorial,why it is $n^2$ and $nlogn$，I don't think so
•  » » » I also..
 » Any good source to learn pbds?
•  » » Benq's template
 » I made B, by using dfs
 » For D -> The Upper Bound of B and C should be mentioned in the problem statement.
•  » » No
•  » » I don't agree, it was a good aha moment for me to figure out upper bounds, and I think it is a big part of the problem.By the way, my weak/loose bound on $C$ was $4 \times 10^{4}$ but I took $5 \times 10^{4}$ during the contest just to be sure.
 » 5 weeks ago, # | ← Rev. 4 →   Why the complexity of the solution of Problem E in this tutorial is $O(nd)$. The while loop from n*(n-1)/2 to the lower bound that approximately equal nlogn. So I suspect it's complex is $O(n^3)$. (n<700) And I copy the solution written at the tutorial, and add a variant to count the time complex as below: codeint main() { int t; cin >> t; while (t--) { int n, d; cin >> n >> d; int ld = 0, rd = n * (n — 1) / 2; for (int i = 1, cd = 0; i <= n; ++i) { if (!(i & (i — 1))) ++cd; ld += cd — 1; } cout << ld << endl; if (!(ld <= d && d <= rd)) { cout << "NO" << endl; continue; } vector par(n); iota(par.begin(), par.end(), -1); vector cnt(n, 1); cnt[n - 1] = 0; vector bad(n); vector dep(n); iota(dep.begin(), dep.end(), 0); int cur = n * (n - 1) / 2; int iter = 0; while (cur > d) { int v = -1; for (int i = 0; i < n; ++i) { iter++; if (!bad[i] && cnt[i] == 0 && (v == -1 || dep[v] > dep[i])) { v = i; } } assert(v != -1); int p = -1; for (int i = 0; i < n; ++i) { iter++; if (cnt[i] < 2 && dep[i] < dep[v] - 1 && (p == -1 || dep[p] < dep[i])) { p = i; } } if (p == -1) { bad[v] = 1; continue; } assert(dep[v] - dep[p] == 2); --cnt[par[v]]; --dep[v]; ++cnt[p]; par[v] = p; --cur; } cout << iter << endl; cout << "YES" << endl; for (int i = 1; i < n; ++i) cout << par[i] + 1 << " "; cout << endl; } return 0; } It is my input : 1 650 5000 It is my output: 4837 268511100 YES 1 2 3 4 5 6 7 8 9 ... It seems that the complex is bigger than $O(nd)$. 650*5000=3250000 and it iters 268511100 times.
•  » » could you help me please? @Kirundel
•  » » Please place codes in spoilers.
•  » » It seems $O(n * (n^2 - d))$, but the algorithm just runs if there is an answer.Therefore $n\log_2 n \leq d$ or $n \leq \frac{d}{\log_2 n}$ and the algorithm runs in $O(\left( \frac{d}{\log_2 n} \right) ^3)$ which is enough to pass. This result also matches your experiment as $\left(\frac{5000}{\log_2 650}\right)^3 \approx 153204056$.
•  » » Code is O(max value possible — min value possible) per test case. If you only take cases where min value possible <= 5000 then the max possible gap is 218448 so final complexity is O(2*10^8) with pretty low constant
 » 5 weeks ago, # | ← Rev. 2 →   Another solution for B is use DSU. We will define x and x + 1 is an edge, then we merge them . Then we sort the array A with storing the original position. We will consider all elements of A ( after sorting ), Call POS[] is a array to store the original pos, If Pos[i] < Pos[i + 1] we continue the loop, else we check if they have the same root , if not the answer is NO and we return, else the answer is YES. My solution : https://codeforces.com/contest/1311/submission/71846993
 » I solved B a bit differently in NlogN, first I made sorted copy of array, then for each element found its index in sorted array, and checked if theres positions in array p for each index from 1 to i-1.
 » 5 weeks ago, # | ← Rev. 5 →   I can't figure out which is the editorial, the blog or the comments? :D
 » vovuh For problem F, I am not familiar with the fenwick tree coordinates compression technique. Can you elaborate a bit more on this? The following statement in your editorial probably has something to do with this technique? add our current point to the Fenwick trees (add 1 to the position Vi in the first tree and Xi to the position Vi in the second tree). I have some knowledge on fenwick tree but not so much with the coordinates compression technique. I assume it is needed because the input can be in range[1, 10^8] which would consume too much memory, right?
•  » » Coordinates compression and Fenwick tree. Read about both techniques and I think you'll understand the solution.
•  » » » Thank you! :)
 » More clear explanation for sentence in D editorial "Then let's iterate over all possible multiples of A from 1 to 2b. Let this number be B." While we want to choose B if we choose it bigger than 2b this mean we need to have at least (b+1) operations. Except this if we just equalize the B to A at most we do b operations. Because highest value of |b-A| can be (2a-b) or (b-1) and these are smaller or equal to b because a<=b. So that we can't choose B upper than 2b.
 » is there a proof for solution to E?
 » 5 weeks ago, # | ← Rev. 2 →   It seems like for D, any reasonably tight bounds will work: here is the one I came up with (after the contest...) and a proof: $a$ ranges from $i = 1$ to $2c$; $b$ equals $ji$ where $j$ ranges from $1$ to $ji\leq 2c$ Complexity: $O(c\log c)$ by counting all pairs $(i,j)$ with $ij\leq 2c$ (use harmonic series).Proof: $a$ will never be above $2c$: because instead of taking $a$ to $>2c$, $b$ to $>2c$, and $c$ to $>2c$, we could simply take $a$ and $b$ to $c$.And for the same reason, $b$ will never be above $2c$; because the number of moves in raising $b$ to $>2c$, and in raising $c$ to $>2c$, already exceeds the number of moves in making both $a$ and $b$ equal to $c$: $(c-a)+ (c-b) \leq 2c$.
 » 5 weeks ago, # | ← Rev. 2 →   .
•  » » I don't understand why I'm getting downvoted
 » Why we go till 2*b only ? Please tell is my explanation correct. So suppose we choose a multiple which is more than 2*b so total cost will be B — b which is more than b coz B > 2*b + cost of changing a + cost of changing a. We choose a such that it's cost dosen't exceed a (A <= 2*a) but in turn we have made the cost of b > b coz(B > 2*b) so as b > a we have made our costs worse. So we need to optimise cost of b before a. So suppose we optimise the cost of b and it will be <= b (coz B <= 2*b) for any given C. Now with this fixed B we can choose A in such a way that cost of a dosen't exceed a (A <= 2*a) to make it a divisor of B. Thus we improved cost of both a and b simultaneously. Hence we should only consider multiples upto 2*b as we can always get some A <= 2*a and B <= 2*B so that the condition B%A == 0 and C%B == 0 holds.Can someone tell if my idea is correct or it has some flaw.
 » In problem E, what is the logic behind calculating lower bound ld?
•  » » 5 weeks ago, # ^ | ← Rev. 3 →   The least value of sum of depths will be least only when all the layers of the binary tree are filled except possibly the last level. You could show that if this was not the case, you could move one of the leaves to a lesser depth and reduce the total sum of depths. This type of binary tree is called 'Complete Binary Tree'.https://www.geeksforgeeks.org/binary-tree-set-3-types-of-binary-tree/
 » For E, Can anyone explain me why the time complexity is O(nd)?
 » can someone explain me why in B,in nlogn solution we have checked for p[i]==0 ??
•  » » p[i] == 0 means this i index is not present in p and hence continue to next iteration because in this solution we are finding continues segment of p[i] == 1
•  » » » thanks
 » why is this incorrect for fourth question (D).
 » In F , what if the points start moving simultaneously at time t=0. how to solve then?
 » In PROBLEM F, Can anybody explain at what point below coordinates coincide? ~~~~~ 3 1 5 10 9 6 1 ~~~~~ A B C (suppose names of points)Ans is 0 I guess. But I don't understand at which point? (maybe I'm assuming something wrong)At 1 sec: A = 10, B = 11, C = 11 (Only d(B,C)=0)At 1.x sec:A = 11.a, C = 11.a, B = 11.b where b>a ( only d(A,C)=0)At 1.y sec: (y>x)C = 11.c, A = 11.d, B = 11.d where b>a (only d(A,B)=0)At 1.z sec: (z>y)C = e, B = f, A = g where g>f>e (diff increases more hereafter)
 » Can anyone explain why we need to consider only upto 2*a in problem D?
•  » » If Suppose A=2a+1 then |A-a|=a+1 so better convert a to 1. So, the difference then will be a-1.
•  » » » Got it thank you.
 » 5 weeks ago, # | ← Rev. 2 →   Could anyone share the simplest way you've figured out to build that tree(in E)? Thanks in advance.
 » why in problem D the harmonic series is estimated as log n? (I would like to see the proof)
•  » » One can use comparison of $\sum\limits_{n=1}^M \frac{1}{n}$ with $\int\limits_{1}^M \frac{1}{x} \, dx$
 » In Problem F. WHy do we need to make compression ?? I didn't make it and got wrong answer. but I coudn't understand why? Thanks for help
»

Problem B solution using disjoint sets

# include<bits/stdc++.h>

using namespace std;

int giveParent(int x,int *parent) { if(parent[x] == -1)return x; else{ return giveParent(parent[x],parent); } }

void solve() { int n,m; cin>>n>>m;

int a[n+1],b[n+1];
for(int i=1;i<=n;i++){
cin>>a[i];
b[i] = a[i];
}

int parent[n+1];
memset(parent,-1,sizeof(parent));
while(m--)
{
int x;
cin>>x;
parent[x+1] = x;
}

sort(b+1,b+n+1);
bool visited[n+1];
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;i++)
{
if(b[i] ==  a[i])
{
visited[i]=true;
continue;
}
else{
int j;
for( j=1;j<=n;j++)
{
if(b[j] ==  a[i] && visited[j] == false)
{
if(giveParent(i,parent) == giveParent(j,parent)){
visited[j] == true;
break;
}

}
}

if(j==n+1)
{
cout<<"NO"<<endl;
return;
}
}
}

cout<<"YES"<<endl;

}

int main() { int T; cin>>T; while(T--) solve(); }

 » For problem F,while updating and querying Fenwick tree we generally isolate the last bit and the update our loop control variable as x+=(x&-x) and x-=(x&-x).However,here we are using different updating statements in the functions(pos=(pos & (pos + 1)) — 1) and (pos |= pos + 1).Can someone please explain me this.I am new to Fenwick trees. Thank you!
 » in problem A how we are geting only 1 & 2 as output .can any one please explain in easy way
•  » » if a == b then obviously answer is 0, if a < b then we have to add a number to get from a to b, but we can add only odd numbers which is good if a is odd and we want to go to even number (o+o=e), or if a is even and we need to go to odd numbers (e+o=o), other wise we can subtract 1 from a to get to one of the above mentioned stage, do the same reasoning for a > b..
 » In the fourth question, we can enumerate a, B and C. the upper bound is 2 * C, which can also be crossed.
 » 4 weeks ago, # | ← Rev. 2 →   can anyone tell me why I am seeing O(n^2) and O(n^3) answers getting accepted in probD, here n = 10^4, how is that even possible, isn`t 10^8 too much to pass through 2 seconds limit.