CodeChef invites you to participate in the December Cook-off 2014.
Time: 21st December 2014 (2130 hrs) to 22nd December 2014 (0000 hrs). (IST — +5:30 GMT) — Check your timezone.
Registration: Just need to have a CodeChef user id to participate.
New users can register here.
Problem Setter: Rubanenko
Problem Tester: ddldyj237
Russian Translators: vadimmm & Rubanenko
Editorialist: fchirica
Mandarin Translator: MinakoKojima
It's my third CodeChef Cook-Off. The contest is quite balanced and I think that this contest will bring you something new and unusual. Don't be afraid of being creative! As always I'd love to hear from you after the competition is over.
Special thanks go vadimmm for discussing the problemset.
Don't forget that top ten contestants will receive CodeChef T-shirts!
UPD
Contest has started with some lagging and delays. I'm sorry for that and, unfortunately I could do nothing with it.
Strongest active ACM ICPC Belarus competitor kostya_by takes the lead! uwi has two penalty submissions in margin.
uwi submits the last problem from the first try and wins the contest!
dreamoon_love_AA seemed to be trying to do the same as he does on codefoces these days, but the problems were too easy, so he didn't succeed and accidentally solved all of them. Congratulations!
By the way, it seems that I forgot to say that you should be not only creative, but attentive as well..:)
I'm sorry that the problemset was too easy for some contestants. Problem RRPLAYER turned out to be known and easy. As you will see from the editorials, I had more complicated(and I thought cool) solution. I'm really sorry and probably won't set public contests in future :(
Bump: starts in a minute! Hopefully I won't need the "Keep calm and spam F5" pic...
UPD: Okay, too late for pics anyway.
Your hopes are shattered ! -_-
I am getting 502 bad gateway.
Seems like you will :D
accidently pressed F4 instead of F5 :P
Thanks for that reminding; original announcement had wrong timeenddate link, so i was sure that it is still almost an hour left to the beginning, when i saw your message few minutes after contest has started:)
I can't download the CodeChef.
Does somebody have the same problem?
UPD: All works!
Me, too :/ 502 Bad Gateway
Strongest active ACM ICPC Belarus competitor kostya_by takes the lead!
Sad news for tourist...
In ACM ICPC he represents Russia, doesn't he?
I really did not like your sense of humor : 107 + 7
But other problems were interesting especially "Jam". I used parralel binary search. What was the intended solution?
There is an easier n1.5 approach. What data structure did you used to use to do the binary search?
If one implements something that allows to add progression and ask for minimum over the entire array, then he does not need binary search at all.
i've used 2 fenwicks that allows me to update range and query an index.
By the way, did you do something special to avoid overflows? Since x, y < = 109, applying first, say M / 2 updates would cause an overflow.
No, i did not noticed it exceeds 1019. It looks like test-data has not got this kind input right?
I have to mention that problem statement says that x, y < = 105.
There are also lot of other problems with this statements in this contest — indexes in statement of Matrix Again were fixed at some moment late after contest start, and input format of problem Jam still does not say anything about line with values of B[i] :) And also limitation 0 < = l, r < = N looks a bit strange. Thanks for a contest, but please prepare better statements next time.
I had O(N·logN·logM) solution for RRJAM. It seems like some AC solutions have that complexity too. Was there some special case for that problem that caused my solution to run infinitely? I ran a couple of big tests and it seems like it should pass in time. (In fact, I had 2 solutions with that complexity, one with parallel binary search, and the other with persistent lazy segment tree, and both TLE)
Solution link: http://ideone.com/01kXO2
My solution with persistent segment trees (and the same time complexity as yours) got accepted, so I don't think it was intended to get TLE.
First Cook-Off where I solved all the problems :) Don't know if I have improved or your problems were easy :P
"Problem RRPLAYER turned out to be known and easy."
I did not know the problem, but it was rather easy to see the pattern between answers for different n's.
This problem even have it's own page in Wikipedia.
Кто-то из Украины получал футболку codechef в последнее время?
Можете рассказать детали? Эти ребята должны мне уже довольно много футболок:) О большинстве из этих футболок мне вообще ничего не известно:) Они доставляют их с помощью DTDC — у которых на сайте в списке стран Украины нету. По тем нескольким футболкам, о которых, после переписки с админами, пришли сообщения, и которые пробиваются через tracking — указано Destination где-нибудь в пределах страны, выставлено время доставки, но как и где их забрать — я не понял. С кем сотрудничают эти DTDC, и к кому идти за посылками — не нашел; админы codechef тоже ничего особо не знают. Как я понял, для них мое сообщение несколько месяцев назад о том, что футболки не доходят, и не только мне — стало новостью:) Остальным уже вроде бы доходят, а я до сих пор в ожидании.
Мне уже писали здесь в переписку вопрос — где и как забрать футболку; а я и сам не знаю. Сейчас еще самим DTDC напишу:) Но, может быть, кто-то быстрее поможет здесь.
How to use dp solution for n equals 3000. My dp implementation has precision problems when n approaches 3000.
You were allowed to have 10 - 1 relative error. So for 3000 answer is about 25000 and it was ok to output 23000.
It turns out my implemtantion had a bug.
The problems were indeed easier than usual — you can see that by the larger than usual number of contestants who solved all of them (and the speed with which they solved all the problems). But it was a good contest. I don't think that the fact that the problems were easier is a good reason to stop setting public contests in the future.
Can someone explain a dp solution to RRPLAYER (other than the one described in the editorial)? According to the editorial one needs to pre-compute values but many solutions didn't do that.
I just become stupid in the first hours that think problem Servers is a very very hard problem and try to use some strange method to solve it...