Edvard's blog

By Edvard, 3 years ago, translation, ,

Hi, Codeforces!

Educational Codeforces Round 2 will take place on November 27th, 2015, at 15:00 UTC for the first and second divisions. You can read about educational rounds here.

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

Round was prepared by me, Edvard Davtyan. Problems was invented by me and MikeMirzayanov.

I hope you will enjoy the problems.

Good luck and have fun!

UPD: Thanks a lot to PrinceOfPersia for testing the problems and Delinur for checking my bad English (in problem statements).

UPD2: The first part of competition is over. I hope that you enjoyed the problems. Now you let's hack other solutions :-)

UPD3: At the stage of hacking we found that a lot of correct solutions are numerically unstable, so they print the right answer with error in ninth digit. So we decided to increase the requirement for precision from 10 - 9 to 10 - 6. All submissions and hacks will be rejudged soon. It will not affect correct solutions. They will got Accepted as earlier.

UPD5: The round is over. All solutions are rejudged on full testset. The results are final.

•
• +234
•

 » 3 years ago, # |   0 Yay another educational round :) Hope for lots of knowledge :D
 » 3 years ago, # | ← Rev. 2 →   +16 hi,how can i hack solutions with generator codes? last contest i tried to hack a solution with generator code but it said invalid input. what should i do?
•  » » 3 years ago, # ^ |   +19 Your hack is invalid -- and actually, most program outputs are "invalid" in the same way (I'll explain what I mean below). All input and output files must end in a new line character. So if you change cout << "6"; to cout << "6" << endl; in your program, then it would work properly. Technically, all of the output files you produce should also end in a newline character. The reason that you don't get WA is because the checkers ignore whitespace (and are case-insensitive). But it is good practice to include the newline at the end of your programs either way.
•  » » » 3 years ago, # ^ |   0 thanks a lot!!
•  » » 3 years ago, # ^ |   0 when you tryna hack but you get trolled since "#define int long long"
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +13 I once did that, got error return value of main must be int But, if you define the macro inside main, and be careful to define other functions below main, then it will be fine.
 » 3 years ago, # | ← Rev. 14 →   +20 An opportunity to compete without tension... ~-20UPD1: (unless you get lots of down votes!) ~-30UPD2: I wish I could delete my comment:( ~-40UPD3: TNX the recent few ones who gave me up vote:) ~-30UPD4: I can't believe this!!! :D ~+5UPD5: Because of your forgiveness I give every comment an up vote;) ~+20
 » 3 years ago, # | ← Rev. 2 →   -8 hi again!! 14453627 i tried to hack this. it got accepted but i think it should get time-limit exceeded what do you think?
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Maybe you should read comments in the announcing post about this contest? Don't you think you are the first who sent this solution?By the way, yes, it's correct solution because of breaks.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 (10^5)/2 555555 and then one 6 and then ((10^5)/2)-1 777777 ===> time-limit.order of time is= ((10^5)/2)*(average order for second for = (10^5)/4)=(10^10)/8 ====>time-limit.am i right?
 » 3 years ago, # |   0 I hope the tutorials will be ready and translated after all.
 » 3 years ago, # |   0 Thanks. These rounds are great! But I can't see any editorial :(
 » 3 years ago, # | ← Rev. 2 →   +47 Will there be a proper editorial this time?Editorials are the most educational part of any Codeforces round, yet the first educational round had none. That made it less educational for me than regular rounds.The concept of educational rounds is fantastic and can help us beginners a lot, but it has to be coupled with a strong, thorough, clear and educational editorial.
•  » » 3 years ago, # ^ |   +25 Unfortunately previous time we have not decided in which format editorial should be. So there are editorial only in Russian. This time I'll write editorial myself. And I'll also translate editorial for the previous round soon.
 » 3 years ago, # |   +21 Can these problems have hints for tougher problems in the near future during the contest itself,since these are just unrated contests and meant for learning?
•  » » 3 years ago, # ^ |   0 add button "Get hint" (or even different levels of hints)if you use it, the accepted solution will get some penaltyof course, one can use the second account just to unlock and read the hints, but cheating in an unrated round doesn't make any sense
•  » » » 3 years ago, # ^ |   +75 people cheat even in virtual participation.
•  » » » » 3 years ago, # ^ |   0 people cheat even in official rounds, so why care virtual?
•  » » » 3 years ago, # ^ |   0 No matter how hard you try admins won't accept it!
•  » » » » 3 years ago, # ^ |   0 why not? it is easy to implementone also could implement the idea that the problem timer starts after you open it (like on tc), and that the hint automatically comes up after you can't solve the problem for half an hour or so :)and we just ignore 0.1% cheating contestants since the round is unrated anyway
 » 3 years ago, # |   -19 Educational rounds are very good for IOI. I like them!
 » 3 years ago, # |   -25 i will invite my friend to this round thanks codeforces
