Привет!
Раунд 2 VK Cup 2017 состоится 16 апреля в 18:35 по московсвому времени (время в вашем часовом поясе по ссылке), параллельно пройдет стандартный Codeforces Round #409 для первого и второго дивизиона. Соревнование "VK Cup 2017 — Раунд 2" предназначено для команд, квалифицировавшихся из Раунда 1 или Уайлд-кард раунда 1. Лучшие 100 команд пройдут в Раунд 3, а у остальных будет еще один шанс в Уайлд-кард раунде 2. Те, кто не участвуют в чемпионате VK Cup, могут индивидуально принять участие в Codeforces Round #409. Все три раунда будут длиться два часа, все будут рейтинговыми.
Раунд не состоялся бы без следующих людей (в случайном порядке): KAN, Errichto, winger, AlexFetisov, LiChenKoh, xiaowuc1, MikeMirzayanov. Кроме того, спасибо компании ВКонтакте за проведение чемпионата.
Как всегда, стоимости задач будут объявлены позже.
UPD 1: Стоимости задач:
div2: 500 — 1000 — 1500 — 2000 — 2750
div1 и официальный раунд: 500 — 1000 — 1750 — 2250 — 2250
UPD 2: Разбор по ссылке (на английском языке): http://codeforces.me/blog/entry/51598
Поздравления победителям!
Официальный раунд:
- LHiC, V--o_o--V
- I_love_Tanya_Romanova, enot110
- netman, andrew.volchek
- aid, ershov.stanislav
- MrDindows, Rubanenko
div 1:
div 2:
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.
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.
But so if I fail my teammate's rating will be ruined too :D
Nope, you can register only you
Bro! it's round 409 actually. :D All the Best
TFW необходимо участвовать в раунде 2, чтобы пройти в раунд 2:
Лучшие 100 команд пройдут в Раунд 2Если будет участвовать один человек из команды и он пройдет в след. раунд, то пройдет вся команда? И рейтинг будет меняться только у этого человека?
Именно так.
А если оба участника будут отдельно участвовать?
Good luck to all participants!!!
T-shirts?
Unfortunately Clashes with Manchester United Vs Chelsea!
And the F1 Grand Prix!
You can win wildcard round, similar to winning Europa League for League Champions ticket :)
I'm glad that man utd won otherwise i would have regret missing the contest. GGMU
Something is wrong with my teacher. I write in C++. He gave me A+
You are lucky :P
Lol
Rating prediction: div1, div2, VK-round2
Для официального раунда (VK Cup 2017 — Round 2) на странице результатов предсказание будут отображаться только для команд с английским названием. Предсказания будут доступны в английской версии и таблице
Extensions:
Have fun & high rating:)
1) 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!
lueluelue
Will the contest be rated?
yes
Thanks
All three rounds last 2 hours, and all are rated.
You did it!
how can I enroll this :( ?
Click the third "Before contest"'s "Register now »" to join it. Have fun!
Hack me if you Can!
May be you are out of contest....:)
王大拿
YQY! ;(
Long queue for submission :(
long queue for submission in problem C:(
Midway through the exam I realized I forgot to register. I guess I'm now officially too old for this shit.
King Of Unsuccessful hack
I was trying to find the bug of someone's code but I couldn't find it :(
No coach , you wanna reach the white rate :"D
whaa,u're trying to make a big leap in rating changes
He is trying to do Bus
Hah! Did you find anything wrong with my Div2.A solution? =)
Hey man , he qualified for ICPC , but i think he has a problem with Mike Mirzayanov
too late :) worse
Mhammad1 Well, we didn't get the visa for ICPC this year, but at least now you are famous :D
Stress testing isn't a good strategy for hacking.
Problem difficulty is like AACCE lol
How to solve D?
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.
problem title: "E. Verifying Kingdom"
problem statement: described formally — no story about a kingdom or something :D
same thing with some other problems :D
I think the writer's goal is to increase letters V and K as he can :D
didn't enjoy the contest :p
quite a boring one
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
Problems statements are Short and Clear.
Nice Problem Set.
Thank You.
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?
Logic for Div2 C please?
Binary Search
More details please.
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.
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
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 .
How did you choose the upper limit as 1e18.
Randomly. I did the same thing and payed for it :)
I chose 1e18 and it passed systests.
mine for 1e15 is TLE, but 1e10 accepted with 93ms
I think the upper limit is
1e10because the worst case that I can think of is you haven = 1e5devices, The charger is as fast as possible but doesn't make the devices work for infinityp = 99999, each device uses minimum amount of powera[i] = 1and has max starting powerb[i] = 1e5. Now the time needed will be1e10because you originally have1e10power in total (summation ofb[i]) and each second you lose one power in total (lose1e5, one for each device.. and regain99999from the charger) so it will take you1e10seconds to run out of power.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.
How to solve Div2 D?
Point-line distance
I know that it is minimum altitude of a triangle, but checking all N^3 triangles TLEd.
For line (i, j), just check point i + 1 and j - 1
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.
Did you find ur mistake? I have wr on test 4 too.
Yeah, it was precision error, changing double to long double gave me AC.
I got AC checking only adjacent triples i,i+1,i+2
Can you elaborate it with some details.
From what point? To which line?
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)?
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.
Could D be less than (distance from one point and line between two its neighbouring points) / 2?
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).
How to solve Div 2C?
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.
Similar problem to Div.2 E: http://codeforces.me/problemset/problem/487/C
How did you find it?
Just googled "prefix product sequence".
I found it also, when I searched for prefix product. I didn't know what does it mean, so I just googled it.
Well, it looks like googling that problem didn't help anyone. That's a relief for me :)
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.
But I remember the problem and its solution without googling :)
you are google it self ;)
Imho, that problem differs from today's very much
I think user sp_502 has cheated because he hacked a same user for 10 times
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.
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
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?
True
I did nearly the same and passed pretests. Did you consider n,1,2 and n-1,n,1?
Maybe you have forgotten about first and last points, because my solution is same.
You also need to to halve the distance between two consecutive points.
Edit: That distance is actually never optimal. Explanation Here.
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.
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.
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).
Ah right.
I didn't consider this... And passed pretest???
Beacause you're so WEN3 that you needn't think about it.
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?
I did the same thing and it passed. Maybe you initialized the answer wrong. The maximum possible distance was 10^9*sqrt(2)/2.
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...
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)
I think you just have to print answer with greater precision.
Mine failed pretests with double, but passed with long double in C++11.
How to solve Div. 1 C ?
https://math.stackexchange.com/questions/2149600/prove-ax-equiv-b-mod-m-iff-b-equiv-0-mod-gcdm-a/2149624
How does it help us?
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.
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
What does the symbol
|mean?a | b means that b is divisible by a. Sorry, in my country it is a recognized notation
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 sequence
Here is my submission
Did you noticed that names of problems starts with "V" and "K" letters?
on both languages!
Yeah, that is really cool!
That feeling when you finally fix the bug and your solution runs ... one minute after contest ends ...
same
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)..........
Сначала прочитал название задачи C как "Возмутительный Контест". Видимо, не зря
the same code for div 1 B got WA 4 by using C++ 14 and passed pretest by C++ 11.
the cf is too hate you
Maybe you need better online judge！
I think you will be downvote...hahahahah
Do u know any reason y??
not know yet, waiting for system test to see dataset
What was your precision set to?
And y did u submit so many times even after getting ac.Just out of curiosity.
out of curiosity haha
I hope I won't be fst.....
Is div2E/div1C just brute forcing on factoring of m then using dp to find the chain of factors the give the largest answer?
It doesn't look so. What will be the chain of factors for this input:
3 102 9 11 -> 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
I am sorry, but I don't understand what you have written.
What is this?
1 -> 2 -> 10That'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.
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.
1 -> 2 -> 10?1 -> 2 -> 10help us find the final sequence of length 6?You have: (btw the divisors are 1, 2, 5, 10)
0, 3, 4, 5, 6, 7, 8
divide those numbers by their gcd with m
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).
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)
Div.1 D makes me hate mathematics.
Seems like he used the technique described by the bots in previous round :3
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 ?
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
again, div2C/div1A, like some problems in previous contest, is containing 100 kilometers long input file
Did someone come up with an upper bound for the answer in Div2 C ?
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
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 .
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.
what are hack case for div2 A ?
KK
Any tip for Div1 D?
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.
Fast Subset Convolution?
Fast Subset Convolution.
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).
undoubtedly today's best performer
Zoomed screen 300%, still can't see picture :D
He got -72 hacks, and -2192 point overall, with 3 solved problems.
Бан?
http://codeforces.me/contest/772/submission/26422584 Объясните, кто-нибудь пожалуйста, как тут затлиться могло? Все другие тесты такого размера проходятся за копейки времени.
Думаю это из-за right-left>eps.
У тебя бесконечный цикл.
OMG, so many WA's for problem Div.2 C
Div.1 — A. Test — 74 :(
me too!!
I think my INF is not big enough.
I WAed on the same test case, but the my issue is that my INF is too large. Haha.
Same :(
I added checking -1 case separately (the sum of all the powers shouldn't exceed p) and then got AC
My mistake was using 1e14 as upper bound instead of 1e13. Bad luck.
Its showing failed system case for div2 D for all users, but displays accepted when clicked on it.
Paradox
Lol ;P
Fatalities everywhere in Div2 C and D 0_0
At me too :(
Why does the system say my problem d failed system test, but when i click inside it said i got accept?
what happened on div2.D?
Bug on standings page.
EDIT: Fixed now.
EDIT: Unfixed :P
EDIT: I think it's fixed for good now.
Nope:)
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
At a moment the bug is fixed.
But now it is buggy again...
hope to be fixed as fast as it can...
Ребята после сис. тестов написано, что фулл, а в таблице не засчитывает и пишет -1, исправьте
Что случилось с тестером по задаче Div2 D? У меня вердикт — полное решение и при этом -1 в общей таблице.
То же самое с Е
Why this submission stuck in pretest 9? :D
UPD: FIXED
10^8 floating operations, 2s. Not sufficient. TLE on testcase 42 :/
I want to cut my veins...
Please don't! It is our own bad experience that is a lesson to us not to repeat our mistakes.
It was just an expression for being mad. Anyways, I don't even know what was my mistake. 26422821
You stop when
toandfromare 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. :)
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.
In Voltage Keepsake problem judge is rounding up, and i am outputing more precise and getting wrong answer for that :)))
How come got accepted problem D and it's counted as a "Failed System Test" in the final standing.
Bug in standing page .
I have this problem , too. I got accepted D and it's counted as a "Failed System Test" in the final standing
Got it, Thanks ^^
У меня, в посылке 26427063 засчитано решение D на полных тестах (409 Div 2), тем не менее в результатах оно значится -1, при этом, при клике на этот -1, я вижу единственную строку с полным решением. Это нормально?
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 :(
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 :(
I found, only 1 person got accepted by Java in Div1A. Most contestants got failed at test 71. Is this case valid?
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 :(
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...
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? :^)
This is a bit unexpected for me too, and we'll look into it.
Test 71 is generated by the following code:
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?
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.
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 ?
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.me/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.
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.
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.
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.
I checked some solutions from the top of the leaderboard, and they fail if compiled with
-ffloat-storeflag. Nothing new, though.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 workstells, 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.
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.
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.
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!
Got AC with Java 8 & binary search: 26437377.
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?
I believe that 'that green guy' got his solution on problem D accepted.
What is wrong with this solution http://codeforces.me/contest/801/submission/26427548 for Div2C / Div1A
you have to output -1 if it is possible to keep all devices on indefinitely, you didn't do that.
I did, check line 53. If it is possible even at max_limit, I output -1
t*a[i] can overflow, when t = 1e24.
isn't the range of double much larger than that?
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 :/
Always use setprecision.
what's wrong !!?
Two problems double WA , long double after contest AC , i hope that's not intended.
how much time will it take to update ratings?
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.
In div2 C , what happens wrong when we compare the answer to the upper bound in binary search for the infinity case? 26437983
Can someone explain to me why my solution for Div.2 C fails with binsearch upperbound 1e11 or 1e9 but gets AC with 1e10 ?
It fails with 1e9 because it is too small and fails with 1e11 because you use the == operator. Never use that thing with doubles.
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?
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.
Thanks, I got it)
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?
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.
How do we resolve this issue?
Iterate a fixed number of times (like 100-200) or use relative error
Can you please point out what edit i need to make in my solution.
http://codeforces.me/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)
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
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.
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?
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.me/contest/801/submission/26438478
You're fine only with GNU c++. With MS c++ I also had precision problems using the same code.
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
Similar problem for me. Got WA using MS C++ (26438473) and AC using GNU G++ (26438539). This is a really bad behaviour.
Lol, such a simple solution for div2C, and I spent a hour for solving it in much more complex way
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)?
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.
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?
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.
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.
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?:)
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.
Please help: http://codeforces.me/contest/800/submission/26441326
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 :
and in WA code I have:
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
I had to face the similar problem.
WA
AC
Can't understand which statement caused the overflow, if any.
Strange behavior with my submission:
Submited under MS C++ during the round and got WA71: http://codeforces.me/contest/772/submission/26418943
The same code (only casting to double in printf) submited under GNU G++ 14 get AC: http://codeforces.me/contest/772/submission/26460846
How is it possible?!
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)
How does it relate to the fact that under GNU G++ 14 everything is OK?)
But anyway it's WA71 http://codeforces.me/contest/772/submission/26461442 :D
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.
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
Try to submit in g++14, double is more precise. I guess the solution lost precise in (thisAns * v[i].first).
Same result.. WA
Hello... Why I don't rated in this contest I solved a question A
My team submited this code under MS C++ for problem B in 22 min of the Round 2: http://codeforces.me/contest/772/submission/26422281 — got WA 4.
The same code submited under GNU G++ 14 get AC: http://codeforces.me/contest/772/submission/26461048
IDK what's wrong with MS C++ in codeforces, but with problem A http://codeforces.me/blog/entry/51577?#comment-355114 — my team lost 1390 points and, ironicaly, 100 place. :P
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):
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.
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.me/contest/772/submission/26419872
http://codeforces.me/contest/772/submission/26419872
You 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.me/contest/800/submission/26463062
But if we rework a bit f(...) function with Kahan summation approach — we get AC, even on MS C++. See this attempt: http://codeforces.me/contest/800/submission/26463142
The main problem is in this line:
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.
MS C ++ makes me sad now :)
Thank you for clarifying.
hello world! :)
Very quietly I take my leave
As quietly as I came here;
Quietly I wave good-bye
To the rosy clouds in the western sky.
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)
The unpaired "(" in D makes me feel puzzled and make mistakes in the first code