### vovuh's blog

By vovuh, history, 6 months 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)

• +31

 » 6 months ago, # |   +42 B works in O(n), no sort needed. Code
•  » » 6 months ago, # ^ |   +3 nicely done :)
•  » » 6 months ago, # ^ |   0 awsome spookywooky
•  » » » 5 months ago, # ^ |   0 in problem A how we are geting only 1 & 2 as output .can any one please explain in easy way
•  » » 6 months ago, # ^ |   +4 Can you explain your solution? Thanks in advance...
•  » » » 6 months ago, # ^ |   +1 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.
•  » » 6 months ago, # ^ |   +1 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
•  » » 6 months ago, # ^ |   0 nice!
•  » » 4 months ago, # ^ |   0 Thank You very much!!!!
 » 6 months ago, # | ← Rev. 2 →   +24 If we use 2 pointers in E, complexity will be O(n). https://codeforces.com/contest/1311/submission/71823186
•  » » 6 months ago, # ^ |   +3 Can you explain your approach ? Thank advance ^_^!!
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 6 months ago, # ^ |   0 Wow!! Thank you for the detailed explanation. What a nice solution :>
 » 6 months ago, # |   +12 F can be solved without pbds and fenwick tree, look at this submission.
•  » » 6 months ago, # ^ |   +8 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.
•  » » 6 months ago, # ^ |   +6 I managed to solve F using a modified version of Merge Sort and prefix sums. Code.
•  » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # | ← Rev. 2 →   0 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.
 » 6 months ago, # | ← Rev. 2 →   +3 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?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +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.
•  » » » 5 months ago, # ^ |   0 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?
•  » » » » 5 months ago, # ^ |   0 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.
•  » » » » » 5 months ago, # ^ |   0 Thank you so much!
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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?"?
•  » » » » » » 5 months ago, # ^ |   0 I can kind of think about why it is so but cannot prove it. Maybe somebody good at Maths here can prove it
•  » » 6 months ago, # ^ |   +1 Could you please explain why do we iterate A to maximum 2a?thanks in advance.
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ | ← Rev. 4 →   +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)$
•  » » » » » 6 months ago, # ^ |   0 You're welcome, thank you too.
•  » » » » » 5 months ago, # ^ |   0 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).
 » 6 months ago, # |   +4 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)$
•  » » 6 months ago, # ^ |   0 nice <3
•  » » 6 months ago, # ^ |   0 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))
•  » » » 6 months ago, # ^ | ← Rev. 3 →   +8 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.
•  » » » » 6 months ago, # ^ |   -16 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.
•  » » » » » 6 months ago, # ^ |   +3 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).
•  » » » » » » 6 months ago, # ^ |   0 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.
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   +3 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
•  » » » » » » 6 months ago, # ^ |   +3 You are correct about this. Thanks for correcting me.
•  » » 6 months ago, # ^ |   0 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 ?
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Is there a way to approach find closest divisor of given number in O(log n) ?
•  » » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   0 I dont understand, can you go in more detail. I mean the source of your algorithm ?
•  » » » » 6 months ago, # ^ |   +1 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.
•  » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ |   +1 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.
•  » » » » 6 months ago, # ^ |   0 wow, thanks!
•  » » » 6 months ago, # ^ |   0 why till 2*10^4 . How did you get this number ?
•  » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   +4 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
•  » » » » 6 months ago, # ^ |   0 awesome, great explanation
•  » » » » 6 months ago, # ^ |   0 great!!!
 » 6 months ago, # |   0 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)
 » 6 months ago, # |   -7 IN D why editorial code O((n^2)*10^2) is working even after a<=10^4 and b <=10^4 ?
•  » » 6 months ago, # ^ |   +1 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)).
•  » » » 6 months ago, # ^ |   0 Thanks
 » 6 months ago, # |   +1 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
•  » » 6 months ago, # ^ |   0 I was hacked...
•  » » » 6 months ago, # ^ |   0 That's bad :-(
•  » » » » 6 months ago, # ^ |   0 I was rank 62 when I went to sleep,and rank 226 when I woke up,and found myself hacked.
•  » » 6 months ago, # ^ |   0 why are we setting limit to 20000? I do not understand this, can you please explain. Thank you
•  » » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   0 Greate problem!
 » 6 months ago, # |   +5 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?
•  » » 6 months ago, # ^ |   0 Oh I understand that now. B must satisfy: |B-b|<=|A-b|, thus B<=2b.
•  » » » 6 months ago, # ^ |   0 hi could you please elaborate a little more. Thanks in advance.
•  » » » » 6 months ago, # ^ |   +1 if |B-b|>|A-b|, then change B to A, and the result will be better
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   0 thankyouu :) williamwangx
•  » » » » 6 months ago, # ^ |   0 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; } 
•  » » » » » 6 months ago, # ^ |   0 AC. thank you for your precious time Ravenclaw_OIer !
 » 6 months ago, # |   0 " A cannot be bigger than 2a, " Proof please. (Problem D)
•  » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # | ← Rev. 2 →   0 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
 » 6 months ago, # |   0 can someone tell me why this submission got WA 71787302. and this AC 71788262. why could defining arrays in main is wrong?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 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
•  » » » 6 months ago, # ^ |   0 ooh! how stupid I'm XD .ty
 » 6 months ago, # |   -7 In Problem B you can try the logic of Bubble sort.. 71787966
•  » » 6 months ago, # ^ |   0 In the tutorial,why it is $n^2$ and $nlogn$，I don't think so
•  » » » 6 months ago, # ^ |   +1 I also..
 » 6 months ago, # |   -8 Any good source to learn pbds?
