By HolkinPV, 7 years ago, translation, ,

Good day)

Soon is coming Round 1 of the All-Russian Programming Championship CROC-2013. Contestants who gain a score equal to the 400-th place finisher score or greater will advance to the Round 2 (also you need to gain positive score).

Round will be held by usual Codeforces rules (with hacks and decreasing values of the problems). During the round the problems are judged only on pretests and system testing will take place after the end of the contest. The pretests do not cover all possible cases of input data, test your programs carefully.

Before the end of the round it is strictly forbidden to publish the problem statements/solutions/any thoughts and ideas about them elsewhere. It is forbidden to talk about the problems, discuss the statements, solutions and so on.

The problems were prepared by the group of authors: Pavel Kholkin (HolkinPV), Gerald Agapov (Gerald) and Michael Mirzayanov (MikeMirzayanov). I will add that our team have already prepared for you qualification round and answered the questions during the whole competition. Traditionally thanks to Mary Belova (Delinur) for translating the problems.

UPD1: The problems are sorted by increasing of estimated difficulty. The score dustribution is decided to be not standard a little bit : 1000, 1000, 1500, 2000, 2500.

UPD2: due to the large number of participants, it is decided that it will not be able to participate out the competition. For official contest participants the round will be rated.

We wish all the participants good luck and successful advance to the next round of competition.

Announcement of Croc Champ 2013 - Round 1

• +40

 » 7 years ago, # | ← Rev. 2 →   +11 Seems like really tough competition.. Did you mean under 400 amongst all Red,orange and purple coders ?
•  » » 7 years ago, # ^ | ← Rev. 2 →   -8 In order to pass to the Round 2, your score must be greater or equal to the score of any participant who placed 400-th in the Round 1 score table.
 » 7 years ago, # |   +5 Will the round be rated?
•  » » 7 years ago, # ^ |   +6 "UPD2: due to the large number of participants, it is decided that it will not be able to participate out the competition. For official contest participants the round will be rated."
•  » » » 7 years ago, # ^ |   -8 So what does a official contest participant mean?
•  » » » » 7 years ago, # ^ | ← Rev. 5 →   -15 it's rated for both Divisions.
•  » » » » » 7 years ago, # ^ |   0 I guess it means all eligible registered participants.When a Div2 contestant participates in a Div1 contest, he is considered unofficial, because although he registered for the contest, he is non-eligible to participate in a Div1 contest, and vice versa.
•  » » » » » 7 years ago, # ^ |   +5 In my view, all the participant who read the problem will be rated, as normal CF contests.
•  » » » » » » 7 years ago, # ^ |   +28 You need to submit something to be rated, be it normal CF round or competition one
 » 7 years ago, # |   0 How would the rating be calculated for both division 1 & division 2 participants ?
 » 7 years ago, # |   +15 how many rounds will this series of contests have，is there any T-shirts to give the winners ?
•  » » 7 years ago, # ^ |   -26 It seem that there's only one round.
 » 7 years ago, # |   +5 The problems will be more suited for div1, div2 or half way? :)
 » 7 years ago, # |   +21 How to register when registration is private? It seems too private for somebody to enter :)
•  » » 7 years ago, # ^ |   +3 I have the same problem. I have to register now because I will not have internet acces until the start of the competition
 » 7 years ago, # |   +9 I receive an Email tell me that I need to register on Codeforces for Round 1, but it seems that I cannot register because the registration is private. Did I really need to register or it will be done automatically?
 » 7 years ago, # |   +15 "Registration is private", does it mean that all participants who passed qualification round will get registered automatically?
•  » » 7 years ago, # ^ |   +2 Well, when I click "register now", a message box "The contest does not allow self registration" pops up. So I suppose that the registration will be automatically done.
•  » » » 7 years ago, # ^ |   0 I hope
•  » » » 7 years ago, # ^ |   +8 I hope so because our dorm cut the wired internet access at 23:00(UTC+8), 30min before the round start, every workdays and it will be very crowded at the public WIFI, which cause it crash frequently.
 » 7 years ago, # |   +8 "For official contest participants the round will be rated" ... for only the contestants the round is rated ??? am I misunderstanding ???
