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.
Seems like really tough competition.. Did you mean under 400 amongst all Red,orange and purple coders ?
Will the round be rated?
"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."
So what does a official contest participant mean?
it's rated for both Divisions.
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.
In my view, all the participant who read the problem will be rated, as normal CF contests.
You need to submit something to be rated, be it normal CF round or competition one
How would the rating be calculated for both division 1 & division 2 participants ?
how many rounds will this series of contests have,is there any T-shirts to give the winners ?
It seem that there's only one round.
The problems will be more suited for div1, div2 or half way? :)
How to register when registration is private? It seems too private for somebody to enter :)
I have the same problem. I have to register now because I will not have internet acces until the start of the competition
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?
"Registration is private", does it mean that all participants who passed qualification round will get registered automatically?
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.
I hope
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.
"For official contest participants the round will be rated" ... for only the contestants the round is rated ??? am I misunderstanding ???
it is decided that it will not be able to participate out the competition.
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"
haha you quoted that sentence as if it were in correct English :D
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.
Try to use mobliephone:(
Registration is fixed now.
Edit
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?
put off 5 minutes?
Lots of hacks specially Problem 4.
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 :(
what is error message?
Looks like you forgot to output request's type in the last
for
Did you mean
printf("1 %d %d %d\n", 1, 1, n);
in the last line?Oops, I forgot that the 1-typed query needs three parameters. Thanks everyone :). (I need to practice generating input more regularly).
Just one second to click submit button for problem E. :|
And one second for my C, please :(
Thanks God! Mine was wrong :)
Just one second to click submit button for my 100% corect sources for A, B,C,D,E :/
What is the solution for D? Or is it just a DFS per query?
I use disjoint set, with total complexity O(K * (N + UnionSet cost)).
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))?
oh yes, sorry I miss calculation :). N that I wrote first, I mean is M, total edge not total vertex.
Given M = 10000, K = 20000, will 2*10^8 survive?
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)).
How could one merge 2 DSUs ?
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...
OK, it seems to be correct.
It can be done in O(N) by DFS using only edges v — parent[v].
each DSU has O(n) edges, just use them.
DFS per query:
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.
thanks for your response,I am interested why this solution get TLE,I only changed positions and get ac:
TLE41:
ACCEPTED:
why system test is so strictly what is difference ? :(
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].ind<l || g[v][j].ind>r) statement is false more often than !used[g[v][j].v] is. Therefore, if ((g[v][j].ind<l || g[v][j].ind>r) && !used[g[v][j].v]) is the best way.
It will be a good lesson for me,thanks
CROC's English is very very difficult and long... I took hard to read even using translation machine.
Very nice problem D. I knew my solution in wrong, but I've locked my code and hacked 7 people!!
Lucky you, I wanted to do the same but tourist hacked me first :(
It can be considered a privilege being hacked by him. :)
Could you tell me what's the tricky case for problem D ?
Just a random test with 500 vertexes and 10000 edges and 20000 queries that all of them are : 1, 10000
if N = 2, M = 2, edge are = {1, 2} {1, 2} and the query is {1, 1} The answer is 1 or 2 ?
I think there could not be any multiple edges.
There could be multiply edges.
"Note that a pair of computers can be connected by multiple cables." But the problem say so. .
Very good! now I think my solution besides time limit, will get wrong answer!! :D
Cool strategy..!
What's the solution to C and E? Thanks.
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.
Too strange, why I can't see the system testing? Are they really testing now?
you sure you know what "pending" means? xD
You mean there are some delays and they are just waiting?
Yes and no. the aren't waiting (its pointless isn't it?), they most likely are master basing
I think systest will run for last 6 hour like on qualification round :D
I think the judge should tells when will the ST begin , if it's too late , I will go to bed now
one does not simply, you mean ?
double translation is evil:)
Actually, you should better hack O(MK)
Oops. I hope everyone understood me :)
Why testing won't start?
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 :(
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 ???
excuse me! i mean 4500(not 1400)! it's because of my brain!
Hey guys, Is there any one to start system test? Mike? Gerald? Pavel?
it seems there is no one to start system test
It will be started soon. Please, a little patience.
Is there any technical problem? I Can't understand this to much delay.
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 :)
Meanwhile in CodeForces HQ:
This one!
Plus this comment to see how many people are waiting for the system test. :D
Okay, keep downrating it :D. I'll take the abs :D
We can minus your comment to see how many people are waiting for the system test. Same result :D
you wanted to say "minus this post to see how many people are waiting for system test"
I'm staying up for the system test! Please get this done ASAP, I want to sleep!!
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.
no wonder tourist completed the contest in just 35 minutes.
3000+ on the cards.
haha, in my B i had "unknown toplogy" instead of "unknown topology" in one minor case, WA on 38 :-))
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
More than 1200 contestants, it isn't slow system testing!
it is really slow. just remember last 3 contests, this contest had less contestants than them.
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 start
i 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
I don't see how it's unfair. All had same chances
Because there are participants who got Ac on O(mk) soloution And if the k limit was higher, people would think on another soloution
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.
agree with your reasons, specially with third one.
Anyway it's too late! The ratings have been updated
I have the same problem, One of my friend's code got acc although his code had to be very slower than mine.
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.
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.
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?
People may already have plans based on published schedule. Also Codechef Cookoff is scheduled for Sunday
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?
I do the same too :(
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.
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)
good idea, tnx :-)
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
R_R_ You hacked in during contest. Comments please.
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.
3552076
Still not..
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)
Haha.. That was really awesome..!! Never thought using STL queue will make it this much slower..:P
Thanks a lot. ondrah..:)
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
292D - Connected Components
can anyone tall me why is [ if(!fix[v[i][j].fi] && (v[i][j].se<x || v[i][j].se>y)) ] this wrong and this [ if((v[i][j].se<x || v[i][j].se>y) && !fix[v[i][j].fi]) ] true?????
It isn't wrong — it just exceeds the time limit. The matter was discussed here.
:D :D thanks jimi :D
such a long questions . it was hard to translating specially for persons that their english are not too good .
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 .
Round 2 will be rated for people who did not get in the first 400 in round 1 ? Thanks.
and both for div2 and div1 ? Thanks
Yes , for all the people who participate.