### Lewin's blog

By Lewin, history, 3 years ago, , Viscious Keyboard
Valued Keys
Voltage Keepsake
Volatile Kite
Vulnerable Kerbals
Varying Kibibits
Verifying Kingdom Tutorial of VK Cup 2017 - Round 2  vk, cup, Comments (88)
 » Fast editorial! Great!
•  » » I think Lewin is fastest among problemsetters to put editorial :) .BTW I love the format too :)
 » 3 years ago, # | ← Rev. 2 →   Div1B can be solved in O(n*log(D)) by binary searching on d. For a particular d if a line passes through the circles with centre i,i+1,i+2 and radius d then concave polygon can be formed. My submission
 » "First, we can make only one angle of the polygon nonconvex." Why?
•  » » We dont need more.If we can find 3 non-consecutive vertices of polygon moved for some D so that it becomes nonconvex, we can find 3 consecutive vertices of this polygon that being moved for the same D also make it nonconvex. If some vertex can become unconvex with some other vertex after moving them, it will also become unconvex with all of the vertices that are between them after moving these vertices for the same or lower D.
 » 3 years ago, # | ← Rev. 3 →   nice
 » In my impression, Div1 A is tough to solve in some language such as Java and C#. See this (26436569). It is almost same as expected solution. However, it failed at case 71.I want to know whether this problem can be solved or not.
•  » » 3 years ago, # ^ | ← Rev. 2 →   I got the same error so that means...probably not. Maybe test case 71 should not be counted for some languages?
•  » » » Hi guys, quickly check out accepted solutions here http://codeforces.com/contest/801/statusand filter by Java | accepted | Problem Cwe can learn something from how accepted Java solutions solved it.Take care
•  » » » » After looking through different solutions, they all look identical to mine besides some names, nothing big.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   After slowly making changes in my code until it works, this is what I came to:I was calculating the amount of time a device would need the charger for to stay alive , so I was using Math.max(0, (b[i] — a[i] * time)/p) and compared the total to time.What you were doing was using the required power as in the amount of energy per second the charger would need to have all of the devices living a.k.a. using Math.max(0, (a[i] — b[i]/time)) and comparing that to p.There are also other people who calculate the overall energy with Math.max(0,a[i]*time-b) and comparing that to time*P. This is what the editorial used.The only difference that caused power to work is that the numbers that are being worked with are smaller, meaning no calculation error. Thinking purely mathematically, all three way would work, but since the computer is not perfect at math, only one way works in practice.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   To get rid of the errors in calculations with fractional numbers, try to avoid multiplications/divisions with double values. Instead do the mul/div operations with integers and leave only comparisons to doubles. In my solution, I check only t <= sumB/ (sumA - p). sumA and sumB are the sums of those a[i] and b[i] for which t > b[i]/a[i]. Therefore all multiplication and division occurs with integers.Second thing worth-mentioning is that you can take high value in binary search to be a power of two. That would help to get integer values for t, most of the time.Hope, this helps.
•  » » Same thing happened for me to during practice. Any reasons for the disparate results?
•  » » I had the same issue http://codeforces.com/contest/801/submission/26432569
•  » » I had the same problem. setting the high value in binary search to 1e10 + 10 passes Test #71, but fails in Test #73. Setting it to 1e10 + 20, passes #73 but fails in #80 in my solution. Can't get further than that.Judges should clarify this issue.
 » 3 years ago, # | ← Rev. 2 →   Cool)) All the titles of the problems are "V... K..."P.S. Ранее условия и названия, в частности, были прочитаны на русском языке.
 » In D we shouldn't consider f(S) >= x as numbers, but rather as a vector of digits (what is currently not specified).
 » 3 years ago, # | ← Rev. 2 →   In div2C, I think the max answer can be at most around 10^10... The max answer will be generated by a case like:100000 999991 1000001 100000................1 100000Could you verify?
•  » » 3 years ago, # ^ | ← Rev. 2 →   Yes. It can be proved in this manner. Since p & a(i)'s are integers, this essentially means the sum of a(i)'s at t = 2sec < sum of a(i)'s at t = 1sec because p < sum of a(i)'s. This means sum of a(i)'s will decrease by atleast 1 after each second. Therfore maximum answere possible = sum of all a(i)'s in the start which is nothing but (10 ^ 5) * (10 ^ 5).
 » I have a question concerning problem Div.2 C:Why is the maximum answer 1e14?I had trouble finding the upper limit in the contest so I ended up putting it 1e20 or more, I solved it.Any help is appreciated.
