### NALP's blog

By NALP, 9 years ago, translation,

Hi to all!

A few hours later you're lucky to participate in Codeforces Round #159 for Div.2 participants, but traditionally the others can take part out of the competition. It has been prepared by me (NALP), Ivan Fefer (Fefer_Ivan), Pavel Holkin (HolkinPV), Vitaly Aksenov (Aksenov239) and Gerald Agapov (Gerald). Also we express thanks to Mary Belova (Delinur) and Mike Mirzayanov (MikeMirzayanov).

Traditionally I wish good luck, accepted solutions and successful hacking attempts for you!

UPD: Today it is decided to use dynamic scoring system. But the problems will be sorted from low difficulty to high by authors' opinion!

UPD: The contest finishes, congratulations to the winners!

1.Leonidas

3.Dakurels

4.ytqiaqia

• +86

 » 9 years ago, # |   -49 Thank You ! We Were Waiting for The First Contest in This Year ! :)
 » 9 years ago, # | ← Rev. 4 →   -53 Correction Required :It is obvious, but traditionally it is Round #159.In Indian culture, it is considered good to make minor mistakes when you do something good (like a small typo in the wedding card). So hope this NEW YEAR CONTEST is good for all.
 » 9 years ago, # |   -52 I can't wait to do it >_< thank u very much
 » 9 years ago, # |   -62 Nice, waiting for tutorial :)
•  » » 14 months ago, # ^ |   0 hey senior ,do u still need :)
 » 9 years ago, # |   -72 wow it seems all the comments here get negative votes. so here i am! :d
 » 9 years ago, # |   -68 happy new year and good luck :) :*
•  » » 9 years ago, # ^ |   -58 thanks
 » 9 years ago, # |   -43 C-C-C-COMBO BREAKER!
 » 9 years ago, # |   -39 Good luck to all CodeForcers :) Let's hope in a good and fun one!
 » 9 years ago, # |   -18 Problem A description was so hard to interpret. It took me more than 15 minutes to get what the problem was asking.
 » 9 years ago, # | ← Rev. 3 →   +17 In problem A , I was really getting confused through a lot of words like supply line filters , devices , sockets , electric sockets. I was really changing the symbols through and forth.I could not even understand the meaning of the problem :(. I need to improve my English.
•  » » 9 years ago, # ^ |   +12 Its not about how good your English is! The problem statement was the worst ever!!
•  » » » 9 years ago, # ^ |   0 humm...really, I've not understood too... :(
 » 9 years ago, # |   +3 how amazing testing system
 » 9 years ago, # | ← Rev. 5 →   +6 About Problem CWhy atan2() have error, but acos() is ok?PS: Oh,atan2() is ok. The error occur because cout and printf have some diff.
•  » » 9 years ago, # ^ | ← Rev. 4 →   +4 Got AC with atan2 (after contest). Here 2893071.UPD: I know who are downvoting to these comments. People who had no fun in this contest.THOSE WHO USE RUSSIAN-CF ARE LUCKY THIS ROUND.
•  » » 9 years ago, # ^ |   +7 atan2() works. May be just careful boundary crossing angles handling.
•  » » 9 years ago, # ^ |   +7 I get AC using atan2(),,
•  » » 9 years ago, # ^ |   +7 I used atan2, no trouble whatsoever. But you can just check your solution with the test data you get the error at, and find the bug.
 » 9 years ago, # |   -11 This is Contest or english lessons?,problem A is so hard who does not know english,Fuck english
•  » » 9 years ago, # ^ |   +6 Let me rephrase your question: are the problem setters foreign language experts? English is the main scientific language, too bad.
•  » » 9 years ago, # ^ |   0 It's okay. On ICPC we were calling such problems English problems. Sometimes they were two A4 papers long. But we were able to dedicate time for that, concentrate, read and sometimes solve.
 » 9 years ago, # |   +25 Hi,I believe there is a problem with the solution judging system for Problem D: Sum.My corrected submission after the round (now registered for practice) can be found at the following link: @ http://codeforces.com/contest/257/submission/2893122For test 1, which is: 4 1 2 3 5My solution output: +--+, which works, because this translates into 1-2-3+5 = 1, whereas my solution was judged WA, because the system was expecting "+++-" instead.The problem statement clearly states "If there are multiple solutions, you are allowed to print any of them."Could someone please verify this/provide me some clarification please?Thanks, Lee Wei
