By lewin, 12 months ago, ,

Hello!

The round 2 of VK Cup 2017 will take place on April 16 at 18:35 MSK (check your timezone here), along with separate div1 and div2 Codeforces Round #409. The contest "VK Cup 2017 — Round 2" is for teams qualified from round 1. The top 100 teams will advance to the Round 3, while other ones will have one more chance in the Wild Card Round 2 later this month. Those who don't participate in the VK Cup can take part in the Codeforces Round #409 individually (problems will be available in English too). All three rounds last 2 hours, and all are rated.

The round would not be possible without the following people (in no particular order): KAN, Errichto, winger, AlexFetisov, LiChenKoh, xiaowuc1, MikeMirzayanov. Additionally, I thank VK company for sponsoring this contest.

As usual, the scoring distribution will be announced later.

UPD 1: The scoring distribution is as follows:

div2: 500 — 1000 — 1500 — 2000 — 2750

div1 and official round: 500 — 1000 — 175022502250

UPD 2: The tutorial is available here: http://codeforces.com/blog/entry/51598

Congratulations for the winners

Official round:

div 1:

div 2:

Announcement of VK Cup 2017 - Round 2

•
• +217
•

 » 12 months ago, # | ← Rev. 2 →   +25 As I my teammate for VK wouldn't​ be able to participate can I participate in Round 409 instead? Because last time all teams qualified for Round 1 needed to participate in the Round 1.
•  » » 12 months ago, # ^ |   +10 Actually, there should be no difference for you: in which round to participate. Except the fact, that if you'll write official one, you'll have chances to pass to the next round.
•  » » » 12 months ago, # ^ |   +28 But so if I fail my teammate's rating will be ruined too :D
•  » » » » 12 months ago, # ^ |   +6 Nope, you can register only you
•  » » 12 months ago, # ^ |   +3 Bro! it's round 409 actually. :D All the Best
 » 12 months ago, # |   +12 Good luck to all participants!!!
 » 12 months ago, # |   +15 T-shirts?
 » 12 months ago, # |   +131 Unfortunately Clashes with Manchester United Vs Chelsea!
•  » » 12 months ago, # ^ |   0 Yeah, I'm out
•  » » 12 months ago, # ^ |   +4 And the F1 Grand Prix!
•  » » 12 months ago, # ^ |   +38 You can win wildcard round, similar to winning Europa League for League Champions ticket :)
•  » » 12 months ago, # ^ |   +16 I'm glad that man utd won otherwise i would have regret missing the contest. GGMU
 » 12 months ago, # |   -41 Something is wrong with my teacher. I write in C++. He gave me A+
•  » » 12 months ago, # ^ |   +6 You are lucky :P
•  » » » 12 months ago, # ^ |   0 Lol
 » 12 months ago, # | ← Rev. 2 →   +55 Rating prediction: div1, div2, VK-round2Для официального раунда (VK Cup 2017 — Round 2) на странице результатов предсказание будут отображаться только для команд с английским названием. Предсказания будут доступны в английской версии и таблицеExtensions: Have fun & high rating:) couple of pleasant thing that happened this week1) CF-Predictor extension for Chrome cross the threshold of 1,000 users!2) I finally received my T-Shirt from VK-Cup 2016!3) From today CF-Predictor can calculate rating for team contests!
 » 12 months ago, # |   +2 lueluelue
 » 12 months ago, # |   -25 Will the contest be rated?
•  » » 12 months ago, # ^ |   0 yes
•  » » » 12 months ago, # ^ |   +3 Thanks
•  » » 12 months ago, # ^ |   +20 All three rounds last 2 hours, and all are rated.
 » 12 months ago, # |   +202
•  » » 12 months ago, # ^ |   +13 You did it!
 » 12 months ago, # |   0 how can I enroll this :( ?
•  » » 12 months ago, # ^ |   +8 Click the third "Before contest"'s "Register now »" to join it. Have fun!
 » 12 months ago, # |   -11 Hack me if you Can!
•  » » 12 months ago, # ^ |   0 May be you are out of contest....:)
 » 12 months ago, # |   -14 王大拿
 » 12 months ago, # |   0 how to get extra registration?
 » 12 months ago, # |   0 YQY! ;(
 » 12 months ago, # |   0 Long queue for submission :(
 » 12 months ago, # |   0 long queue for submission in problem C:(
 » 12 months ago, # |   0 queue :'(
 » 12 months ago, # |   +4 Midway through the exam I realized I forgot to register. I guess I'm now officially too old for this shit.
 » 12 months ago, # |   +53 King Of Unsuccessful hack
•  » » 12 months ago, # ^ |   +55 I was trying to find the bug of someone's code but I couldn't find it :(
•  » » » 12 months ago, # ^ |   +32 No coach , you wanna reach the white rate :"D
•  » » » 12 months ago, # ^ |   0 whaa,u're trying to make a big leap in rating changes
•  » » » » 12 months ago, # ^ |   0 He is trying to do Bus
•  » » » 12 months ago, # ^ |   +12 I was trying to find the bug of someone's code but I couldn't find it :( Hah! Did you find anything wrong with my Div2.A solution? =)
•  » » » » 12 months ago, # ^ |   +4 Hey man , he qualified for ICPC , but i think he has a problem with Mike Mirzayanov
•  » » » 12 months ago, # ^ |   0 too late :) worse
•  » » » 12 months ago, # ^ |   +17 Mhammad1 Well, we didn't get the visa for ICPC this year, but at least now you are famous :D
•  » » » 12 months ago, # ^ |   +9 Stress testing isn't a good strategy for hacking.
 » 12 months ago, # |   +17 Problem difficulty is like AACCE lol
•  » » 12 months ago, # ^ |   +10 How to solve D?
•  » » » 12 months ago, # ^ | ← Rev. 2 →   +5 For each adjacent vertexes A, B and C: find the distance between point B and line AC, divide the distance by 2. Choose the minimum.
 » 12 months ago, # | ← Rev. 2 →   +46 problem title: "E. Verifying Kingdom"problem statement: described formally — no story about a kingdom or something :Dsame thing with some other problems :D
