By VladProg, 2 years ago, translation, 1011A - Stages

Author: Mike Mirzayanov (MikeMirzayanov).

Tutorial
Solution

1011B - Planning The Expedition

Author: Mike Mirzayanov (MikeMirzayanov).

Tutorial
Solution

Tutorial
Solution

Tutorial
Solution

Tutorial
Solution

Tutorial
Solution

1010E - Store

Tutorial
Solution

1010F - Tree

Authors: Ildar Gainullin (300iq) and Dmitry Sayutin (_kun_).

Tutorial
Solution Tutorial of Codeforces Round #499 (Div. 2) Tutorial of Codeforces Round #499 (Div. 1) 499, Comments (79)
 » For Rocket bonus, you can check 1 then 2 then 3 etc. while recording p[] values. When you want to search for the answer do not include already searched values. which will turn 1073741853 to 1073741823. which can be done with 30 iteration.
 » I guess that solution to F is exactly the same as my one from this comment: http://codeforces.com/blog/entry/60806#comment-447283, but here author is just collecting and keeping polynomials from heavy path.
•  » » 2 years ago, # ^ | ← Rev. 2 →   Yup, it seems that my solution is exactly the same as yours :)
 » 2 years ago, # | ← Rev. 2 →   mlogm div2 B solution with data structures (probably not the mlogm the tutorial wants xD) SpoilerInstead of checking every time, we want to run a process that computes time.Make an array of food sizes, where each number x means there are x packets of one food type.Sort this array in decreasing order.Now loop through the array, for each point we want to find the maximum arr[i]/(used[i]+1), and this value can be maintained by a segment tree (store arr[i], used[i] and merge two nodes based on arr[i]/(used[i]+1)). And we assign the person to such a food pile.We loop through at max M elements, assign at max M people and we have a factor of logM from the segment tree, and we have another MlogM because sorting. It's overall O(M+MlogM+MlogM) = O(MlogM).
•  » » Another O(mlogm) solution is to binary search the answer with lower bound of 0 and upper bound of m.
•  » » » Yeah that's what the tutorial wants, and what most people went for. I just decided to share some interesting alternative, even if not the best.
•  » » » » I think you just want to show everyone that you did a badass code with segment tree, so everyone should think that you were cool
•  » » » » » that's because he is cool
•  » » » » » » Yeah, showing a solution with advance technique of an easy problem is cool
•  » » » » » » » it's not about the post, it's about the poster
•  » » » » » » » » Yes, i talked about showing. So the post was showing, or the poster?
•  » » » » » » » 23 months ago, # ^ | ← Rev. 2 →   advanced*
•  » » » I'm unable to crack it. Could u please explain a bit more about it ?
 » Many participants have solution on div1E based on finding the number of points inside a box in 3D space. How to do this effectively?
•  » » Offline with scanline + 2d segment tree, for example
•  » » » 2 years ago, # ^ | ← Rev. 2 →   Could you please tell me if we can use three one-dimensional segment tree to solve Div1.E?
•  » » » » No I doesn't work like that, because for 3D segtree (which you almost always never need because you can remove a dimension with sweep or something) you are querying for three constraints.So its something like Q(A and B and C) where A,B,C are [left,right] range query in some dimension.But using three one dimension is like Q(A) + Q(B) + Q(C).
 » The English is not very good. But thanks for the editorial, I managed to understand.
 » In problem E, we can eliminate another coordinate from the data structure by taking advantage of the fact that we can process queries offline, so we can sort them by 0-th coordinate. This results in a O(nlogn) solution that uses only simple 1D Fenwick tree with min operation as the data structure.Not very readable code: http://codeforces.com/contest/1010/submission/40820468
 » I think that Div 1. E can be solved with a simple segment tree.First, just as the tutorial says, we check the possibility of "INCORRECT". Then, each of the m moments can be treated as a open-ended 3D-box, i.e. denote the moment as (xi, yi, zi), if xi < xl, the restriction for knowing the moment (x, y, z) is "CLOSED" using this knowledge will be x ≤ xi, if xl ≤ xi ≤ xr, there will be no restriction for x, and if xi > xr, the restriction will be x ≥ xi. The same goes for yi and zi. Putting the 3 restrictions together gives you a open-ended 3D-box. The query is actually asking whether each point is in any of them.This is not difficult as it seems to be. First, there are actually 8 kinds of different boxes, regarding the  ≥  or  ≤  sign. We can deal with them by mirroring the coordinate and do the same process 8 times, so we only need to focus on {(x, y, z)|x ≤ xi, y ≤ yi, z ≤ zi} situations. This is done by a scanning line trick. We sort both the queries and the boxes by descending x coordinate. Then each time we need to update something like {(y, z)|y ≤ yi, z ≤ zi} when we meet a box, which is simply done by a segment tree in the range of [1, ymax], maintaining the maximum value of zi on yi so that there is a box covering {(y, z)|y = yi, z ≤ zi}.My code: 40807344
 » 2 years ago, # | ← Rev. 2 →   My 3D segment tree (aka octree) with some constant optimizations passed E.http://codeforces.com/contest/1010/submission/40822866The asymptomatic complexity is , I believe. This seems terrible but it works.