•  » » 7 years ago, # ^ | ← Rev. 2 →   +4 it is decided that it will not be able to participate out the competition.
•  » » » 7 years ago, # ^ |   +6 if there is no participant out of the competition then all the participants are official so now whats the need of the "For official contest participants the round will be rated" statement ? they can simply say "this round is rated"
•  » » » 7 years ago, # ^ |   +16 haha you quoted that sentence as if it were in correct English :D
 » 7 years ago, # |   0 If there is problems with the registration I suggest to open the registration durig the contest. Because not all of us can register. I am going to miss school for the competition. I will be home at the 4-5 min from the start. I will mis the competition if i don't register now.
•  » » 7 years ago, # ^ |   +8 Try to use mobliephone:(
 » 7 years ago, # |   0 @xkszltl it seem that he is using mobile phone but, the screen's of mobile are too small. so, it cause difficulty in using codeforces with mobile phones.
 » 7 years ago, # |   0 Registration is fixed now.
 » 7 years ago, # | ← Rev. 2 →   -23 Edit
•  » » 7 years ago, # ^ |   +66 Why some of you cares so much about the ratings calculations and the score distribution? Every round about ten such messages appear.What will change if your rating changes will depend on only Div-2 or both Div-1 and Div-2 coders? Won't you participate in one of these cases?
 » 7 years ago, # |   -19 put off 5 minutes?
 » 7 years ago, # |   -8 Lots of hacks specially Problem 4.
 » 7 years ago, # |   -14 Could anyone tell me what's wrong with this generating code for problem E? I kept hacking and got "invalid input". Making the right input specification is so tough :( int main() { int n = 1e5,Q = 1e5; printf("%d %d\n", n, Q); for (int i = 0; i < n; i++) { printf("%d", 100); if (i == n - 1) printf("\n"); else printf(" "); } for (int i = 0; i < n; i++) { printf("%d", 100); if (i == n - 1) printf("\n"); else printf(" "); } for (int i = 0; i < Q; i++) printf("%d %d %d\n", 1, 1, n); } 
•  » » 7 years ago, # ^ |   +8 what is error message?
•  » » 7 years ago, # ^ |   +16 Looks like you forgot to output request's type in the last for
•  » » 7 years ago, # ^ |   0 Did you mean printf("1 %d %d %d\n", 1, 1, n); in the last line?
•  » » » 7 years ago, # ^ |   0 Oops, I forgot that the 1-typed query needs three parameters. Thanks everyone :). (I need to practice generating input more regularly).
 » 7 years ago, # |   +10 Just one second to click submit button for problem E. :|
•  » » 7 years ago, # ^ |   0 And one second for my C, please :(
•  » » » 7 years ago, # ^ |   0 Thanks God! Mine was wrong :)
•  » » 7 years ago, # ^ |   0 Just one second to click submit button for my 100% corect sources for A, B,C,D,E :/
 » 7 years ago, # |   +8 What is the solution for D? Or is it just a DFS per query?
•  » » 7 years ago, # ^ |   +5 I use disjoint set, with total complexity O(K * (N + UnionSet cost)).
•  » » » 7 years ago, # ^ |   +8 How do you achieve that complexity? Don't you need to traverse the edges that are not taken? I mean, isn't it O(K * (N + M))?
•  » » » » 7 years ago, # ^ |   0 oh yes, sorry I miss calculation :). N that I wrote first, I mean is M, total edge not total vertex.
•  » » » » 7 years ago, # ^ |   0 Given M = 10000, K = 20000, will 2*10^8 survive?
•  » » » » 7 years ago, # ^ |   0 You can make it faster by pre-computing spanning forests for all edge prefixes [0..i] and all edge suffixes [i..N]. Then you only need to merge two disjoint-set forests for each query.That brings the total cost down to roughly O(N * (M + K)).
•  » » » » » 7 years ago, # ^ |   +6 How could one merge 2 DSUs ?
•  » » » » » » 7 years ago, # ^ |   0 I iterated through every (vertex: root) pair in one forest and merged them in the other forest. It seemed logical, but I have no idea if it's actually correct or not...
•  » » » » » » » 7 years ago, # ^ |   0 OK, it seems to be correct.
•  » » » » » » 7 years ago, # ^ |   0 It can be done in O(N) by DFS using only edges v — parent[v].
•  » » » » » » 7 years ago, # ^ |   +8 each DSU has O(n) edges, just use them.
•  » » » 7 years ago, # ^ |   0 How to union long lenght ?
•  » » 7 years ago, # ^ | ← Rev. 4 →   +4 DFS per query: void dfs(int v){ used[v]=true; for (int j=0;jr)) dfs(g[v][j].v); }; 
•  » » » 7 years ago, # ^ |   +19 It fails on half of hacks. Probably systest will fail most of them.I solved in such way. Let's have to sets of edges. First is edges, which connect vertexes, which is not connected by edges with less numbers. Second is edges, which connect vertexes, which is not connected by edges with greater numbers. There sizes is O(n) and other edges is not need. So we can answer query in O(n) time. It's easy to implement this solution with dsu.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +15 thanks for your response,I am interested why this solution get TLE,I only changed positions and get ac:TLE41: if (!used[g[v][j].v] && (g[v][j].indr)) ACCEPTED: if ((g[v][j].indr) && !used[g[v][j].v]) why system test is so strictly what is difference ? :(
•  » » » » » 7 years ago, # ^ |   +17 Consider "if ( A && B ) {}" code. If A is false, then B isn't checked. B is checked only when A is true. So if we know that A is false more often than B is false, it's better to write "if ( A && B) {}", otherwise "if ( B && A ). In our case (g[v][j].indr) statement is false more often than !used[g[v][j].v] is. Therefore, if ((g[v][j].indr) && !used[g[v][j].v]) is the best way.
•  » » » » » » 7 years ago, # ^ |   +9 It will be a good lesson for me,thanks
 » 7 years ago, # |   +36 CROC's English is very very difficult and long... I took hard to read even using translation machine.
 » 7 years ago, # | ← Rev. 2 →   -8 Very nice problem D. I knew my solution in wrong, but I've locked my code and hacked 7 people!!