•  » » 12 months ago, # ^ |   +54 I think the writer's goal is to increase letters V and K as he can :D
 » 12 months ago, # | ← Rev. 2 →   -6 didn't enjoy the contest :pquite a boring one
 » 12 months ago, # | ← Rev. 4 →   +18 Please look into the user sp_502, and submissions of user newworldorder, it seems first user is just hacking second user in every 3-4 minutes to top the leaderboard. :P
 » 12 months ago, # |   +12 Problems statements are Short and Clear. Nice Problem Set.Thank You.
 » 12 months ago, # |   +19 I solved div.2 D quite fast, but it didn't pass presets. After thinking about possible bugs about 50 mins and stress-testing the solution I decided to change the language implementation from MS C++ to GNU C++ and it passed presets. So the question: is it honest to set such a high precision requirements that submission verdict heavily depends on C++ compiler choice?
 » 12 months ago, # |   +4 Logic for Div2 C please?
•  » » 12 months ago, # ^ |   +4 Binary Search
•  » » » 12 months ago, # ^ |   0 More details please.
•  » » » » 12 months ago, # ^ |   0 Binary search for absolute charging time (l): One device needs (l*a[i]-b[i])/P time to charge in that period(l). Take the sum of these positive values ant compare it to l.
•  » » » » 12 months ago, # ^ |   +2 Binary search the answer. for the device i: if b[i] — a[i] * time < 0 , you will need -(b[i] — a[i] * time) units of power. and check whether p * time >= AllThePowerYouNeed
•  » » » » 12 months ago, # ^ |   0 Take lower limit of ans as 0 and upper limit as 1e18 . Now since you know the time for which each device work thus you know the total power needed (req (power)=a[i]*mid) . If the power already present >= req (power) then continue to another device else the required power will be supplied from the plug and time required ( plugging time for this device ) for that = (req-b[i])/p ; this way sum up the time required on plug for each device (= totaltime). If totaltime>mid then r=mid else l=mid because if total time is more than the mid then answer should be less than mid otherwise answer can be greater than or equal to the mid . To check if we can use the devices indefinitely : check if mid>=1e17 after the binary search loop , if this fails then ans is mid .
•  » » » » » 12 months ago, # ^ |   0 How did you choose the upper limit as 1e18.
•  » » » » » » 12 months ago, # ^ |   0 Randomly. I did the same thing and payed for it :)
•  » » » » » » » 12 months ago, # ^ |   0 I chose 1e18 and it passed systests.
•  » » » » » » » » 12 months ago, # ^ |   0 mine for 1e15 is TLE, but 1e10 accepted with 93ms
•  » » » » » » 12 months ago, # ^ |   +3 I think the upper limit is 1e10 because the worst case that I can think of is you have n = 1e5 devices, The charger is as fast as possible but doesn't make the devices work for infinity p = 99999, each device uses minimum amount of power a[i] = 1 and has max starting power b[i] = 1e5. Now the time needed will be 1e10 because you originally have 1e10 power in total (summation of b[i]) and each second you lose one power in total (lose 1e5, one for each device.. and regain 99999 from the charger) so it will take you 1e10 seconds to run out of power.
•  » » 12 months ago, # ^ | ← Rev. 4 →   0 Imagine that there is no charger. Then your answer would be the min(b[i] / a[i]). (The one that finishes faster).But the charger makes you able to add this b[i]. So Binary Search the answer.When you are checking if they can last x seconds or not, you will need to sum needed = sum(max(0, x — (b[i] / a[i])) * a[i]), which is the energy needed by everyone to last x seconds. and if needed <= stay * p then you can charge them and make them last <= x seconds.BTW max(0, x — (b[i] / a[i])) is the how much time we need to add to the ith device to complete at least x seconds.
 » 12 months ago, # |   +8 How to solve Div2 D?
•  » » 12 months ago, # ^ |   +7 Point-line distance
•  » » » 12 months ago, # ^ |   0 I know that it is minimum altitude of a triangle, but checking all N^3 triangles TLEd.
•  » » » » 12 months ago, # ^ |   +6 For line (i, j), just check point i + 1 and j - 1
•  » » » » » 12 months ago, # ^ |   0 I tried doing that (well, even more, since I also checked i — 1, and j + 1) but got WA on pretest 4, but I calculated the area of a triangle, so maybe it was just double precision.
•  » » » » » » 12 months ago, # ^ |   0 Did you find ur mistake? I have wr on test 4 too.
•  » » » » » » » 12 months ago, # ^ |   0 Yeah, it was precision error, changing double to long double gave me AC.
•  » » » » » 12 months ago, # ^ |   +19 I got AC checking only adjacent triples i,i+1,i+2
•  » » » 12 months ago, # ^ |   +2 Can you elaborate it with some details.
•  » » » 12 months ago, # ^ |   +1 Point-line distance From what point? To which line?
•  » » » » 12 months ago, # ^ |   0 From one point to line between two near points(You should calculate the distance through perpendicular)
•  » » » » » 12 months ago, # ^ |   0 From one point to line between two near points(You should calculate the distance through perpendicular) Is that the required distance D?Can you give a prove for that (its not obvious for me)?
•  » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 If D > (distance from one point and line between two its neighbouring points) / 2 then we can place points in such a way that we will have not convex polygon.
•  » » » » » » » 12 months ago, # ^ |   0 Could D be less than (distance from one point and line between two its neighbouring points) / 2?
•  » » » » » » » » 12 months ago, # ^ |   0 Sure, we should take minimum of such values for all triples of consecutive points. Besides, we should also satisfy the condition that the answer is less or equal than half of any edge of the polygon(not to have intersections).
•  » » 12 months ago, # ^ |   0 I think the logic was to check if there exist a line which is equidistant from three points (perpendicular distance from line to points). No idea how to implement this one:)
 » 12 months ago, # | ← Rev. 3 →   0 How to solve Div 2C?
