### Lewin's blog

By Lewin, history, 23 months ago, ,
Viscious Keyboard
Valued Keys
Voltage Keepsake
Volatile Kite
Vulnerable Kerbals
Varying Kibibits
Verifying Kingdom
Tutorial of VK Cup 2017 - Round 2

•
• +63
•

 » 23 months ago, # |   +23 Fast editorial! Great!
•  » » 23 months ago, # ^ |   +1 I think Lewin is fastest among problemsetters to put editorial :) .BTW I love the format too :)
 » 23 months ago, # | ← Rev. 2 →   0 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
 » 23 months ago, # |   +1 "First, we can make only one angle of the polygon nonconvex." Why?
•  » » 23 months ago, # ^ |   0 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.
 » 23 months ago, # | ← Rev. 3 →   -19 nice
 » 23 months ago, # |   +12 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.
•  » » 23 months ago, # ^ | ← Rev. 2 →   -16 I got the same error so that means...probably not. Maybe test case 71 should not be counted for some languages?
•  » » » 23 months ago, # ^ |   +5 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
•  » » » » 23 months ago, # ^ |   0 After looking through different solutions, they all look identical to mine besides some names, nothing big.
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 23 months ago, # ^ |   0 Same thing happened for me to during practice. Any reasons for the disparate results?
•  » » 23 months ago, # ^ |   0 I had the same issue http://codeforces.com/contest/801/submission/26432569
•  » » 23 months ago, # ^ |   0 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.
 » 23 months ago, # | ← Rev. 2 →   +5 Cool)) All the titles of the problems are "V... K..."P.S. Ранее условия и названия, в частности, были прочитаны на русском языке.
 » 23 months ago, # |   +5 In D we shouldn't consider f(S) >= x as numbers, but rather as a vector of digits (what is currently not specified).
 » 23 months ago, # | ← Rev. 2 →   +14 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?
•  » » 23 months ago, # ^ | ← Rev. 2 →   +7 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).
 » 23 months ago, # |   +4 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.
•  » » 23 months ago, # ^ |   +3 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
•  » » » 23 months ago, # ^ |   0 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.
•  » » » » 23 months ago, # ^ |   +3 yes of course it's 10^10. My solution has it's upper bound at 1e11 and still pass the system test
 » 23 months ago, # | ← Rev. 2 →   0 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 ?
•  » » 23 months ago, # ^ |   0 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.
•  » » » 23 months ago, # ^ |   0 Hey I didn't get it completely what you are saying! Can you explain in a bit detail ?
•  » » » » 23 months ago, # ^ |   0 What part you didn't understand?
•  » » » » » 23 months ago, # ^ |   0 How much time do you spend supplying i'th device?
•  » » » » » » 23 months ago, # ^ |   0 The time sufficient such that ith device garners a(i) amount of charge. SO the time in seconds will be a(i) / p seconds.
•  » » » » » » » 23 months ago, # ^ | ← Rev. 2 →   0 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
•  » » 23 months ago, # ^ | ← Rev. 2 →   0 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!
 » 23 months ago, # |   0 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
 » 23 months ago, # | ← Rev. 3 →   +25 Easy ac with long double on cpp. Easy tl/wa with bigdecimal/double on java. Nice ;)
 » 23 months ago, # |   0 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
•  » » 23 months ago, # ^ |   0 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.
•  » » 23 months ago, # ^ |   0 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<
 » 23 months ago, # | ← Rev. 4 →   +26 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.
•  » » 23 months ago, # ^ | ← Rev. 3 →   0 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.
 » 23 months ago, # |   0 Crisp and clear explanations in the editorial.
 » 23 months ago, # |   +19 In div1a (772A - Вечная Копилка), 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.
 » 23 months ago, # |   0 why there is not a fixed value for infinity .. like 1e10 or anything else (limits) in problem C