•  » » 2 years ago, # ^ | ← Rev. 2 →   Complexity of your solution is definitely not as you described. Even for 10000 queries on the test of type: 2 100000 10000 2 2 2 3 3 3 100000 100000 1 100000 100000 2 ... 100000 100000 100000 99999 99999 99999 99999 99999 99999 ... 99999 99999 99999 your solution works in more than 2s on CF. So for 100000 queries it works almost 30s. https://ideone.com/VnJcp3I looked through your code and complexity of your solution looks like O(m + log(x·y·z)) per query. These lines of code:  if(tree->p.size()<=LEAF_SIZE||(tl.x==th.x&&tl.y==th.y&&tl.z==th.z)){ for(Point &p:tree->p) if(in_box(ql,qh,p))return true; return false; } can check all m points through recursive call. I checked it for this test and your in_box(ql,qh,p) above was called 100000 times for 1 query. So your solution has complexity O(m·k).
•  » » 2 years ago, # ^ | ← Rev. 3 →   I'm guessing you have some implementation issue in your octree, but that a nice idea! I tried implementing it in Java, and it's the only 3d range query solution that passed the time limit (577 ms).Here is some of the other implementation:577 ms Oct3Tree (https://codeforces.com/contest/1010/submission/40861402)TLE RangeDTree (https://codeforces.com/contest/1010/submission/40860248)I even tried using persistence Kd-Tree, but this didn't quite work either.I'm interested why the range-tree (which is in the same complexity as the octTree), didn't pass the tests, maybe I'm missing a bug somewhere...Anyway cool question, I really enjoyed it :)
 » A round to test who type faster.
 » I solved both div2 problem B and problem C with binary search.
 » could somebody please explain the editorial explanation for div2 E? why we are we considering multiples of gcd only?