•  » » 12 months ago, # ^ |   0 Binary search on the time. Calculate how much under 0 each device will go if it runs without charger for t seconds.If the sum of these values that go under is less than or equal to the capacity of the charger * t then that time is valid and you should try a higher one. Otherwise go lower. At least I think that'll work.
 » 12 months ago, # |   +13 Similar problem to Div.2 E: http://codeforces.com/problemset/problem/487/C
•  » » 12 months ago, # ^ |   0 How did you find it?
•  » » » 12 months ago, # ^ |   +3 Just googled "prefix product sequence".
•  » » » 12 months ago, # ^ |   -10 I found it also, when I searched for prefix product. I didn't know what does it mean, so I just googled it.
•  » » » » 12 months ago, # ^ |   0 Well, it looks like googling that problem didn't help anyone. That's a relief for me :)
•  » » » » » 12 months ago, # ^ |   -10 487C was at least as difficult as this one, and I don't think the idea of that solution could be easily rewritten for this one.
•  » » » » » 12 months ago, # ^ |   0 But I remember the problem and its solution without googling :)
•  » » » » » » 12 months ago, # ^ |   +1 you are google it self ;)
•  » » 12 months ago, # ^ |   0 Imho, that problem differs from today's very much
 » 12 months ago, # |   +44 I think user sp_502 has cheated because he hacked a same user for 10 times
 » 12 months ago, # | ← Rev. 2 →   +5 I tried to hack a solution when the contest was only ten minutes or something. But Judge kept me in waiting queue during the whole contest and after 50 minutes someone hacked the solution and got the points and i'm still in waiting queue. Why this was happen? Also I didn't get negative point :( I was pretty sure about my hack case.
•  » » 12 months ago, # ^ |   0 this happened because someone hacked it before u and was waiting in the queue for a longer time than u were. u didnt get negative because the problem was already hacked by someone else before so ur hack was not taken into consideration
 » 12 months ago, # |   +8 My idea for div2B was: for every 3 adjecent points calculate the distance between the middle one and the segment, formed by other 2, then halve the result, and take minimum of all these values, but it didn't even pass the 3rd pretest(Could anyone point out where I've gone wrong?
•  » » 12 months ago, # ^ |   +5 True
•  » » 12 months ago, # ^ |   0 I did nearly the same and passed pretests. Did you consider n,1,2 and n-1,n,1?
•  » » 12 months ago, # ^ |   0 Maybe you have forgotten about first and last points, because my solution is same.
•  » » 12 months ago, # ^ | ← Rev. 3 →   +9 You also need to to halve the distance between two consecutive points.Edit: That distance is actually never optimal. Explanation Here.
•  » » 12 months ago, # ^ |   0 If it's point i, then you have to check it's distance from the line (i-2, i-1) and (i+1,i+2) line also. I did it, maybe it's still not sufficient, or my implementation was bad, but I failed on pretest 4.
•  » » 12 months ago, # ^ | ← Rev. 2 →   +8 You also have to take the minimum of half of each polygon side lengths. Because if somehow the radius is bigger than half of a side, you can move two ends of that segment making the polygon intersect itself. Edit: forget it.
•  » » » 12 months ago, # ^ |   +37 Height / 2 will always be smaller as the side of polygon is hypotenuse of the right triangle formed by the height, the side and the base(split at the point of intersection).
•  » » » » 12 months ago, # ^ |   0 Ah right.
•  » » » 12 months ago, # ^ |   +8 I didn't consider this... And passed pretest???
•  » » » » 12 months ago, # ^ |   0 Beacause you're so WEN3 that you needn't think about it.
•  » » 12 months ago, # ^ |   0 I binary searched the answer, checking if its possible the same way as you described. At least it passed pretests)P.S. Maybe you forgot about p[0], p[n — 1], p[n — 2] or smtj like that?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 I did the same thing and it passed. Maybe you initialized the answer wrong. The maximum possible distance was 10^9*sqrt(2)/2.
•  » » 12 months ago, # ^ |   0 Probably precision issues. I did the same, for some reason it was accepted after I output the answer with "cout << setprecision(10) << ans << endl;".By default, cout outputs 6 digits after the decimal point, which I thought would be just enough, so I'm not sure why this changed the verdict though...
•  » » 12 months ago, # ^ | ← Rev. 2 →   +8 thanks for replies, guys :)I was considering i, (i + 1) % n, (i + 2) % n, so indexes are not the case. Well, now I am confused, might be precision issues, but at least I know the approach wa correct)
•  » » » 12 months ago, # ^ |   0 I think you just have to print answer with greater precision.
•  » » 12 months ago, # ^ |   +3 Mine failed pretests with double, but passed with long double in C++11.
 » 12 months ago, # |   +18 How to solve Div. 1 C ?
•  » » 12 months ago, # ^ |   0
•  » » » 12 months ago, # ^ |   +8 How does it help us?
•  » » » » 12 months ago, # ^ |   +23 After this , you need a sequence of numbers a1, a2, a3, ..., ak such that gcd(ai, mod) divides gcd(ai + 1, mod) 1 ≤ i < k , so sort all the allowed numbers according to their gcd with mod and do dp.
•  » » 12 months ago, # ^ |   +20 You can go from a prefix product x to some other prefix product y if and only if gcd (x, M) | gcd (y, M). (that is, there exists a number z so that x * z % M = y if this condition holds). Now, for each value d | M, you can keep cnt[d] the number of numbers q that have gcd (q, M) = d and do not appear in the given list and some dynamic programming. If we write down the numbers gcd (prefix_product[i], M), we'll get some clusters (contiguous groups with the same value). You can keep dp[d] the maximum length of an array whose last element q has gcd (q, M) = d. There are few divisors for M<=200.000 (160 in worst case), so we can compute the dp in complexity O(number_of_divisors^2). In order to get some z for given x and y so that (x * z) % M = y, you should use modular inverse. To better understand it, look at the numbers' decomposition. Take care at the fact that the modular inverse of a number t is defined if and only gcd (t, M) = 1
•  » » » 12 months ago, # ^ |   -6 What does the symbol | mean?
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   +17 a | b means that b is divisible by a. Sorry, in my country it is a recognized notation
•  » » 12 months ago, # ^ |   0 First try to find max prefix modulo sequence. Prefix modulo should hold condition that gcd(pre[i],m) is divisible by gcd(pre[i-1],m)Using that condition,by dp we can find prefix modulos and then some inverse modulo operations on it gives the sequenceHere is my submission
 » 12 months ago, # | ← Rev. 3 →   +47 Did you noticed that names of problems starts with "V" and "K" letters?