•  » » 7 years ago, # ^ | ← Rev. 3 →   +8 Lucky you, I wanted to do the same but tourist hacked me first :(
•  » » » 7 years ago, # ^ |   +21 It can be considered a privilege being hacked by him. :)
•  » » 7 years ago, # ^ |   0 Could you tell me what's the tricky case for problem D ?
•  » » » 7 years ago, # ^ |   0 Just a random test with 500 vertexes and 10000 edges and 20000 queries that all of them are : 1, 10000
•  » » » » 7 years ago, # ^ |   0 if N = 2, M = 2, edge are = {1, 2} {1, 2} and the query is {1, 1} The answer is 1 or 2 ?
•  » » » » » 7 years ago, # ^ |   0 I think there could not be any multiple edges.
•  » » » » » » 7 years ago, # ^ |   0 There could be multiply edges.
•  » » » » » » 7 years ago, # ^ |   0 "Note that a pair of computers can be connected by multiple cables." But the problem say so. .
•  » » » » » » » 7 years ago, # ^ |   +1 Very good! now I think my solution besides time limit, will get wrong answer!! :D
•  » » 7 years ago, # ^ |   +1 Cool strategy..!
 » 7 years ago, # |   0 What's the solution to C and E? Thanks.
•  » » 7 years ago, # ^ |   +1 for C the most important thing you should consider is that you can obtain the hole string by determining the length of each of 4 number O(3^4) and the material of the first half of the string O(n^(half of the length <=6)) and then you should check whether it is legal or no for more info see my C++ code : 355108 for E you should use segment tree data structure (read about it here )segmnet tree and keep for each node of the tree that what is the last copy that contains this node and then easily find the answer for each query if you need more info see my C++ code : 3550844 I hope it will be useful for you.
 » 7 years ago, # |   +4 Too strange, why I can't see the system testing? Are they really testing now?
•  » » 7 years ago, # ^ |   +7 you sure you know what "pending" means? xD
•  » » » 7 years ago, # ^ |   +6 You mean there are some delays and they are just waiting?
•  » » » » 7 years ago, # ^ |   0 Yes and no. the aren't waiting (its pointless isn't it?), they most likely are master basing
 » 7 years ago, # |   -6 It was too hard!!! :D
 » 7 years ago, # |   0 why the wait for system tests?
 » 7 years ago, # | ← Rev. 2 →   +136
•  » » 7 years ago, # ^ |   +6 I think systest will run for last 6 hour like on qualification round :D
•  » » » 7 years ago, # ^ |   +6 I think the judge should tells when will the ST begin , if it's too late , I will go to bed now
•  » » 7 years ago, # ^ |   +13 one does not simply, you mean ?
•  » » » 7 years ago, # ^ |   +1 double translation is evil:)
•  » » 7 years ago, # ^ |   +82
•  » » » 7 years ago, # ^ |   +1 Actually, you should better hack O(MK)
•  » » » » 7 years ago, # ^ |   +11 Oops. I hope everyone understood me :)
 » 7 years ago, # |   +4 Why testing won't start?
 » 7 years ago, # |   0 please tell me when i can submit my solution for problem 5??? and where i can do that???my brain is exploding, because i submitted my code 5 seconds before the end, and because of the stress i had, i made a little mistake and 10 seconds after i noticed that!! if i submitted that my score was about 1400 and i would advance to the Round 2.my brain is exploding now! help please :(