•  » » Using Euclidean proof? I don't know what it is in English, but only the multiples of gcd make the equation has a solution
•  » » For any integer a and b with gcd(a,b)=D, there always exists integers x and y, such that ax + by = D. And here we can use gcd, as D is also bounded by K,in other words (ax + by)mod K = D mod K, so there always exists non-negative x and y.If we take gcd(a1,a2,...,an,K)=S, we will get the smallest last digit(other than 0) which we can be obtained using the denominations ( K is also included in the gcd because we need the last digit which is bounded by K).So multiples of S less than K will be the answer because there are the number of denominations are infinite.
•  » » » Thankyou Hemant.
•  » » » How are they accomodating for negative coefficients?,like in this eqn a1*x1 + a2*x2 = c , if some xi is negative then?
•  » » » » If you try to do extended euclidean algorithm by hand, you will see this works for negative coefficient.Simple case:ax + by = d, where d = gcd(a,b)In many euclidian algorithm you define gcd(a,b) recursively like: gcd(a,b) = gcd(b, a mod b) and base case gcd(a, 0) = aWell actually, we know already x and y values forax + by = a (here x = 1, y = 0)andax + by = b (here x = 0, y = 1)Now we can use these values to find (x,y) such thatax + by = (a mod b) How?Lets say (a mod b) = a — kb. K is just a/b in integer division.Now say we know xa,ya, xb, yb where xval * a + yval * b = val.We can use algebra to find:x(a mod b) = x(a — kb) = xa — k*xb (basically taking the first equation — k*second_equation and distributing)and use same logic to find y(a mod b)Ok so now you can recursivley apply this logic until you find good coefficients x and y that make it so ax+by = gcd(a,b).Of course, try some examples and you will notice some of these coefficients are negative. (since a mod b is just a-kb, it's not surprising)Now you can extend this to more than 2 numbers because gcd(a,b,c) is just gcd(gcd(a,b),c) and so on.
•  » » » » » But... Why x_i < 0 does not affect the calculation to problem (Div. 2) — E, can you explain me.Tutorial: Here some xi<0, But Natasha can add for each par a sufficiently large number, multiple k, that xi became greater than zero, the balance from dividing the amount of tax on k from this will not change.what does it mean? add sufficiently large number, multiple k, that xi became greater than zero. I think that considering negative xi means that Natasha receives money from martians (she should only pay to visit Mars). Example 12x1 + 20x2 = gcd (12,20) = 4 where x1 = 2, x2 = -1. How is x2 made positive?
•  » » » » » » I think the answer is that x2 = -1, can become x2 + r*k. Then 12*x1 + 20*(x2 + r*k) = 12*x1 + 20*x2 = gcd (12,20) is true.
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   Once you find one set of coefficient, actually you can find infinite amount (and you can adjust the coefficients to be positive one)for example:ax + by = cbut also meansa(x+b) + b(y-a) = cAnd you can "adjust" it.
 » Solution Link : http://codeforces.com/contest/1011/submission/40827796 What is the error in the above solution? I used binary search for problem Div2C. The solution gets accepted if my high for binary search is 10^9+1 but not for 10^9.
•  » » Comparing double value with integer gives you 1000000000.0000000 > 1000000000. So 1000000000.0000000 is considered wrong(as it exceeds 10^9) which in fact is right. Did the same mistake
•  » » It is because, your first binary search. if(check(mid)) { if(check(mid-1)) r=mid-1; else break; } Let's say that l=10^9 and r=10^9 -> mid=10^9. when you called check(mid) function it returns true. It is obviously if you called check(mid-1), it will also return true and now your r will become 10^9 — 1; That's why when your first binary search is done, it will produce -1 (l>r)
•  » » » How is this code returning -1 on test case 58? https://codeforces.com/contest/1011/submission/40837886
•  » » » when l=r=10^9 and if check(mid) return true then obviously check(mid-1) will return false.
•  » » Using both mid+1 and mid-1 doesn't work in this problem because you are ignoring all the real values from (mid, mid+1) and (mid-1, mid) when you transition in your search. Eventually it means even when you convert it to doubles, you will not find an answer because the integer bounds were wrong.
•  » » » I didn't get. Int the second search, I am iterating 200 times from mid-1 tomid which covers all the real values.
•  » » » » Yes but you still do some "cutting" in your integer solution, and the incorrect bounds can carry over to your floating-point search because doing +1 and -1. Maybe it would work with 1e9+1 or mid+1, because of the offset, but the integer binary search is unnecessary and fundamentally wrong. It would be better if you started with floating point in the first place and fixed the iterations.
 » 2 years ago, # | ← Rev. 2 →   Can someone please let me know why was I getting Runtime Error in test case 8 on Div2 Problem C? CodeUpdate : Extremely sorry, my link to code went wrong. Here is the Code
•  » » Because n is up to 1000, and you collect both b[i]'s and c[i]'s into a, the size of a must be at least 2n.
 » Also in Fly Bonus: I guess it goes like this — Try calculating a general term for n=2 maybe. The final expression after taking Common terms and grouping turns out (1-1/a1)(1-1/a2)..(1-1/an)(1-1/b1)...(1-1/bn) multiplied by fuel+m or something like that. So the order of processing DOESNT MATTER since all the ai's and bi's are gonna be there as I wrote above.
 » Can anyone please explain what this means: Here some x i < 0 , But Natasha can add for each par a sufficiently large number, multiple k , that x i became greater than zero, for 1011-E
 » Can someone share some good practice questions similar to 1011F.Thank you.
 » Hey guys, can anybody help me with this BS solution for div2 C ? codeIt gives wrong answer on test case 58.. I know it is precision problem since an iterative BS solution works if I do like 50+ iterations. But how should I fix precision when I have this non-iterative code, should I just change EPS value ?
•  » » The answer in this test case is 109.If you write hi=1e9+EPS, then your solution will be accepted.
•  » » » Oh, I see the problem.. Thanks!!
 » can someone explain me the Div2 D question, not getting what is being asked in the question.
•  » » 2 years ago, # ^ | ← Rev. 2 →   You want to write a program to "guess" a number chosen by the judge.You can print out a number y, to which the judge will return you some information about whether the actual number, x, is less than, greater than, or equal to y (your guessed number).But sometimes the judge will lie and tell you x is less than y when really its the other way around. But the judge lies in a specific pattern of length n.Your program has to determine this pattern by guessing in some strategy, and after knowing this sequence try to guess the number x.
 » 1011C (FLY) Can someone please explain how we arrived at the equation s+x=tx
•  » » 2 years ago, # ^ | ← Rev. 2 →   total mass = mass that all fuel can transporttotal mass = mass of rocket with fuel that not used in this iteration + mass of fuel that used in this iteration = s + xmass that all fuel can transport = fuel coefficient * mass of fuel that used in this iteration = txs + x = tx
•  » » » Thanks for explaining :)
 » For 1010E : Doesn't a 2 dimensional segment tree take m² of memory ? How can this solution work without MLE ?