•  » » 12 months ago, # ^ |   +5 on both languages!
•  » » » 12 months ago, # ^ |   0 Yeah, that is really cool!
 » 12 months ago, # |   +55 That feeling when you finally fix the bug and your solution runs ... one minute after contest ends ...
•  » » 12 months ago, # ^ |   0 same
•  » » 12 months ago, # ^ | ← Rev. 2 →   +93 In Div1 D, I finished coding but the first example didn't work. After contest I found that I calculated G(0) + G(1) + ... + G(999999) instead of G(0) ^ G(1) ^ ... ^ G(999999)..........
 » 12 months ago, # |   +56 the same code for div 1 B got WA 4 by using C++ 14 and passed pretest by C++ 11.
•  » » 12 months ago, # ^ | ← Rev. 3 →   +16 the cf is too hate you
•  » » 12 months ago, # ^ |   +12 Maybe you need better online judge！
•  » » » 12 months ago, # ^ |   -23 I think you will be downvote...hahahahah
•  » » 12 months ago, # ^ |   +16 Do u know any reason y??
•  » » » 12 months ago, # ^ |   +14 not know yet, waiting for system test to see dataset
•  » » » » 12 months ago, # ^ |   +15 What was your precision set to? And y did u submit so many times even after getting ac.Just out of curiosity.
•  » » » » » 12 months ago, # ^ |   +13 out of curiosity haha
•  » » » » » » 12 months ago, # ^ |   +10 I hope I won't be fst.....
 » 12 months ago, # |   +18 Is div2E/div1C just brute forcing on factoring of m then using dp to find the chain of factors the give the largest answer?
•  » » 12 months ago, # ^ |   0 It doesn't look so. What will be the chain of factors for this input:3 102 9 1
•  » » » 12 months ago, # ^ |   +5 1 -> 2 -> 10 for 1 we get 3, 7 for 2 we get 4, 6, 8 for 10 we get 0 so the answer is 6
•  » » » » 12 months ago, # ^ |   0 I am sorry, but I don't understand what you have written.What is this? 1 -> 2 -> 10
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 That's a chain going through the divisors of 10. His approach is correct. Edit: just a quick explanation: if you are on the divisor d, you can get to any number x such that gcd(x, m) = d and to the divisor T such that T % d == 0.
•  » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 That's a chain going through the divisors of 10. His approach is correct. Probably, I didn't understand the approach in the first place. Let me clarify a few moments.The divisors of 10 are: 1, 2, 5, 10. How do we go from this sequence of divisors (1, 2, 5, 10) to the chain 1 -> 2 -> 10? How does this chain 1 -> 2 -> 10 help us find the final sequence of length 6?
•  » » » » » » » 12 months ago, # ^ | ← Rev. 3 →   0 You have: (btw the divisors are 1, 2, 5, 10)0, 3, 4, 5, 6, 7, 8divide those numbers by their gcd with m 1: 3, 7 2: 4, 6, 8 5: 5 10: 0 order the divisors increasingly and d[i] = i'th divisor of m.dp[i] = max(dp[j] from j > i and d[j] % d[i] == 0) + number of numbers with gcd(x, m) == d[i]The answer will be on dp[0] (it will be 6) and the path of the answer will tell you which numbers to pick (the path is the chain).
•  » » » » » 12 months ago, # ^ |   +5 Notice 1 divides 2, 2 divides 10. I first picked all the numbers that have gcd(X,10)=1, which are not banned from input. Then, I went to numbers that have gcd(X,10)=2, which are not banned from input. Finally, since 0 is not banned, I put 0 at the end of sequence. Because you can only reach number B from A if gcd(10,A) divides gcd(10,B)
 » 12 months ago, # |   +11 Div.1 D makes me hate mathematics.
 » 12 months ago, # |   +72 Seems like he used the technique described by the bots in previous round :3
•  » » 12 months ago, # ^ |   +14 It's interesting that how he can be in same room with his fake account, is it just coincidence or there is a trick :D ?
•  » » » 12 months ago, # ^ |   +2 In div1 if you have ~20 accounts then there is high probability that 2 ids will be in same room :P in div2 it works sometimes too :P
 » 12 months ago, # |   0 again, div2C/div1A, like some problems in previous contest, is containing 100 kilometers long input file
 » 12 months ago, # |   +10 Did someone come up with an upper bound for the answer in Div2 C ?
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 I think it should be around max(n)*max(initial_power). I dont have a proof but I generated some test cases and they gave me this idea
•  » » » 12 months ago, # ^ |   +3 Your idea is correct because generate power must be lesser than sum of usage if the answer different than -1. Then it is obvious that the loss of bi is at least 1 per sec and so upper bound is sum of bi .
•  » » 12 months ago, # ^ |   +8 I used 10^20, it was enough. I think the bound is somewhere like 10^10, if you consider that all n (10^5) devices lose 1 power per time unit, (goes out after 10^5) then it's 10^5*10^5=10^10.
 » 12 months ago, # |   0 what are hack case for div2 A ?
•  » » 12 months ago, # ^ |   0 KK
 » 12 months ago, # |   0 Any tip for Div1 D?
•  » » 12 months ago, # ^ |   +8 Instead of f(S)=x consider f(S) ># x where a ># b off a's i-th digit is larger or equal to B's i-th digit for every i. To compute it and to get actual result from this auxiliary results do something similar to Fast Subset Convolution.
•  » » » 12 months ago, # ^ |   +35 Fast Subset Convolution?
•  » » » » 12 months ago, # ^ |   +53 Fast Subset Convolution.
•  » » » » 12 months ago, # ^ |   +10 Fast Subset Convolution is a technique to solve a following problem. We are given set U and a function (P denotes power set). We need to compute function g so that . Bruteforce way is O(3n), using FSC we get O(2n·n).
 » 12 months ago, # |   -9 undoubtedly today's best performer
