Привет, Codeforces!
27 ноября 2015 года в 18:00 MSK состоится второй учебный раунд Educational Codeforces Round 2 для участников из первого и второго дивизионов.
О формате и деталях проведения учебных раундов я писал уже ранее. Также об учебных раундах вы можете прочитать здесь.
Раунд будет нерейтинговым. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. На решение задач у вас будет два часа. После окончания раунда будет период времени длительностью в один день в течении, которых вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования. Таким образом вы можете локально тестировать решение, которое хотите взломать, или, например, запустить стресс-тест.
Подготовкой раунда занимался я, Эдвард Давтян. Идеи задач были снова придуманы совместно с MikeMirzayanov.
На сегодняшнем раунде вам будет предложено шесть задач. Надеюсь они вам понравятся.
Good luck and have fun!
UPD: Большое спасибо PrinceOfPersia за тестирование задач, а также за Delinur за проверку моего плохого английского.
UPD2: Первая часть соревнования завершена, надеюсь всем понравились задачи. Теперь можете ломать соперников :-)
UPD3: На этапе взломов было выяснено, что верные решения многих участников оказались численно неустойчивы к большим ограничениям. В том, числе решения которые использовали тип double, а не long double ошибаются в ответе в девятом знаке. В связи с этим было принято решения ослабить требования на точность от 10 - 9 до 10 - 6. Вскоре все решения и взломы будут перетестированы. Это никак не повлияет на правильные решения они как и раньше будут получать Accepted.
UPD4: Разбор готов.
UPD5: Раунд закончился. Решения протестированы на дополненном наборе тестов. Результаты окончательные.
i will invite my friends to this round to improve their skills :D :D
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?
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";tocout << "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.thanks a lot!!
when you tryna hack but you get trolled since "#define int long long"
I once did that, got error
But, if you define the macro inside main, and be careful to define other functions below main, then it will be fine.
An opportunity to compete without tension... ~-20
UPD1: (unless you get lots of down votes!) ~-30
UPD2: I wish I could delete my comment:( ~-40
UPD3: TNX the recent few ones who gave me up vote:) ~-30
UPD4: I can't believe this!!! :D ~+5
UPD5: Because of your forgiveness I give every comment an up vote;) ~+20
hi again!! 14453627 i tried to hack this. it got accepted but i think it should get time-limit exceeded what do you think?
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.
(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?
Thanks. These rounds are great! But I can't see any editorial :(
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.
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.
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?
add button "Get hint" (or even different levels of hints)
if you use it, the accepted solution will get some penalty
of 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
people cheat even in virtual participation.
No matter how hard you try admins won't accept it!
why not? it is easy to implement
one 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
Educational rounds are very good for IOI. I like them!
Why are these called educational rounds? For me, all rounds are educational!
Because these rounds differs from other.
Other CF rounds are really non-educational.
it's unrated,sad...so i can't join . hahaha
I'm new in Codeforces.But,**what is hacks**!?
Check out this comment by kingofnumbers.
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!
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
If regular Div 2 contests have the same difficulty as Educational Rounds, it would be fantastic.
Я сделал перепосылку, но в таблице штрафа не добавилось. Должно же было? Последнее решение вроде как должно учитываться?
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?!
Relative error is small though. The hack is successful only if both absolute AND relative error exceed 1e-9.
I didn't notice the "or" in the statements and spent the whole contest rewriting the solution in java with BigDecimals -_-
Разве это правильный ответ?
Ответ будет считаться корректным, если абсолютная или относительная погрешность не превысит величины 10^(-9)
http://radikal.ru/fp/44fae3c7c9bd49a99465bb4b0c9e387c
Ну так относительная и не превышает 10^(-9).
Can I submit solution in next 24 hours?
You can do it as long as you are alive BUT of course it will be UNOFFICIAL
Ok. I was asking regarding whether the problems are locked for further submission or not. Thanks!
What does jury solution for D output for the following test?
It seems to me that jury expects 0 as an answer, while it's Pi/2.
It seems jury has PI/2 here.
You answered in just two minutes...!
Yep, my mistake, thanks.
I have 2 TLE and 3 AC code on E. Why it shows verdict as TLE?
На взломах 184717, 184659, 184833 выдается неизвестный вердикт.
Rejudge?
See the UPD3.
Не очень понятно зачем было делать перетестирование. Так как это не рейтинговый контест и тем более нужно было учитывать опыт прошлого educational где задача на геометрию не прошла с типом double и сделать выводы перед сегодняшним контестом.
If you can't write a correct solution, you can use mine :).
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?
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.
I don't see BigDecimal solution of you. Can you write the id of submission.
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.
Actually I see the difference only in 9th sign. Right now the precision is 10 - 6.
I will try to write the full solution though. How hard could it be?
Done: http://codeforces.me/contest/600/submission/14530777
Cool. I see the difference only in 9th digit so I think that the problem is okay.
One more BigDecimal solution by uwi: 14531957, but it differs from your (your solution as answer):
Mathematica gives
using formula (14) from here.
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.me/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.
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.
Your solution uses doubles about everywhere, so it is not "BigDecimal with very high precision".
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.
If we leave old precision all solutions will be failed. Also author solution has an error in ninth sign.
EDIT: DISREGARD THIS COMMENT.
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.
http://www.tau.ac.il/~nogaa/PDFS/lex2.pdf claims
.
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.
O(nm) solution is very simple and could be implemented in less than 100 loc. Please, read the tutorial.
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.
I'm sure Edvard is translating it.
Right, I mean to understand and to code, but not to come up.
It's ready.
Actually I think that these solution is very similar to Kuhn algorithm.
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 ofBigIntegers -- it isn't a level playing field of people who use different languages (and yes, I know, Java hasBigDecimal, 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?LOL
Nice work Adhambek caught me :))
Ninth digit. And "they".
Thanks. Fixed.
Why not make Educational Rounds rated for Div 2?
and then why not for Div 1 ?
Will all the solutions be rejudged after including the Hack test cases?
Will this contest have influence on the rating?@v@
No. Unrated contest.
thxxxxx~
_(:3rz_Sorry that I didn't notice it...
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.
Maybe this: http://codeforces.me/blog/entry/12833 ??
Cool, this seems like the explaination, thanks!
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).
My code is giving correct output for all the small test cases yet giving wrong answer on test 7 id: http://codeforces.me/contest/600/submission/14548282 can someone tell me where i am missing. I have tried to implement STL.
Отличный раунд, спасибо! Идея small to large мне вообще была не знакома до этого, хотя сама по себе очень интересная.