•  » » 9 years ago, # ^ | ← Rev. 2 →   +4 Hi, your solution outputs extra symbols (it seems with code 0) after the answer. So, problem's checker reads token <<+--+__>> (symbol _ for clarity only) and considers this token not a valid answer. I think everything is ok.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   0 Hi,Yep indeed, your judging system has no problems, the problem lies with my solution.I've tried to simplify my code, in order to familiarise myself with how putchar() and printing characters with printf("%c",...) works — see 2902859However, even though the following works on my local machine, and the custom test function on your website, it fails to pass the test 1 for the reason you've quoted. Could you enlighten me as to why this might be the case?putchar('+');putchar('-');putchar('-');putchar('+');I'm basically testing by hardcoding the answer to test 1, I've also tried alternatives like including the trailing null termination character '\0', and a newline '\n' thereafter, but it does not help at all.I can't reproduce the problem on my local machine nor on your custom test section, so I'm absolutely clueless as to what exactly is going on.Please please help.Many thanks, Lee Wei
•  » » » 9 years ago, # ^ |   0 Hi again,I've narrowed it down to the culprit for my WA to this line vector b;2902976 fails, but 2902986 succeeds.So my next question is: since my final answer is guaranteed to be exactly n characters long, why can't i initialise with vector b(n);? which means 'give me a vector of chars called b which will have a max size of n'...Thanks.
•  » » » 9 years ago, # ^ |   0 Hi,I've done further tests to narrow down the issue. It seems that if i only print a single character up to n times, instead of traversing the whole vector (which I've initialised to be max size n), i break when a counter i inserted hits n, then the solution is ACC — see 2903009.is my STL container traversal macro correct? #define TR(c,itr) for (typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)
•  » » » » 9 years ago, # ^ |   0 Yes, it seems correct. Could you show a working and a failing solution that differ not so much, or elaborate on what is wrong?By the way, vector b(n); creates a vector of actual size n, not of "max size n".
 » 9 years ago, # |   0 Can someone tell me why long double doesn't work, but same code with double gives AC? here are submits : AC : http://codeforces.com/contest/257/submission/2893207 (in this code shorten "ld" is for double, not for long double...). When I execute same TP with long double on my computer, it outputs correct result for me. And if I use cout, it truncate the last 6 digits, so I get WA again.
•  » » 9 years ago, # ^ |   0 maybe try running it in the "Custom test" option on this contest website and see if the correct output is generated as expected?
•  » » 9 years ago, # ^ |   +12 You must not print long double with printf("%lf", d); because %lf reads double but not long double. To print long double you should write like this: printf("%.10lf", (double)d);. Or you can use cout like this: cout.precision(10); cout << fixed; cout << d << endl; After cout.precision(10) and cout << fixed program will always output real numbers with exactly 10 digits after the .
•  » » » 9 years ago, # ^ |   0 I know %lf is for double, but I have used in code %llf, and it worked fine on my computer. I have tried Custom test and I have found few things. \$llf and %Lf doesn't work with gnu C++ 4.7 compiler, but If I switch compiler to Microsoft Visual C++ 2010, I get correct answer no matter do I use %llf or %Lf for long double. I have submitted WA code from previous post, with different compiler, and I got AC. :( so sad I didn't realized this before. Thanks anyway on answers. I hope this mistake will not recur.
•  » » » » 9 years ago, # ^ |   +18 in Microsoft Visual C++ long double == double. sizeof(double) == sizeof(long double) == 8 in GNU C++ long double != double. sizeof(double) == 8 sizeof(long double) == 12 That's why Visual C++'s printf works with "long double"
•  » » » 9 years ago, # ^ |   -6 http://codeforces.com/contest/257/submission/2890819check out this solution. I know the solution is incorrect, but the reason why I got WA is really surprising.I did exactly what all u told, I set the precision as 12 digits after the '.' Still answers didn't match.
•  » » » » 9 years ago, # ^ |   0 more surprises... outputs are different in codeforces and Ideone.com. following are the links-IDEONE : http://ideone.com/43Vxq6
 » 9 years ago, # | ← Rev. 2 →   0 Does anyone have any idea that how I can get TLE with GNU C++ 4.7 and AC with Microsoft Visual 2010 with the same code on both??!!!! I'm stuck on this problem for 90 mins in contest and almost missed other problems. :(((
•  » » 9 years ago, # ^ |   0 no one can answer this question?!!!
•  » » 9 years ago, # ^ | ← Rev. 3 →   +1 Mr.MikeMirzayanov answered: "Yes, the compilers are different. You may contact their developers :-)" Thanks everyone.
 » 9 years ago, # |   0 Div 2 — Problem A:My solution is giving correct output for the testcase: 5 50 6 2 1 3 1 3with output -1 on my computer and ideone:http://ideone.com/hM20Vq but giving a different answer on custom test here and hence judged wrong. Please do something about it.