•  » » 23 months ago, # ^ |   0 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
•  » » » 23 months ago, # ^ |   0 can you please elaborate on why the upper limit is 1e14 + 1?
 » 23 months ago, # |   0 For 772A Voltage Keepsake, isn't Xi = max(0,T*ai — bi)?
•  » » 23 months ago, # ^ |   0 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).
•  » » » 23 months ago, # ^ |   0 Thank you!
 » 23 months ago, # | ← Rev. 2 →   +5 Hello: In 772A - Вечная Копилка 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 - Вечная Копилка, 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
•  » » 23 months ago, # ^ | ← Rev. 3 →   0 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
•  » » » 23 months ago, # ^ |   0 can you elaborate on why we multiply those two numbers 1e9 * 1e5 ? it is the maximum TIME we seek after all.
•  » » » » 23 months ago, # ^ |   0 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.
 » 23 months ago, # |   +10 In Div1-D, the inclusion-exclusion approach, how to calculate the modified f(x) function?
•  » » 23 months ago, # ^ |   +5 I have a solution with inclusion-exclusion .You can see details Here ! 26449626
•  » » » 23 months ago, # ^ |   0 What do these array mean in your solution: cnt, sum, sq, g?
•  » » » » 23 months ago, # ^ | ← Rev. 2 →   0 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]
 » 23 months ago, # |   +21 Can anyone please describe the solution of Div1 C with more details .
 » 23 months ago, # |   +8 In div 1 C how do we create the edges in a suitable time?
•  » » 23 months ago, # ^ | ← Rev. 2 →   +19 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
•  » » » 23 months ago, # ^ |   0 Thx man that helped! :)
•  » » » » 23 months ago, # ^ |   +8 Your Welcome :))
•  » » » 23 months ago, # ^ |   0 Can you explain for me why gcd(u, m) | v, that's equal to gcd(u, m) | gcd(v, m) ?
•  » » » » 23 months ago, # ^ |   +13 suppose that d = (u, m), d|vso d|u, d|m, d|vso d|m, d|vso d|(v, m)
•  » » » » » 23 months ago, # ^ |   0 Oh I see. Thank you for help
 » 23 months ago, # |   0 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.
•  » » 23 months ago, # ^ |   0 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);
•  » » » 23 months ago, # ^ |   0 Thank you! techay
 » 23 months ago, # |   +5 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.
•  » » 23 months ago, # ^ |   0 I am also having difficulty with the proof of correctness.
•  » » 23 months ago, # ^ |   0 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.
•  » » » 23 months ago, # ^ | ← Rev. 2 →   0 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?
 » 23 months ago, # |   0 in div1E , how does the checker check if the tree in output is isomorphic to the tree in input?
•  » » 23 months ago, # ^ |   +18 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.
•  » » 23 months ago, # ^ |   +8 Here's my checker implementation: https://pastebin.com/N5nLQUrHI just compute the bracket sequence, and don't do any hashing.
 » 23 months ago, # |   0 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?
•  » » 23 months ago, # ^ |   0 cause it's a valid point of time to make all devices alive with 0 units of power, you didn't consider that.
 » 23 months ago, # |   0 thanks lewin for that fast and well prepared tutorial, nice contest BTW.
 » 23 months ago, # |   0 801C - Вечная Копилка why the max answer is 1e14 ?
•  » » 23 months ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » 23 months ago, # ^ |   0 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.
 » 23 months ago, # |   0 The problem C why the sum suply of these bi more than p ,than output -1?
•  » » 23 months ago, # ^ |   +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.
•  » » » 23 months ago, # ^ |   0 OK，I have understand it.Thank you so much !
 » 23 months ago, # | ← Rev. 3 →   +8 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
 » 23 months ago, # | ← Rev. 2 →   0 The upper bound is 1e10, not 1e14.
 » 23 months ago, # |   0 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??
•  » » 22 months ago, # ^ |   0 Same here, and I guess it is just the language precision in floating number that causes.
 » 21 month(s) ago, # | ← Rev. 2 →   0 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.
 » 10 months ago, # |   0 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