•  » » in the worst case, p + 1 = sum of all a[i]. In that case, you need sum of all b[i] seconds to run out of energy
•  » » » In that case, the maximum answer is less than 1e14.Sum of all b[i] is 1e10. Therefore if the upper bound for binary search was 1e10, it would be fairly enough to solve the problem.Please correct me if I'm wrong.
•  » » » » yes of course it's 10^10. My solution has it's upper bound at 1e11 and still pass the system test
 » 3 years ago, # | ← Rev. 2 →   I didn't participe but I read tasks...I have questions for both A and B div 1. I would submit same solutions as written in editorial but some parts are not clear at all to me — they are intuitive but again I would like to hear proof.1.In A task when time needed to charge all devices is smaller than searched time — can you show construcktive algorithm of charging everything on way that none of devices will be empty during this period ?2.For B task. Why are we making always non-convex polygon, maybe sometime is more optimal to make polygon with edge intersections ?
•  » » If sum of demands <= p then this means you can come back to charge the same device after 1 second and it wouldn't have lost all of the charge. Let's suppose it the device starts charging from device 1 then device 2 .... device n and repeat. For each device i it gives it a(i) charge i.e. which can support it for 1 second Now since p > sum of all a(i)'s this essentially means it will be back at device 1 for the same charging cycle in <= 1sec and will re charge each device before it has fully drained all of it's charge of previous cycle.
•  » » » Hey I didn't get it completely what you are saying! Can you explain in a bit detail ?
•  » » » » What part you didn't understand?
•  » » » » » How much time do you spend supplying i'th device?
•  » » » » » » The time sufficient such that ith device garners a(i) amount of charge. SO the time in seconds will be a(i) / p seconds.
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   But this way of charging devices is not working on this testcase3 15 2 1 5 1 8 1You charge a first device 2/15 seconds. While you're charging amount of energy of the third device will be negative because 2*8/15 is bigger than 1
•  » » 3 years ago, # ^ | ← Rev. 2 →   I have similar doubts on problem A. Here are my thoughts. You don't really need a constructive algorithm to prove that the devices are alive. If you think of it like conservation of energy (charge) — As long as the charger can supply energy of P*T which is greater or equal to the charge required by all devices, an infinitesimally small charge persists on each device.I don't know if this is right. Any help is appreciated. Thanks!
 » In div2 C , what happens wrong when I compare the answer to the upper bound used in binary search for the infinity case? WA : 26437983 AC : 26438358
 » 3 years ago, # | ← Rev. 3 →   Easy ac with long double on cpp. Easy tl/wa with bigdecimal/double on java. Nice ;)
 » Someone please help me out in Div2 C problem. I don't know why i keep getting WA on test 31. I guess the problem might be lying in the error bound. Code: 26438641
•  » » The answer for 31 is -1. Don't use a certain time to determine if it is going on forever. Just check if the sum of the power usages is less than or equal to P.
•  » » Add this code instead of your current "output -1" code: long double sumNeeded = 0; for (int i = 0; i < n; ++i) sumNeeded += a[i]; if(p >= sumNeeded) cout<<-1; else cout<
 » 3 years ago, # | ← Rev. 4 →   For Division 2 C, I did everything the editorial said and even now, I am getting a .0003 error on test case 71. I can't seem to do better no matter what. Does anyone know why? Code: 26438965Also, when I used BigDecimal, I got runtime error on testcase 10.
•  » » 3 years ago, # ^ | ← Rev. 3 →   There was some problem with test-case 71 as many people got that test case wrong, mostly people that submitted with Java.I'm not sure because my solution (basically mirroring the tutorial solution) in C++ passed this testcase.
 » Crisp and clear explanations in the editorial.
 » In div1a (772A - Voltage Keepsake), you can use fewer runs of binary search by using the trick described by Um_nik in his blog: http://codeforces.com/blog/entry/49189?locale=en. It wasn't necessary today but it allowed making a program much faster (/ more precise). But please note that this thing has nothing to do with Java issues in this particular problem.
 » why there is not a fixed value for infinity .. like 1e10 or anything else (limits) in problem C