•  » » 7 years ago, # ^ |   0 well my story is more tragic. Cause of Iran’s f*** network I wasn’t able to submit my E code in 1:10 when I have already submitted A,B,D. My network re-concocted after the contest. what should I have to do ???
•  » » 7 years ago, # ^ |   0 excuse me! i mean 4500(not 1400)! it's because of my brain!
 » 7 years ago, # |   +22 Hey guys, Is there any one to start system test? Mike? Gerald? Pavel?
•  » » 7 years ago, # ^ |   +5 it seems there is no one to start system test
•  » » » 7 years ago, # ^ |   +16 It will be started soon. Please, a little patience.
•  » » » » 7 years ago, # ^ |   +2 Is there any technical problem? I Can't understand this to much delay.
 » 7 years ago, # | ← Rev. 2 →   +6 One hour of pending system test should be something unusual. In that case, we contestants all expect some announcements/explanations from admins :(Edit: ok, just saw Mike's comment :)
 » 7 years ago, # |   +204 Meanwhile in CodeForces HQ:
•  » » 7 years ago, # ^ | ← Rev. 2 →   +80 This one!
 » 7 years ago, # |   -126 Plus this comment to see how many people are waiting for the system test. :D
•  » » 7 years ago, # ^ |   +121 Okay, keep downrating it :D. I'll take the abs :D
•  » » 7 years ago, # ^ | ← Rev. 2 →   +14 We can minus your comment to see how many people are waiting for the system test. Same result :D
•  » » 7 years ago, # ^ |   -20 you wanted to say "minus this post to see how many people are waiting for system test"
 » 7 years ago, # |   0 dafaq are we waiting for! ?
 » 7 years ago, # |   -8 I'm staying up for the system test! Please get this done ASAP, I want to sleep!!
 » 7 years ago, # | ← Rev. 2 →   -19 Well,I have to thanks all Codeforces team. They taught me what does error 502,504 and server busy means :D . I was kidding but I really expect codeforces to be more faster in this contest :D.
 » 7 years ago, # | ← Rev. 2 →   +6 no wonder tourist completed the contest in just 35 minutes.3000+ on the cards.
 » 7 years ago, # |   +9 haha, in my B i had "unknown toplogy" instead of "unknown topology" in one minor case, WA on 38 :-))
 » 7 years ago, # | ← Rev. 2 →   +11 in problem D: Why was K limit so low?? some people got AC with O(mk), but some people didn't.the problems were are implementation and coding and non-algorithmic. and very slow system testing I did not like this contest
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 More than 1200 contestants, it isn't slow system testing!
•  » » » 7 years ago, # ^ |   +4 it is really slow. just remember last 3 contests, this contest had less contestants than them.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   -39 yes it is! most div 2 contests more than 2000 people participate and it takes less than 30 min and i'm not just talking about system testing, it took about an hour for the system testing to starti think this round should be unrated for these reasons: the contest was uneven : i see a lot of RED contestants which their ranks is more than 300. the problem difficulty's were close to a div-2 contest Problem D is very unfair and they could have set limit of k to 10^5 so people know that the MK soloution would not get AC
•  » » » » 7 years ago, # ^ | ← Rev. 3 →   +12 I don't see how it's unfair. All had same chances
•  » » » » » 7 years ago, # ^ |   -17 Because there are participants who got Ac on O(mk) soloution And if the k limit was higher, people would think on another soloution
•  » » » » » » 7 years ago, # ^ | ← Rev. 2 →   +12 If the k limit was higher, then many coders would have discarded the O(mk) solution.But it isn't. The problem statement clearly said k <= 10^4, so, if a coder doesn't realize that the O(mk) solution will work, it's his fault. I don't see how it can be unfair. The constraints were very clear.
•  » » » » 7 years ago, # ^ |   -6 agree with your reasons, specially with third one.
•  » » » » 7 years ago, # ^ |   0 Anyway it's too late! The ratings have been updated
•  » » 7 years ago, # ^ | ← Rev. 3 →   -7 I have the same problem, One of my friend's code got acc although his code had to be very slower than mine.
•  » » 7 years ago, # ^ |   -6 I got back to division 2 and didn't make to the next round because of this So I am completely in agreement with you.
 » 7 years ago, # |   0 is this a rated event or not ? :/
 » 7 years ago, # |   +26 This is translation of my russian answer.We carefully try to make constraints more fair. Our naive solution get TL on our tests. All (except one, that isn't written optimally) our correct solutions passed with 3times reserve. So we decide that our constraints is very good.Here I should say that polygon shows that all TL solutions fits into 2TL. Buy I didn't notice that thing. That's my great fault.I truly apologize for this fault. We will try not to make such faults.
 » 7 years ago, # |   0 Would it be possible to hold the CROC rounds on Sunday instead of Monday? For US competitors who work or are students it's difficult to compete in a round that takes place at 11:30 AM EST on a weekday. I was able to participate in round 1 (and qualify for the next round), but I don't think I will be able to participate in the 2nd round.I don't think this will conflict with the TopCoder Open, or make competing more difficult for participants in Asia or Europe, so maybe it's possible?
