### vovuh's blog

By vovuh, history, 4 years 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

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

 » 4 years 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!
 » 4 years ago, # |   0 in problem A how we are geting only 1 & 2 as output .can any one please explain in easy way
•  » » 4 years 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..
 » 4 years ago, # |   0 In the fourth question, we can enumerate a, B and C. the upper bound is 2 * C, which can also be crossed.
 » 4 years 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, isn`t 10^8 too much to pass through 2 seconds limit.
 » 4 years 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 years ago, # |   +6 Can someone explain me how the time complexity of the problem D is O(nlogn) ?
•  » » 4 years 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
 » 4 years ago, # | ← Rev. 3 →   0 21 42 0How is it coincide??Anyone help please
 » 13 months ago, # |   0 Im practicing DSU and just found out that the problem B can be solved by DSU, here's my solution: 196218629, but I wonder about the time complexity of this code