•  » » If you are asking why there isn't a value where you can safely say that the power will last forever, then their actually is, 1e14 + 1
•  » » » can you please elaborate on why the upper limit is 1e14 + 1?
 » For 772A Voltage Keepsake, isn't Xi = max(0,T*ai — bi)?
•  » » I think you're right, because we want the power to be charged, so Xi = max(0, T * a — b) seems just what we need.P.S.: it must be a mistake, the author's code uses Xi = max(0, T * a — b).
•  » » » Thank you!
 » 3 years ago, # | ← Rev. 2 →   Hello: In 772A - Voltage Keepsake how are you able to assume that the maximum for binary search is 1014? Where does this maximum come from? Also in the tutorial for 772A - Voltage Keepsake, you say Xi = max(0, bi - T * ai), however in your example code you write: ld need=max(0.0L, (imid-exhaust[i])*a[i]); Upon my own testing, I believe the condition in the code is right, and it should be updated to Xi = max(0, T * ai - bi). Thanks
•  » » 3 years ago, # ^ | ← Rev. 3 →   Hello, I think I just (partially) figured out the answer to my question #1 (why is the maximum 1014). Feel free to correct me if I am wrong.The largest time is produced if the power of the charger is one less than the sum of all the charges needed by the devices (if ). EDIT: It does not seem that 1e14 is the lowest possible upper bound though... I'm not sure why it was chosen... see my other comment below for more info
•  » » » can you elaborate on why we multiply those two numbers 1e9 * 1e5 ? it is the maximum TIME we seek after all.
•  » » » » Hello: According to my own testing with limits such as 1.5e10, it seems that 1e14 is NOT the lowest upper bound. I would like to instead argue that 1e10 is a better upper bound:Continuing the logic from my previous comment, the largest time is produced when . When this case is run, the answer would be the sum of the initial battery amounts of each device. There can be at most 1e5 devices, and each battery amount can be at most 1e5, thus the sum of the battery amounts has upper bound 1e5 * 1e5 = 1e10. Therefore I think 1e10 is a better upper bound.
 » In Div1-D, the inclusion-exclusion approach, how to calculate the modified f(x) function?
•  » » I have a solution with inclusion-exclusion .You can see details Here ! 26449626
•  » » » What do these array mean in your solution: cnt, sum, sq, g?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   let S[i] : be the multiset of numbers which all of them has following condition :for every x in S[i]:for every k , kth digit of x is greater or equal than kth digit of i.now :sum[i] is equal to sum of these elements.sq[i] is equal to sum of squares of this elements.g[i] is equal to the answer(the thing that question want!) for all of the subset of S[i]
 » Can anyone please describe the solution of Div1 C with more details .
 » In div 1 C how do we create the edges in a suitable time?
•  » » 3 years ago, # ^ | ← Rev. 2 →   the condition that we have an edge(directed) (u, v) :gcd(u, m) | v , that's equal to gcd(u, m) | gcd(v, m)so , replace each i , with gcd(i ,m),now you want a path that each number is divisor of the next number .you can do it with a simple dp .see this solution for more details ! 26435471
•  » » » Thx man that helped! :)
•  » » » » Your Welcome :))
•  » » » Can you explain for me why gcd(u, m) | v, that's equal to gcd(u, m) | gcd(v, m) ?
•  » » » » suppose that d = (u, m), d|vso d|u, d|m, d|vso d|m, d|vso d|(v, m)
•  » » » » » Oh I see. Thank you for help
 » In problem E/div2: there are two directed edges between two nodes i and j if and only if gcd(n, i) = gcd(n, j). Can anyone give a proof of this?Any help is appreciated.Sory for my poor English.
•  » » we can prove that, exist x make ix ≡ j modn if and only if gcd(n, i)|gcd(n, j)if ix ≡ j modn, gcd(n, j) = gcd(n, kn + ix) = gcd(n, ix). apparently, gcd(n, i)|gcd(n, j);the other way, if gcd(n, i)|gcd(n, j), then exist x make gcd(n, ix) = gcd(n, j), and j = ix + kn, too.so if there are two directed edges between i and j, and then gcd(n, i)|gcd(n, j) and gcd(n, j)|gcd(n, i), so, gcd(n, i) = gcd(n, j);
•  » » » Thank you! techay
 » In problem B, why do we only need to consider every 3 consecutive points? What I did was that, for each point, I took its distance from all line segments such that atleast one endpoint of that segment is adjacent to the given point. eg. A=(0,0), B=(1000,500), C=(1001,500), D=(1000,-500)Here, distance from A to line BC is less than distance from A to line BD.