•  » » 3 years ago, # ^ |   0 why is votes down ?
 » 3 years ago, # |   +3 Why are these called educational rounds? For me, all rounds are educational!
•  » » 3 years ago, # ^ |   0 Because these rounds differs from other.
•  » » 3 years ago, # ^ |   0 Other CF rounds are really non-educational.
 » 3 years ago, # |   +8 I'm new in Codeforces.But,**what is hacks**!?
•  » » 3 years ago, # ^ |   0 Check out this comment by kingofnumbers.
•  » » 3 years ago, # ^ |   0 during the contest only a few pretests will be run on your code... So others can give tests to try to show that your code is wrong. if they do a successful hack your submit will be unsuccessful or vice versa!
 » 3 years ago, # |   +3 some thing wrong with display times, I am getting 02::min::sec for registration time and 00::min::sec for before contest time please see to it
 » 3 years ago, # |   +14 If regular Div 2 contests have the same difficulty as Educational Rounds, it would be fantastic.
 » 3 years ago, # |   +6 I tried to hack a solution with a hack ID = 183673 the jury's solution seems to output 3141592653589793300.0000000000 but the true value is 3141592653589793238.4626433832795 the absolute error is of course much more than 1e-9?!
•  » » 3 years ago, # ^ |   +5 Relative error is small though. The hack is successful only if both absolute AND relative error exceed 1e-9.
•  » » » 3 years ago, # ^ |   0 I didn't notice the "or" in the statements and spent the whole contest rewriting the solution in java with BigDecimals -_-
 » 3 years ago, # |   +3 Can I submit solution in next 24 hours?
•  » » 3 years ago, # ^ |   +3 You can do it as long as you are alive BUT of course it will be UNOFFICIAL
•  » » » 3 years ago, # ^ |   +3 Ok. I was asking regarding whether the problems are locked for further submission or not. Thanks!
 » 3 years ago, # |   +3 What does jury solution for D output for the following test? 0 1000000000 1 0 0 1000000000 It seems to me that jury expects 0 as an answer, while it's Pi/2.
•  » » 3 years ago, # ^ |   +3 It seems jury has PI/2 here.
•  » » » 3 years ago, # ^ |   0 You answered in just two minutes...!
•  » » » 3 years ago, # ^ |   +3 Yep, my mistake, thanks.
 » 3 years ago, # |   +3 I have 2 TLE and 3 AC code on E. Why it shows verdict as TLE?
 » 3 years ago, # |   +1 Rejudge?
•  » » 3 years ago, # ^ |   +20 See the UPD3.
•  » » » 3 years ago, # ^ |   +20 Не очень понятно зачем было делать перетестирование. Так как это не рейтинговый контест и тем более нужно было учитывать опыт прошлого educational где задача на геометрию не прошла с типом double и сделать выводы перед сегодняшним контестом.
•  » » » 3 years ago, # ^ |   -7 If you can't write a correct solution, you can use mine :).
 » 3 years ago, # |   +19 I've sent a submission for D in Java using only BigDecimal with very high precision yet it gets a wrong answer. Are you sure of the judge's answer precision?
•  » » 3 years ago, # ^ |   +3 I wrote BigDecimal solution too. On test 38 it gives 0.33492209274623239922 while my original solution gives 0.33492209274556042825 and jury solution gives 0.33492207527160644531. It is clearly jury solution that does not have enough precision.
•  » » » 3 years ago, # ^ |   +3 I don't see BigDecimal solution of you. Can you write the id of submission.
•  » » » » 3 years ago, # ^ |   0 It doesn't work in all cases, so I didn't sent it. I was lazy and implemented only arctan (and only for small arguments) instead of atan2.
•  » » » » » 3 years ago, # ^ | ← Rev. 4 →   0 Actually I see the difference only in 9th sign. Right now the precision is 10 - 6.
•  » » » » » 3 years ago, # ^ |   0 I will try to write the full solution though. How hard could it be?
•  » » » » » » 3 years ago, # ^ |   0
•  » » » » » » » 3 years ago, # ^ |   0 Cool. I see the difference only in 9th digit so I think that the problem is okay.
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 One more BigDecimal solution by uwi: 14531957, but it differs from your (your solution as answer): Input -99999999 0 100000000 99999999 0 100000000 Output 37712.36171985108000 Answer 37712.361606713992089280270034371253587031800000000 Comment wrong answer 1st numbers differ - expected: '37712.3616067140', found: '37712.3617198511', error = '0.0000000030' 
•  » » » » » » » » 3 years ago, # ^ |   0 Mathematica gives 37712.3616067139920892802700343712535870319630927354351722357447180926 using formula (14) from here.
•  » » » » 3 years ago, # ^ |   0 I found a bug in my previous BigDecimal solution. It didn't matter due to small angle. The new version works in all cases (hopefully). http://codeforces.com/contest/600/submission/14530815 . It was not easy to implement arctan of large argument as I thought. I wonder whether there is a better way.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 You use doubles in intermediate calculation. Your solution is not precise enough because of that. My fully BigDecimal program gives 0.00188342316684821115 on test 36.
•  » » 3 years ago, # ^ |   0 Your solution uses doubles about everywhere, so it is not "BigDecimal with very high precision".
 » 3 years ago, # |   +41 I dislike the decision to lower precision requirements. It would be interesting to test different solutions on really hard tests, but now there's no such option.
