CodeChef invites you to participate in the July Cook-off 2014.
Time: 20th July 2014 (2130 hrs) to 21st July 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: msh_shiplu
Russian Translator: Witalia
Editorialist: PraveenDhinwa
Mandarin Translator: gediiiiiii and MinakoKojima
It's my second CodeChef Cook-Off. I believe this round is more interesting than my first one and hope you'll enjoy it! I think almost every problem can be solved by almost everyone, so everybody has a chance to place in top ten and win a T-shirt from CodeChef.
Problem statements are dedicated to Ukrainian National Team at IOI — Scorpy, NegaTeeF, seland and Omelianenko. I had a pleasure to help them with preparing for the IOI and they invented a nice solution for one of the problems in this contest! I'd also like to thank vadimmm for discussing and sharing ideas about the problemset.
As you will see from the editorials, every problem has at most 50-60 lines neat solution. I'd love to hear from you about your impressions, especially your solutions for RRDAG and RRTREE. I also wonder whether there exists O(N2) solution for RRFRNDS. During the setting process I tried to invent such solution, but eventually ended up with O(N3) solution with constant optimization.
It was a great round, thx for preparing problems. But trouble with long testing was annoying.
Round is not ended, it is prolonged for 1 hour. However, there are some problems with connection.
Edit: Now everything is OK.
Thanks, but you have about 35 minutes to submit all the problems!
Finally I solved "Friends".)) Thanks for this great round!
What complexity do have on problem "Friends"?
I solved Friends with bitsets, pls disqual me.
I guess almost everybody did, since it was intended solution :)
Oh my god! O;
Oh come on, so jury doesn't have a proper solution for it. Why did you decide to have n=2000 then? It kills some of the bitset solutions (e.g. with Java's built-in bitsets), and does not kill others. If you wanted O(n3) to pass, you should've made the constraints way smaller.
Hmm, my java solution based on built-in bitsets passed.
Well, obviously if it's close to TL, it depends on luck. That's why general guidelines are "TL >= max(2 * time of jury java solution, 3 * time of jury C++ solution)". Just for the record, my TL solution is here.
Problem in your solution is that you use O(n^3) memory instead of O(n^2)...
It doesn't. At any point of time it is O(n2) memory, allocating bitset n2 times shouldn't consume much additional memory because GC/allocator implementations are smart. And I bet identical code in C++ would pass (and you wouldn't say that it uses n^3 memory, even though it allocates O(n) memory n^2 times). Besides, locally it was quite fast.
Btw, do you know a way to solve the problem with Java using only built-in bitsets (i.e. BitSet or BigInteger) without allocating n^2 bitsets (and without accessing internals of bitsets, of course)?
I agree about c++ solution:)
Just don't create BitSet s inside your cycles (create it once and clear it inside loop and OR it with g[i]) and also you can optimize your solution in 2 times (you can look only on pairs with i < j).
Yes, yes, I know that it can be optimized a lot, it is far from being optimal :) I'm just saying that n=2000 is too much for intended O(n3) solution, and the TL is quite tight.
Maybe you are right and I'm sorry for this issue. I implemented bitset myself for this problem and set two times my running time as TL. Since it was ACM-style contest, I hope you wasn't affected very much :(
All my solutions are written in Java and have at least two times margin.
My O(N3) (see my code, it's so simple that I don't need to explain it) passed.
UPD: I know I shouldn't be asking anymore and just take it as trolls being strong on CF, but I'll ask anyway: why the downvotes?
I hate the concept of downvote. I only downvote when something is out of context. Otherwise either I upvote or left it as it is.
I also dont know why you got so many downvotes :(
Wow, till now I was sure that this is intended solution))
Don't know whats wrong with my submission for Friends ! O(n^2) gets TLE! but other people's O(n^3) doesn't :(
Could do you describe it? I was unable to find such solution.
Here is AC O(n^3) : http://www.codechef.com/viewsolution/4359971 Here is TLE O(n^2) : http://www.codechef.com/viewsolution/4358215
Isn't it the second on O(n^2)
Your bfs runs in O(M) time which is O(N2) in this problem. So you also have O(N3) solution.
It's not O(N2). BFS gives to you O(N + M) operations. Given that M ~ N2, we have O(N3) solution.
I wonder what's the jury soultion for "Present for Andrii". My (accepted) solution is O(n3) (with bitsets), but I hope jury has smth with proper asymptotics. Is is solvable without finding transitive closure? Or did jury implement O(n2.5) madness for it? (if so, I wonder whether it is faster than bitsets?)
There is a neat O(N2) solution.
Oh, nice! Why did you give such a small N then? Your solution would work for n=10000, which kills all transitive-closure-finders like me.
Because either input or output would be quite massive then. It's also almost impossible to upload more than 8 MB file on CodeChef...
You could've asked to compute hash of the output; and give graph not as a matrix, but as a list of arcs (which doesn't help bitset solutions).
Good idea. I wish you helped me with preparing this contest T_T
This was something like "bitset round".
It seems that hardest 3 problem have bitset solution.
UPD mistakenly russian.
This was something like "bitset round".
It seems that hardest 3 problem have bitset solution.
Only one intended solution requires bitset.
No offense. It was fun. Sometimes i feel good when intended solution was not bitset but mine was :).
For me, it was an "additional factor of N in complexity" round. I had that for the 3 non-trivial problems. In short: WAT.
Long queue building up in the middle of the contest, testing completely nuked and contest extended: commemorating IOI 2013 day 1? :D
Just too bad this Cookoff couldn't be on 8th...
Hope somebody from IOI staff participated and I took revenge :D
:)
Thanks for editorials, this time they are well written and easy to understand)
You should thank PraveenDhinwa :)
Presenting editorial in form of dialogue is great idea)
Yeah, it's also his idea.