•  » » 7 years ago, # ^ |   +9 People may already have plans based on published schedule. Also Codechef Cookoff is scheduled for Sunday
 » 7 years ago, # |   +4 My solution to problem D was bfs for each query having a total time complexity of O(Q * (E + N)), why didn't it pass the time limit? M = 10000 N = 500 Q = 20000 Total number of calculations would be around 2*10^8, I have accepted many problems here in codeforces with the same number of calculations? I had the idea of using DSU but it was a little bit harder to implement and to prove, For further contests how can I be sure if the solution will pass or not whit this number of calculations?
•  » » 7 years ago, # ^ |   0 I do the same too :(
•  » » 7 years ago, # ^ |   +16 When you're that near the limit, there's no guarantee it will work in time. It's just your decision if you want to take the risk and go the easy way, or spend some time thinking a faster solution.
•  » » » 7 years ago, # ^ |   +28 You can always use "Custom test" to approximate the running time in worst case. I first submitted a naive solution. Then I used this and figured out it was too slow and resubmitted it later. (Tips: there's a limit for input size in "Custom test", however we only need to measure the running time, so simply assign some random numbers directly in the code itself)
•  » » » » 7 years ago, # ^ |   0 good idea, tnx :-)
 » 7 years ago, # |   0 In question D: Can somebody tell me why this submission using dfs worked. 3545286 and mine using bfs is giving TLE. 3551854 Thanks in advance..:) KrK
•  » » 7 years ago, # ^ | ← Rev. 3 →   0 R_R_ You hacked in during contest. Comments please.
•  » » 7 years ago, # ^ |   0 The constant factor in your solution seems to be a little higher. You're using two arrays (color and marks), when you only need one (one that states whether the node has been assigned a component). Try using only the color array and see if you get it AC.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 3552076 Still not..
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +1 I think it doesn't work in time because you are using stl queue, which might allocate memory somehow slower when compared to static array used as queue (see 3552315)
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +3 Haha.. That was really awesome..!! Never thought using STL queue will make it this much slower..:PThanks a lot. ondrah..:)
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 ondrah Hey, the one you used in your submission is not BFS. It's is still dfs because you actually implemented a stack using array.:)Even queue implemented through array is not working. See 3553686
 » 7 years ago, # |   -29 292D - Connected Componentscan anyone tall me why is [ if(!fix[v[i][j].fi] && (v[i][j].sey)) ] this wrong and this [ if((v[i][j].sey) && !fix[v[i][j].fi]) ] true?????
•  » » 7 years ago, # ^ |   +9 It isn't wrong — it just exceeds the time limit. The matter was discussed here.
•  » » » 7 years ago, # ^ |   +8 :D :D thanks jimi :D
 » 7 years ago, # |   -58 such a long questions . it was hard to translating specially for persons that their english are not too good .
•  » » 7 years ago, # ^ |   -47 I made a mistake . It is the participants' duty that have a good English .You can give the questions somehow you want . at last thanks for the contest .
 » 7 years ago, # |   0 Round 2 will be rated for people who did not get in the first 400 in round 1 ? Thanks.
•  » » 7 years ago, # ^ |   0 and both for div2 and div1 ? Thanks
•  » » » 7 years ago, # ^ |   0 Yes , for all the people who participate.
 » 2 years ago, # | ← Rev. 2 →   0 Can anyone please tell me where I'm going wrong in the E problem. I have complicated the question with my implementation, but I cannot find where I went wrong :(. Thanks in advance! Here is the link to my submission: 33489074