•  » » 2 years ago, # ^ | ← Rev. 2 →   Editorial says: "let's create a compressed two-dimensional segment tree". It takes only memory.
•  » » If you allocate nodes on demand its only qlogm (q is amount of queries)
 » 2 years ago, # | ← Rev. 2 →   Hey guys, In 1011C — fly can someone point out the error in my code. It fails for test case 58 and is accepted when I increase upper bound of BS from 10^9 to 10^9+1. The reasoning is as follows for test case 58. L will keep approaching 10^9(as check(l) is false) until r — l < eps. At which point it enters the block and check(r) must be true. code
•  » » The answer in this test case is 109. When you call check(109), it returns false because of presicion error.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   Thanks for replying. If that's the case then check(10^9) should return false even if I increase my upper_limit by one. However, when r = 10^9+1, it gets accepted (my answer is 1000000000.0000009537.) More specifically, can you elaborate more on "precision error".
•  » » » » Computer can't save all infinity digits of real number, because it hasn't infinity memory. So it rounds the number. If the program does many operations on real numbers, this error will increase.
 » why is it important to flush the output in C/C++. I know that printf() is line-buffered, so wouldn't '\n' flush the output anyway?
•  » » No. You can submit this code and this solution will get Idleness limit exceeded: code#include using namespace std; int query(int y) { printf("%d\n",y); //fflush(stdout); int t; scanf("%d",&t); if(t==0||t==-2) exit(0); return t; } int main() { int m,n; scanf("%d%d",&m,&n); int p[n]; for(int i=0;i
•  » » » I've already got an Idleness limit exceeded without fflush(). I'm just wondering why doesn't it work with simple '\n'.
•  » » » » \n is only character. It doesn't flushes output. I don't know why printf must flush output after \n.
•  » » » » » yes, '\n' does flush the output, but after searching, it turns out this only works when output is directed to the terminal, which is not the case with OJ. link
•  » » I use endl with cout (C++ style). I learned this from a Chinese and its very helpful and ez to use than before, when I only knew about flush and when I forgot to write them, I got wa verdicts with lots of annoyance. Hope it will be useful to you. Happy coding!!!
 » 2 years ago, # | ← Rev. 2 →   this code have WA on test 1problem div1. B 40930214upd:another submission , now its WA
•  » » try cout << i << endl; instead of cout << i;
•  » » 2 years ago, # ^ | ← Rev. 2 →   You forgot to print newline, problem requires thatUPD: Oh, and if you use std::endl instead of '\n' then get rid of your flush, because then you flush twice (unecessary)
 » Can anyone explain Div2 E problem: Border. I am unable to understand from the tutorial.
 » nice problem F
 » Bro @vladProg i am not getting solution to 3 problem (FLY). Below line..  then fuel can only take it to ourselves, and we need to take a rocket and a useful cargo (the mass of which is positive). That is, if t=1 at least for one t, it is necessary to deduce −1 Plzz help me. ThankYou!
•  » » Let t = 1 at least for one t. If we will use x tons of fuel, it can lift or land only t·x = x tons of (fuel + rocket). So mass of the rocket is at most 0, that is impossible.
 » 2 years ago, # | ← Rev. 2 →   What's wrong in my solution for third question FLY? Please someone tell.. http://codeforces.com/contest/1011/submission/40804467
•  » » 2 years ago, # ^ | ← Rev. 2 →   There is an overflow of type long long in your solution. Variables p and p_1 can be too big (p = a1 * ... * an * b1 * ... * bn ≤ 10001000 = 103000). If you send the Python code for example, it will be accepted, because Python supports big numbers. Python coden=int(input()) m=int(input()) p = 1 p_1 = 1 for a in list(map(int,input().split()))+list(map(int,input().split())): p = p*a p_1 = p_1*(a-1) if (p==0) or (p_1==0): print(-1) else: num = m*(p-p_1) print(num/p_1) 
 » What's wrong with my approach to problem Div1A? I binary-searched over the initial mass of the fuel. It's giving WA on test 58. Here is my solution