•  » » 3 years ago, # ^ |   +18 If we leave old precision all solutions will be failed. Also author solution has an error in ninth sign.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 EDIT: DISREGARD THIS COMMENT.
 » 3 years ago, # |   0 What is the expected solution to the F problem? I have a O(k*m) solution, where k is the maximum degree of a vertex, but this solution doesn't seem like a solution for a codeforces problem.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 The round is educational so it is not unexpected that the solution is hard.UPD. Never mind, O(m2) is enough to pass (unless someone provides a good testcase which looks a hard enough task by itself).UPD 2. ...and O(m2) can be further optimized to O(nm) but it is not needed here.
•  » » 3 years ago, # ^ |   +5 O(nm) solution is very simple and could be implemented in less than 100 loc. Please, read the tutorial.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 The tutorial is available only in Russian for this problem. By no means is this solution simple. Easy to code -- yes. Simple to come up with -- no.
•  » » » » 3 years ago, # ^ |   0 I'm sure homo_sapiens is translating it. Right, I mean to understand and to code, but not to come up.
•  » » » » » 3 years ago, # ^ |   0 It's ready.
•  » » » » 3 years ago, # ^ |   0 Actually I think that these solution is very similar to Kuhn algorithm.
 » 3 years ago, # | ← Rev. 2 →   +25 After seeing the last 2 education rounds where many people are having precision issues, I wonder what people's thoughts are about the level of precision required in some problems. It is obviously a trade off, because as a problem setter, you want the precision to be small enough that an approximation algorithm won't work, but on the other side of the coin, does it really add anything to require the precision to be exceptionally small?As a problem setter, I can tell you that it is hard work to prove that my solution is correct when using floating point precision. I normally end up coding it in Maple with ~500 digits of precision to ensure that my C++ solutions are accurate enough. Personally (as a problem setter), I try to avoid any problem that requires the use of long doubles for the same reason I avoid the use of BigIntegers -- it isn't a level playing field of people who use different languages (and yes, I know, Java has BigDecimal, but most would easily admit that it is a pain to code using it). I'm curious to hear other people's opinion: does it really add anything to contests to ask for precisions of 10 - 9 rather than 10 - 6?
 » 3 years ago, # | ← Rev. 2 →   +22 hack owners hacked them selves
•  » » 3 years ago, # ^ | ← Rev. 2 →   +19 LOLNice work Adhambek caught me :))
 » 3 years ago, # |   0 so them print the right answer with error in ninth sign Ninth digit. And "they".
•  » » 3 years ago, # ^ |   0 Thanks. Fixed.
 » 3 years ago, # |   -7 Why not make Educational Rounds rated for Div 2?
•  » » 3 years ago, # ^ |   0 and then why not for Div 1 ?
 » 3 years ago, # |   +8 Will all the solutions be rejudged after including the Hack test cases?
 » 3 years ago, # |   0 Will this contest have influence on the rating?@v@
•  » » 3 years ago, # ^ |   0 No. Unrated contest.
•  » » » 3 years ago, # ^ |   0 thxxxxx~
•  » » » 3 years ago, # ^ |   0 _(:3rz_Sorry that I didn't notice it...
 » 3 years ago, # |   0 Hi,After struggling for a couple of hours to solve problem B I found out something very interesing, the Arrays.sort method with the input from the 20-th test case take more than 2 s ( which clearly is not normal ), after switching to Collections.sort it got Accepted without any problem. I'am very curious what is the full input for the 20-th test case ( just the first line ) because this really seems as a serious performance issues. Thanks. Dan.
•  » » 3 years ago, # ^ |   +5 Maybe this: http://codeforces.com/blog/entry/12833 ??
•  » » » 3 years ago, # ^ |   0 Cool, this seems like the explaination, thanks!
•  » » » 3 years ago, # ^ |   0 Well, I believe it's an open question if one wants such tests to be in a fixed test set for the problem. It's perfectly OK for hacks. I always thought that antiqsort should not be in jury tests. But the fact that the standard implementation uses it changes something.I'd rather put such tests in training test sets and avoid them in official competitions (probably CF rounds either since someone anyway will hack this).
 » 3 years ago, # |   0 My code is giving correct output for all the small test cases yet giving wrong answer on test 7 id: http://codeforces.com/contest/600/submission/14548282 can someone tell me where i am missing. I have tried to implement STL.