•  » » 12 months ago, # ^ |   0 Zoomed screen 300%, still can't see picture :D
•  » » » 12 months ago, # ^ |   0 He got -72 hacks, and -2192 point overall, with 3 solved problems.
 » 12 months ago, # |   +5 OMG, so many WA's for problem Div.2 C
• »
»
12 months ago, # ^ |
Rev. 2   0

# Test 21 finger crossed

EDIT : killed

•  » » 12 months ago, # ^ |   +1 Div.1 — A. Test — 74 :(
•  » » » 12 months ago, # ^ |   0 me too!!
•  » » » » 12 months ago, # ^ |   +1 I think my INF is not big enough.
•  » » » » » 12 months ago, # ^ |   0 I WAed on the same test case, but the my issue is that my INF is too large. Haha.
•  » » » 12 months ago, # ^ |   0 Same :(
•  » » » 12 months ago, # ^ |   +3 I added checking -1 case separately (the sum of all the powers shouldn't exceed p) and then got AC
•  » » » 12 months ago, # ^ |   -10 My mistake was using 1e14 as upper bound instead of 1e13. Bad luck.
 » 12 months ago, # |   +8 Its showing failed system case for div2 D for all users, but displays accepted when clicked on it.
•  » » 12 months ago, # ^ |   +4 Paradox
•  » » » 12 months ago, # ^ |   0 Lol ;P
 » 12 months ago, # |   0 Fatalities everywhere in Div2 C and D 0_0
•  » » 12 months ago, # ^ |   0 At me too :(
 » 12 months ago, # | ← Rev. 2 →   +22 Why does the system say my problem d failed system test, but when i click inside it said i got accept?
 » 12 months ago, # |   +2 what happened on div2.D?
•  » » 12 months ago, # ^ | ← Rev. 7 →   +18 Bug on standings page.EDIT: Fixed now. EDIT: Unfixed :P EDIT: I think it's fixed for good now.
•  » » » 12 months ago, # ^ |   +6 Nope:)
•  » » 12 months ago, # ^ | ← Rev. 4 →   0 I think if we take triplets , We should have considered 1 as well in triplets ...I did not consider point 1 in triplet :/ I do not know anything
•  » » 12 months ago, # ^ |   0 At a moment the bug is fixed.But now it is buggy again...
•  » » 12 months ago, # ^ |   +3 hope to be fixed as fast as it can...
 » 12 months ago, # | ← Rev. 2 →   +1 Why this submission stuck in pretest 9? :DUPD: FIXED
•  » » 12 months ago, # ^ |   0 Cause after 9 pretest someone hacked it, your friend didnt notice, that after all VK strings there can last also KKKK... which can be transformed to VK so count++;
 » 12 months ago, # | ← Rev. 2 →   0 10^8 floating operations, 2s. Not sufficient. TLE on testcase 42 :/
 » 12 months ago, # |   0 I want to cut my veins...
•  » » 12 months ago, # ^ |   +31 Please don't! It is our own bad experience that is a lesson to us not to repeat our mistakes.
•  » » » 12 months ago, # ^ |   0 It was just an expression for being mad. Anyways, I don't even know what was my mistake. 26422821
•  » » » » 12 months ago, # ^ |   0 You stop when to and from are relatively close to each other, but it doesn't guarantee you that the number in between is close to answer.You can simply run some number of iterations (smth like 500) and then print the result. It's counted as good practice here. :)
•  » » » » » 12 months ago, # ^ |   0 But the correct answer will be between from and to always, won't it? I thought about the iteration number also, but I found it better to go for relative error, as the judge checks.
 » 12 months ago, # |   0 In Voltage Keepsake problem judge is rounding up, and i am outputing more precise and getting wrong answer for that :)))
 » 12 months ago, # |   +9 How come got accepted problem D and it's counted as a "Failed System Test" in the final standing.
•  » » 12 months ago, # ^ |   0 Bug in standing page .
•  » » 12 months ago, # ^ |   0 I have this problem , too. I got accepted D and it's counted as a "Failed System Test" in the final standing
•  » » 12 months ago, # ^ |   0 Got it, Thanks ^^
 » 12 months ago, # |   +24 How come same solution fails in Java: 26436284 but passes in C++: 26436022, can somebody explain this? Both solutions are exact same and both use double, it is not as if we use long doubles in C++ or anything. Super confused right now :(
•  » » 12 months ago, # ^ |   +5 I had the same problem with Java — rewrote it in python3 after an hour and it passed.. Too bad I get a really bad time :(
 » 12 months ago, # |   +59 I found, only 1 person got accepted by Java in Div1A. Most contestants got failed at test 71. Is this case valid?
•  » » 12 months ago, # ^ |   +26 Yes I agree and somehow it passes with EXACT same solution in C++, see my above comment for the codes. Bad time to use Java :(
 » 12 months ago, # | ← Rev. 2 →   +83 Problem A, Java 8: I don't see a single Accepted solution with binary search... (there are a few with sorting + explicit computation though).All of them failed on test 71, with "9995877311.0944" vs "10000000000.002304". Unfortunately, I don't see a way to download the test (as it is too long and gets truncated). Is it possible to share it somehow? I'm really interested in what's going on there. (I can try to get it part by part with debug submits, but I guess sharing is easier)FWIW, the troubles are clearly with precision, but I don't get why they appear only in Java (I see C++ binary search solutions accepted), and so consistently. I tried known precision-related tricks (like sorting doubles before adding them together), but they don't seem to help here...