•  » » 9 years ago, # ^ |   0 if(sum+(k-i-1)>=m), are you sure that you want 'i' there?
•  » » 9 years ago, # ^ | ← Rev. 4 →   +8 REP(i,0,k) If k > n, then this loop goes outside the array, so the variable sum is added an undefined value of a[n]. You can use customtest to debug directly on CF.
•  » » » 9 years ago, # ^ | ← Rev. 2 →   0 Changing it to min(n,k) gets ACC. Thanks alot for pointing this out.
•  » » » » 9 years ago, # ^ |   0 I had same issue before! I had following statementbool checked[n];Where my assumption was the default values are false. Locally it was working but in CF it's not guaranted that default values are false and you have to initialize them manually :)
 » 9 years ago, # | ← Rev. 2 →   +3 my solution is producing correct output for all the test cases,but my code is failed during the system testing on case 17,although it gives correct output -1. can anyone answer why this happened ? my solution can be viewed here
•  » » 9 years ago, # ^ |   +17 I tried it locally, it gives incorrect output 6. The issue is in your code.
•  » » » 9 years ago, # ^ |   +2 sir,I have checked on custum test indivisually only for that case. It gives output -1.
•  » » » » 9 years ago, # ^ | ← Rev. 2 →   +3 The bug is in line 15: for(i=0;i<=k;i++)Here must be no k, it must be n.
•  » » » » » 9 years ago, # ^ |   0 ohhh...thanks. Its my fault.I got it. sorry for troubling you all.
 » 9 years ago, # |   0 I wrote a solution about problem B long 3 lines in O(1) time. Looking among the submitted solution almost everyone has solved the problem in O(n) in more complicated way. I wanted to ask why, is there any case where my idea fails?
•  » » 9 years ago, # ^ |   0 Some of my friends solved it with 1 liner solution O(1) and their solutions passed the system test!I don't know how or why till now!
•  » » » 9 years ago, # ^ |   +5 The optimal strategy is the simplest one: as long as you have a choice, use the cube that gives you a point. I don't have a solid proof for this, but it's sort of the obvious way (especially given it's just problem B and those rarely involve more than brute force/greedy).How will the situation look, then? Suppose there are A cubes of the color which the first player chooses as the first cube, and B of the other, on the input. Then the adding of the cubes only gives 1 point to the player making the move, until there are no more cubes of the desired color; then, each turn only gives a point to pl. 1. From this, it's easy to see that the sooner there's only 1 color left, the more points pl. 1 gets, so A <= B. And it's just simple math from here on out.(This is just my opinion on the solution. I used the greedy approach, though, since I code faster than think so logically :D)
•  » » » » 9 years ago, # ^ |   0 Well the idea is to solve the case n = m, which is simply petya = n — 1, vasya = m. Now is easy to adapt it for the general case by adding the assolute difference between n and m to petya and thats it.
 » 9 years ago, # |   -38 Okay, here is my comment on this contest.This was the worst contest I ever played on codeforces! The problem statement of the first problem was the worst ever! More than 15 minutes of reading and I couldn't figure out what the problem is talking about!!For the second problem, it was not clear as well! Many people submitted O(1) solutions which passed the system test for non obvious reasons (at least for me!)
•  » » 9 years ago, # ^ |   +42
•  » » » 9 years ago, # ^ |   -19 huh, funny?!
•  » » 9 years ago, # ^ |   +6 Contests aren't just about thinking/coding, but also about being able to efficiently understand the prob. description (and other stuff).For my opinion on the solution of prob. B, read above.I actually liked this contest, because there weren't crazy jumps in difficulty.
•  » » » 9 years ago, # ^ |   +5 But still the statement of task A was unecessarly overloaded of test.
 » 9 years ago, # | ← Rev. 3 →   -7 edited ..
 » 9 years ago, # |   0 Will the editorial be published in English, and a link updated on this blog post please?
 » 9 years ago, # | ← Rev. 2 →   +4 editorial in Russian published here @ http://codeforces.com/blog/entry/6357, use google translate pls, at least until a translation (will it come?) arrives.
 » 9 years ago, # |   0 What about the English editorial?
 » 9 years ago, # |   0 Is there a tutorial?
 » 4 years ago, # |   0 Still no tutorial?BTW can you update the tag for problem 1 it can also be solved using binary search approach.
 » 35 hours ago, # |   0 Can't find the editorial..