•  » » I am also having difficulty with the proof of correctness.
•  » » In this case, the optimal answer is actually the distance from point B to line AC.I guess the difficulty may be when the projection of the point doesn't lie in the segment. In that case, I think we can claim that's never an optimal solution, and doesn't need to be considered.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   Yes, in this case, that is true. But in general, can we say that given three consecutive vertices A, B and C, there can never exist some vertex D such that distance from B to line AD is less than distance from B to line AC and that this is the final answer?
 » in div1E , how does the checker check if the tree in output is isomorphic to the tree in input?
•  » » Tree hashing. For example computing the centroid of the tree, then we can hash the subtrees by imagining the subtree as a bracket subsequence, and for each internal node, we sort the subtrees oriented from it by hash value.
•  » » Here's my checker implementation: https://pastebin.com/N5nLQUrHI just compute the bracket sequence, and don't do any hashing.
 » My dear!I have got at least 15 WA on div2 C!!!it's on the test 71 or 74 ,Could you please give me some suggestions?
•  » » cause it's a valid point of time to make all devices alive with 0 units of power, you didn't consider that.
 » thanks lewin for that fast and well prepared tutorial, nice contest BTW.
 » 801C - Voltage Keepsake why the max answer is 1e14 ?
•  » » 3 years ago, # ^ | ← Rev. 3 →   It's not. The maximum answer is 1010.Let's say I have 105 devices, each uses 1 unit of charge per second, and starts with 105 units of charge. The charger is p = 99999. The answer should be 1010.Edit: this scenario is the same as test #66.
•  » » » yeah I consider it as 1e10 as p has to be strictly less than the summation of the consumption and it's max val 1e5*1e5 ...but I got confused with 1e14 at the tutorial , thanks bro.
 » The problem C why the sum suply of these bi more than p ,than output -1?
•  » » It is if the sum of a[i]s is less than or equal to P, then the output is -1. The idea is that the total voltage will always increase through time.
•  » » » OK，I have understand it.Thank you so much !
 » 3 years ago, # | ← Rev. 3 →   div 1 B can be solved in O(n): We can draw a line through the nearest two points with a given point, and it is easy to see that the answer is half the length of the perpendicular from the point to this line (and we have three options to draw a straight line through two of the three points). That is, the problem is reduced to the search for a minimum of three heights of triangles formed by every three neighboring points. /// Мы можем провести прямую через ближайшие с данной точкой две точки, и нетрудно убедиться, что ответом будет половина длины перпендикуляра от точки к этой прямой (причём у нас есть три варианта провести прямую через две из трех точек). То есть задача сводится к поиску минимума из трёх высот треугольников, образованных каждыми тремя соседними точками. /// http://codeforces.com/contest/772/submission/26468460
 » 3 years ago, # | ← Rev. 2 →   The upper bound is 1e10, not 1e14.
 » In div2-D, firstly I used Heron's formula to get triangular's area but repeatedly got wrong answer. After fixxing it by calculating with vector property, I got accepted.Is it dangerous to use heron's formula in calculating triangular's area usually??
•  » » Same here, and I guess it is just the language precision in floating number that causes.
 » 3 years ago, # | ← Rev. 2 →   can anyone explain this line of the code given in the editorial for 772C — Vulnerable Kerbals:  int print = (long long) b * my_pow(a, cnt_coprime, m) % m; print = (long long) print * my_gcd(m, nxt) / my_gcd(m, previous) % m; Thanks in advance :)UPD: DONE.
 » can anyone help explain in B. Volatile Kite if i am using int for coordinates of the vertex i am getting wrong answer but using double AC,in input they are integer
 » 10 months ago, # | ← Rev. 3 →   I have a ques for this problem. QuestionIf I calculate "minimum such distance for all such consecutive three points on our polygon" then how can I be sure that by moving such distance the polygon does not intersect itself?? Can anyone give me proof?? thanks in advance