•  » » 12 months ago, # ^ |   0 There seem to be some really weird stuff going on today, I solved A with sorting + traversal in java. However I solved B with the standard approach of calculating all heights of every 3tuple in java, but got WA, then I just ported my solution to python and got accepted. Is the servers JVM broken? :^)
•  » » 12 months ago, # ^ |   +24 This is a bit unexpected for me too, and we'll look into it.Test 71 is generated by the following code: n = 100000 print(n, 10 ** 9) for i in range(99999): print(10000, 100000) print(10001, 100000) 
•  » » » 12 months ago, # ^ |   0 Just out of curiosity, given that you use Java yourself, is the reason you didn't see this issue when writing problems because your reference solutions did not use binary search? Or is test 71 a hack case and thus was not seen before?
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 Test 71 was a hack. Actually it caused unexpected verdict in our java solution, but since all other c++ solutions agreed (in particular, the one that used long doubles also), we decided to mark the java solution as incorrect.
•  » » » » » 12 months ago, # ^ |   +14 Had u been a contestant trying to solve this problem in Java, and not the setter today, you would have failed to solve this problem right ?
•  » » » » » » 12 months ago, # ^ |   +18 I understand the frustration, and I have experienced this multiple times first hand where the problem is just not solvable in Java because of the problem setter's mistakes. As a contestant, I definitely would have been upset by this as well.On the other hand, I think it's a dangerous precedent to set to remove hacks that are difficult for a particular language to handle. I think the ideal solution is that problem setters should learn from this and set lower bounds or make sure precision is not as big of an issue (for example, there is no need for me to set a_i,b_i <= 10^5, and I could have set a_i,b_i <= 100).Anyways, I think the most similar situation is in round 284 where denormal numbers caused some submissions to TLE: http://codeforces.com/blog/entry/15356. In that case, the decision was to keep the contest rated. I feel that that situation is closest to this situation, so that's why I think the results should still stand.
•  » » » 12 months ago, # ^ |   0 We managed to find a java solution that works. We believe the problem is that the comparison A <= B when A,B are very large may not be precise. We're not sure why it only shows up in java.More specifically, the inequality we want to check is sum(a) * t — sum(b) — p * t <= 0, for devices that need to be charged. This may be imprecise, so we can compute it as sum(a * t — b — p * t / n) <= 0 instead. This seems to agree with all of our other solutions right right now.Unfortunately, I don't think we will change results, but I think next time I'll lower the bounds of such a problem more so precision issues like this are less likely to come up.
•  » » » » 12 months ago, # ^ |   +5 It makes sense that summing many doubles is less precise than multiplying long by double. Why does it only matter in java is less clear to me.
•  » » » » 12 months ago, # ^ |   +5 Interesting. I didn't by any means imply that results should be changed in any way — jury answer is clearly the right one.I tried to debug what's going on, but I still don't understand what happens there :( Apparently function f(t) = sum(a * t — b) / t — p is very non-monotonic around t = 1010, and jumps around 0 like crazy even with small changes of t. I'm not sure why the same doesn't happen in C++ — maybe it gets magically optimized to use higher-precision arithmetic.
•  » » » » » 12 months ago, # ^ |   +28 I checked some solutions from the top of the leaderboard, and they fail if compiled with -ffloat-store flag. Nothing new, though.
•  » » » » 12 months ago, # ^ |   0 I don't find it pretty fair to leave the results as they are.The fact that the same algorithm can pass in C++ and not in Java, is pretty unfair. It should be samely easy to get AC in every languages. Even the sentence We managed to find a java solution that works tells, that this was pretty hard for Java programmers. We couldn't have known, that Java double is buggy at big values, so this test is pretty cruel.Personally, I have lost 71 rating instead of winning something like 30, because of this test case. I'd be happy if this test case could be ignored for Java users, as a lots of people got WA on this test while using the right approach.
•  » » » » » 12 months ago, # ^ |   +12 In a problem with bigintegers, will you want all big tests to be removed for C++ submissions?You choose a language yourself and it's up to you to know its weaknesses. A solution is good if and only if it passes all created tests — not if it passes all tests except for those hard for this language.
•  » » » » » » 12 months ago, # ^ |   +3 I think it's something else with C++ big integers. If you need big integers, then the whole problem is about big integers, and handling hundreds or thousands of digits. You can know, that you can't use C++ there. But here, the problem wasn't about the double's precision at 10^10. Even lewin said, that this result was unexpected, so they didn't make this to have problem with double's precision.In C++ everyone knows that it can't handle big integers, because there is simply no datatype for that. But in Java, as you can see from the comments, and submissions, most of the people didn't know, that the precision of double is not enough. On the other hand I get your PoV, and you are mostly right, but I still think, that this problem was unfair for java users as a div2 C.
•  » » » » 12 months ago, # ^ |   0 Finally, I achieved to solve this problem (26441610) in C# by summing up like segment tree. Now, I'm really interested in whether we could hack this or not and how we should manage real number!
•  » » 12 months ago, # ^ |   +10 Got AC with Java 8 & binary search: 26437377.
 » 12 months ago, # |   -6 Hi, can anyone explain me this?Why the green guy, who got 1232 points doing A and B got +203 points when me and other green people with 1230 points A and B done got only 30-50?
•  » » 12 months ago, # ^ |   0 I believe that 'that green guy' got his solution on problem D accepted.
•  » » » 12 months ago, # ^ |   0 oh, ure right, thanks for the explanation
 » 12 months ago, # |   0 What is wrong with this solution http://codeforces.com/contest/801/submission/26427548 for Div2C / Div1A
•  » » 12 months ago, # ^ |   0 you have to output -1 if it is possible to keep all devices on indefinitely, you didn't do that.
•  » » » 12 months ago, # ^ |   0 I did, check line 53. If it is possible even at max_limit, I output -1
•  » » » » 12 months ago, # ^ |   +6 t*a[i] can overflow, when t = 1e24.
•  » » » » » 12 months ago, # ^ |   0 isn't the range of double much larger than that?
 » 12 months ago, # |   0 cout gave me wrong answer on test case 3 26434138 later after the contest just printed output using printf with 8 decimal places and got AC 26435680 :/
•  » » 12 months ago, # ^ |   +8 Always use setprecision.
 » 12 months ago, # |   +4 what's wrong !!?
 » 12 months ago, # |   0 Two problems double WA , long double after contest AC , i hope that's not intended.
 » 12 months ago, # |   +1 how much time will it take to update ratings?