•  » » 6 months ago, # ^ |   0 Benq's template
 » 6 months ago, # |   -8 I made B, by using dfs
 » 6 months ago, # |   -23 For D -> The Upper Bound of B and C should be mentioned in the problem statement.
•  » » 6 months ago, # ^ |   +11 No
•  » » 6 months ago, # ^ |   +3 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.
 » 6 months ago, # | ← Rev. 4 →   -8 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.
•  » » 6 months ago, # ^ |   0 could you help me please? @Kirundel
•  » » 6 months ago, # ^ |   0 Please place codes in spoilers.
•  » » 6 months ago, # ^ |   +8 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$.
•  » » 6 months ago, # ^ |   0 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
 » 6 months ago, # | ← Rev. 2 →   +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
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Yes, These swapping questions can always be generalised into Graphs. Here is my similar solution using DSU.my DSU Solution
 » 6 months ago, # |   0 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.
 » 6 months ago, # | ← Rev. 5 →   -17 I can't figure out which is the editorial, the blog or the comments? :D
 » 6 months ago, # |   +1 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?
•  » » 6 months ago, # ^ |   +5 Coordinates compression and Fenwick tree. Read about both techniques and I think you'll understand the solution.
•  » » » 6 months ago, # ^ |   0 Thank you! :)
 » 6 months ago, # |   0 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.
 » 6 months ago, # |   +1 is there a proof for solution to E?
 » 6 months ago, # |   0 I am getting the error for testcase4 in Problem B. Please help me my code
 » 6 months ago, # | ← Rev. 2 →   -9 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$.
 » 6 months ago, # | ← Rev. 2 →   -9 .
•  » » 6 months ago, # ^ |   0 I don't understand why I'm getting downvoted
 » 6 months ago, # |   0 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.
 » 6 months ago, # |   0 In problem E, what is the logic behind calculating lower bound ld?
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 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/
 » 6 months ago, # |   0 For E, Can anyone explain me why the time complexity is O(nd)?
 » 6 months ago, # |   0 can someone explain me why in B,in nlogn solution we have checked for p[i]==0 ??
•  » » 6 months ago, # ^ |   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
•  » » » 6 months ago, # ^ |   0 thanks
 » 6 months ago, # |   0 why is this incorrect for fourth question (D).
 » 6 months ago, # |   -8 In F , what if the points start moving simultaneously at time t=0. how to solve then?
 » 6 months ago, # |   0 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)
 » 6 months ago, # |   0 Can anyone explain why we need to consider only upto 2*a in problem D?
•  » » 6 months ago, # ^ |   0 If Suppose A=2a+1 then |A-a|=a+1 so better convert a to 1. So, the difference then will be a-1.
•  » » » 6 months ago, # ^ |   0 Got it thank you.
 » 6 months ago, # | ← Rev. 2 →   +3 Could anyone share the simplest way you've figured out to build that tree(in E)? Thanks in advance.
 » 6 months ago, # |   0 why in problem D the harmonic series is estimated as log n? (I would like to see the proof)
•  » » 6 months ago, # ^ |   +3 One can use comparison of $\sum\limits_{n=1}^M \frac{1}{n}$ with $\int\limits_{1}^M \frac{1}{x} \, dx$
 » 6 months ago, # |   0 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
»
6 months ago, # |
0

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(); }

 » 5 months ago, # |   0 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!
 » 5 months ago, # |   0 in problem A how we are geting only 1 & 2 as output .can any one please explain in easy way
•  » » 5 months ago, # ^ |   0 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..
 » 5 months ago, # |   0 In the fourth question, we can enumerate a, B and C. the upper bound is 2 * C, which can also be crossed.
 » 5 months ago, # | ← Rev. 2 →   0 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, isnt 10^8 too much to pass through 2 seconds limit.
 » 4 months ago, # |   0 In problem D, Why we are using cC = cB * (c / cB) + i * cB formula?
 » 4 months ago, # | ← Rev. 2 →   0 in problem F vector cnt(vs.size()), xs(vs.size()); what is this xs?
 » 4 months ago, # |   0 I think the lower bound for $d$ in the problem E can be calculated as follows: $\sum_{k=1}^{n} \lfloor{\log_2 k}\rfloor$
 » 4 months ago, # |   0 https://codeforces.com/contest/1311/submission/76479163Firstly, I supposed the tree as complete binary tree and used the depth sum as initial sum. I checked that if I can move any vertex down from it's original depth and if I could then did it and incremented the sum till it becomes d. I thought it would be a tle as we are running two loops. Why it isn't.
 » 4 months ago, # |   0 can anyone explain the solution of problem C?
 » 3 months ago, # |   0 In B question i am getting wrong answer .My submission is https://codeforces.com/contest/1311/submission/79317124
 » 3 months ago, # |   +6 Can someone explain me how the time complexity of the problem D is O(nlogn) ?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 For each value of $A$ from $1$ to $2a$, you iterate over all possible multiples of $A$ from $1$ to $2b$. So the number of iterations is: $\sum_{A=1}^{2a} \lfloor \frac{2b}{A} \rfloor \leq {2b} \sum_{A=1}^{2a} \frac{1}{A} \leq {2b} \cdot (\log_2 2a + 1) = O(n \log n)$according to harmonic series
 » 3 months ago, # | ← Rev. 3 →   0 21 42 0How is it coincide??Anyone help please
 » 7 weeks ago, # |   0 I solved D. Three Integers using binary search in O(nlognlogn)`. If anyone is interested here is the code. Binary search the number of steps. (fix new A, and iterate over all possible values of new B which is multiple of new A, and check if new C exists).
 » 5 weeks ago, # |   0 I did B differently from the solution given in the editorial and got AC. https://codeforces.com/contest/1311/submission/86419979 Is the solution wrong?