•  » » 12 months ago, # ^ |   0 Probably something is wrong with the checker, lots of people got WA on div2 C with java, so they'll check it. It may take some time.
 » 12 months ago, # |   0 In div2 C , what happens wrong when we compare the answer to the upper bound in binary search for the infinity case? 26437983
 » 12 months ago, # |   0 Can someone explain to me why my solution for Div.2 C fails with binsearch upperbound 1e11 or 1e9 but gets AC with 1e10 ?
•  » » 12 months ago, # ^ |   +5 It fails with 1e9 because it is too small and fails with 1e11 because you use the == operator. Never use that thing with doubles.
•  » » » 12 months ago, # ^ |   0 Thank you so much! Using relative error it turns out that I can use upper bound up to 1e16. The only not clear thing here is why 1e9 is too little. I mean how to find upper bound for the answer in this problem?
•  » » » » 12 months ago, # ^ |   +13 For the following test it is clear that each second our total sum of b[i] decreases by 1 every second (as p — sum(a) == -1). Our total initial sum of b[i] is 10^10, thus we can see that the answer will be 10^10 and that this is the worst case. n = 100 * 1000; p = 100 * 1000 - 1; print(n, p) for i in range(n): print(1, 100 * 1000) 
•  » » » » » 12 months ago, # ^ |   0 Thanks, I got it)
 » 12 months ago, # | ← Rev. 3 →   0 I am really not able to understand why i am getting TLE on test 74. Please help me!!! Code: 26437499 UPD: It got accepted when upper bound = 1e10 but fails when upper bound = 1e12 or 1e18 , i don't know why?
•  » » 12 months ago, # ^ |   0 Probably because you lose precision and can't get a difference of 1e-5 when the numbers go too big so it creates an infinite loop.
•  » » » 12 months ago, # ^ |   0 How do we resolve this issue?
•  » » » » 12 months ago, # ^ |   0 Iterate a fixed number of times (like 100-200) or use relative error
•  » » » » » 12 months ago, # ^ |   0 Can you please point out what edit i need to make in my solution.
•  » » » » » » 12 months ago, # ^ |   +4 http://codeforces.com/contest/801/submission/26439427 look at the binary search look (it's now a for, not a while) look at the infinite condition (it's using now relative error instead of absolute error, the same could be done for the first loop)
•  » » » » » » » 12 months ago, # ^ |   0 It works but when i put the upper bound of binary search = 1e18 instead of 1e12, it is giving me WA verdict. 26445116
•  » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 Thanks for the explanation :) , my solution was also getting stuck in Infinite loop whenever the ans was calculated correctly, so I used clock to break the loop. Anyways it failed sys test due to 1e9 Solution
 » 12 months ago, # |   0 I cannot believe I passed Div2 C systest. I have no idea how precision works here. I just keep adjusting parameters until I passed pretest.
 » 12 months ago, # | ← Rev. 2 →   0 26431601 has WA 28. I have a variable ans, the initial value of which does not matter. After some attempts: 1. ans is not defined -- WA 28. 2. ans = INF, INF = 1e9 + 7 -- WA 28. 3. ans = 1e9 -- WA 33. 4. ans = 2e9 -- AC. 5. ans = 0 -- AC. Can someone explain me WHY?
 » 12 months ago, # |   -22 Huge minus to author's karma for Div 2C/Div 1A problem. They decided to not accept Java's double precision and didn't give enough time for BigDecimal solution. So if you use c++ and long double you are fine if java — please fail on test 71. BTW: solution with hardcoded value for such "tests" receives "Accepted": http://codeforces.com/contest/801/submission/26438478
•  » » 12 months ago, # ^ |   0 You're fine only with GNU c++. With MS c++ I also had precision problems using the same code.
 » 12 months ago, # |   0 Can Someone explain why are solutions for Div2/C got TLE when submitted in Ms C++ 2010 and got Accepted when submitted in Gnu++14? here's my code in Ms got TLE at test 66 26436248 and Accepted with exactly the same code on Gnu++14 with time 78!! 26436769
•  » » 12 months ago, # ^ |   +3 Similar problem for me. Got WA using MS C++ (26438473) and AC using GNU G++ (26438539). This is a really bad behaviour.
 » 12 months ago, # |   0 Lol, such a simple solution for div2C, and I spent a hour for solving it in much more complex way
 » 12 months ago, # |   0 Awesome rounds... and contests... fallen in love with codeforces <3
 » 12 months ago, # |   0 Manchester Vs Chelsea.... The awesomest 1...
 » 12 months ago, # |   +2 I'm the one to blame for the same number of points for two last problems. I solved the last problem quickly but struggled with the other one a bit. I even proposed to swap those two problems... (fortunately, it didn't happen).And btw. I'm surprised by precision issues in Java. Is there any fix for that? Maybe we can simulate float values with bigintegers in Java (if it's necessary)?
•  » » 12 months ago, # ^ |   0 I tried to use BigDecimal, but it is too slow and TLEs. Maybe there is some way to be very careful with the precision of the BigDecimals and make it work, but have not seen any solution like that so far. meijun has this submission though, 26437993, that uses streams somehow and passes in Java, but I don't really see how to intuitively know that this should work.
 » 12 months ago, # | ← Rev. 2 →   +21 Is it normal to have a submission failing the second pretest (which was part of the sample in div1D) counted as wrong submission? It was just now when I saw that I have -50 on that problem because it failed second sample (of course I could have made sure it works, but I sent it just about 2 minutes before the ending and, as I was running out of time, I didn't check all samples).Also, in the first problem, I used custom invocation to test my first attempt for div1A on a test with N = 100.000 and I saw it was running in 2200 ms, so I decided to resubmit it with smaller precision (170 iterations of the binary search instead of 200). The new source worked in custom invocation in 1930 ms, but on the final tests it worked in just 300 ms, which makes me wonder: is custom invocation running the code with the same speed as it does whilst system testing?
•  » » 12 months ago, # ^ |   +5 A participant might send a wrong code, print some debug info, or their solution can be wrong in CF system (e.g. small MAX_RAND). These mistakes aren't usually penalized thanks to friendly checking of the first test. Doing the same for other samples would help mostly if a participant is lazy or doesn't have time to run his solution on those tests — these arguments aren't that strong. I think the current system is ok.
•  » » 12 months ago, # ^ | ← Rev. 2 →   +16 To your first question yes it is normal, only incorrect submissions to the first sample / pretest are not counted. I don't claim to judge if this is fair or not, however there are cases where it is not trivial to know if a solution passes the samples, say in constructive problems with many possible solutions, and thus making all submissions that fail on samples not count would be a big departure from current policy.
•  » » 12 months ago, # ^ |   0 Thanks for the information. I just wanted to know if this is supposed to happen. I thought that CF ignores all solutions that fail samples, not necessary the first test. Soo, the answer for the first question was clarified. Can anyone answer the second?:)
 » 12 months ago, # |   0 Can someone look at my solution for Div1 B? I'm trying to use Binary search and moving the points closer to each other (perpendicular) and then computing the cross product to see if it's convex or not.
 » 12 months ago, # |   0 why there is not a fixed value for infinity .. like 1e10 or anything else (limits) in problem C
 » 12 months ago, # | ← Rev. 2 →   +13 For Div2-C / Div1-A This is AC code and this is the WA code. Only difference is, for -1 case, in AC code I have : if(check(1e14)) and in WA code I have: if(ans >= (1e14)) Can someone please point out what is my mistake here. Is there some kind of overflow which breaks my binary search to converge on a solution. The WA solution gives answer 99999997522874.859000000 on test-74, that is, it converges on a solution. Thanks
•  » » 12 months ago, # ^ |   +3 I had to face the similar problem.WAACCan't understand which statement caused the overflow, if any.
•  » » 12 months ago, # ^ | ← Rev. 2 →   +5 Strange behavior with my submission:Submited under MS C++ during the round and got WA71: http://codeforces.com/contest/772/submission/26418943The same code (only casting to double in printf) submited under GNU G++ 14 get AC: http://codeforces.com/contest/772/submission/26460846How is it possible?!
•  » » » 12 months ago, # ^ | ← Rev. 3 →   0 I think it's because the <= with doubles in the function check. Try to change the )need <= have) to (need < have+EPS_ (EPS = 1e-6)
•  » » » » 12 months ago, # ^ |   0 How does it relate to the fact that under GNU G++ 14 everything is OK?)
•  » » » » 12 months ago, # ^ |   0 But anyway it's WA71 http://codeforces.com/contest/772/submission/26461442 :D
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 This is accuracy error with doubles, it's not good to compare >= when using doubles. Try to change (ans >= (1e14)) to (ans > (1e14)-EPS), EPS is a low number, like 1e-5. In this case 99999997522874.859000000 is very close to (1e14), but not equal, then it's good use EPS when comparing doubles.
•  » » » 12 months ago, # ^ |   0 I actually think the difference between 1e14 and 99999997522874.859000000 is not very small, particularly not as small as something like 1e-5, (2477125.14063 to be exact). Even then, here is the same verdict after the suggested modification WA
•  » » » » 12 months ago, # ^ |   0 Try to submit in g++14, double is more precise. I guess the solution lost precise in (thisAns * v[i].first).
•  » » » » » 12 months ago, # ^ |   0 Same result.. WA
 » 12 months ago, # |   0 Hello... Why I don't rated in this contest I solved a question A
 » 12 months ago, # |   +5 My team submited this code under MS C++ for problem B in 22 min of the Round 2: http://codeforces.com/contest/772/submission/26422281 — got WA 4.The same code submited under GNU G++ 14 get AC: http://codeforces.com/contest/772/submission/26461048IDK what's wrong with MS C++ in codeforces, but with problem A http://codeforces.com/blog/entry/51577?#comment-355114 — my team lost 1390 points and, ironicaly, 100 place. :P
•  » » 12 months ago, # ^ | ← Rev. 2 →   +3 Different compilers generate different machine code, i.e. different set of assembler commands. And differently process floating point numbers. Try this code under MS C++ and GNU G++ 14 (you can use Run option): #include int main(){ std::cout << sizeof(long double) << std::endl; return 0; } It turns out that MS C++ prints 8 (bytes), while GNU 14 prints 12 (bytes). It means that under MS C++ long double is less precise than under GNU C++ 14. Moreover you could think about computing triangle area with more precision in problem B. In this case double would be enough.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 Thx, correct explanation — extinguish burning )But anyway there are submissions which using double (not long double) with 8bite size and the get AC. Example: http://codeforces.com/contest/772/submission/26419872
•  » » » » 12 months ago, # ^ | ← Rev. 3 →   +3 http://codeforces.com/contest/772/submission/26419872You are right. It almost same as your solution. And again, this AC double solution was sent to GNU G++. In fact, it produced a better assembler code for implementing function f(...). The same code sent to MS C++ generates WA 71: http://codeforces.com/contest/800/submission/26463062But if we rework a bit f(...) function with Kahan summation approach — we get AC, even on MS C++. See this attempt: http://codeforces.com/contest/800/submission/26463142The main problem is in this line: double add = T * a[i] - b[i]; UPD. In test 71, T*a[i]-b[i] ~ 10^14. Then we get the sum of 100000 such numbers, which is about 10^19 and does not fit into double precision. Lower bits of final value are just truncated and this leads your binary search to a smaller value, than test requires. So no magic here, just a bit of luck for GNU users :) I suppose GNU organizes all intermediate computations within floating-point registers (which are 10 bytes and more) with no writes to RAM.
•  » » » » » 12 months ago, # ^ | ← Rev. 3 →   0 MS C ++ makes me sad now :)Thank you for clarifying.
 » 12 months ago, # |   -6 hello world! :)
 » 12 months ago, # | ← Rev. 2 →   -11 Very quietly I take my leaveAs quietly as I came here;Quietly I wave good-byeTo the rosy clouds in the western sky.
 » 12 months ago, # |   0 Why I can register for Vk Cup Wild Cart round 2 only as individual participant? There is not option for registering as a team(I took part in both Vk cup rounds as a member of a team)