By Seyaua, 6 years ago, translation, ,

Hello everyone!

Round 2 of All-Russian Programming Championship CROC-2013 will take place today. Round was prepared by sdya, Seyaua, Gerald and traditionally, problem statements were translated to English by Delinur.

Good news for people, who didn't qualify to this round — today everyone can participate out the competition. Additionally, round will be rated for both official participants and out of competition participants.

Remind some facts about the official participants:

• All the participants should be 18+ years old
• The championship finals are going to take place on May, 16-17 in Moscow in the CROC office (50 participants)
• The CROC company pays for the accomodation in Moscow during the finals
• For Russian citizens: the travel expenses around Russia will be covered, the transport expenses outside Russia can be covered possibly partially but you need to contact CROC and clarify it for each particular case
• All finalists should confirm invitation and their participation in finals until May 2

A little bonus: top 200 official Championship contestants will receive t-shirts!

Enjoy problems and good luck!

UPD: Point values for problems will be unusual today. 500-1500-1500-2000-2500 for first division and 500-1000-1500-2500-2500 for second.

UPD2: We are really sorry for technical problems. After some discussion we have decided that this round should be rated. The list of the finalists will be based on today's results.

Announcement of Croc Champ 2013 - Round 2
Announcement of Croc Champ 2013 - Round 2

•
• +108
•

 » 6 years ago, # |   +8 I'm assuming div2 people who qualified to Round 2 should participate in the non-Div2 round?
 » 6 years ago, # |   +7 In last 3 raunds I've lost 204 points of rating, may I find some luck in this contest ))))
 » 6 years ago, # |   -11 It's good news that participants from div 2 can participate in this contest ))))
 » 6 years ago, # |   -17 I pray for irakli_p to increase his rating this time.
•  » » 6 years ago, # ^ |   -13 thanks )))
 » 6 years ago, # |   -111 "A little bonus: top 200 official Championship contestants will receive t-shirts!" why only official ? give top 200 contestants from both official and unofficial.
•  » » 6 years ago, # ^ | ← Rev. 2 →   -57
 » 6 years ago, # | ← Rev. 2 →   +24
 » 6 years ago, # |   +175 I think, this contest should not be rated, due to the network problem.
•  » » 6 years ago, # ^ |   +62 When the contest first opened on my pc, many people had already submitted the first problem
•  » » » 6 years ago, # ^ |   +60 yeah... so i think this contest should not be rated...
•  » » » » 6 years ago, # ^ |   -31 If they said it's going to be rated, it will be rated. End of story :)
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   -7 All contests are intended to be rated, but sometimes things go wrong and in these cases, the best to do is to not validate the contest.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +50 difference between over 160 contestants is for submission time for problem A and due to the network problem many contestants read the problem A after 10 minutes. so i think the contest should be unrated.
•  » » » 6 years ago, # ^ |   -11 The same happened here.
•  » » 6 years ago, # ^ |   +102 I agree. For over 200 contestants the difference between them is set by the submission time for A, which today was related more to luck and F5ing skill rather than coding.
•  » » 6 years ago, # ^ |   +11 The main argument for making round unrated are network problems and late submissions of problem A. But is it normal solving only the simplest problem A and making all the contest result depending on first few minutes in which one sends it? Something is wrong with competitors not solving anything else. Sorry that I write that, being myself far from a strong participant.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -10 No guys, the result of a soccer game is not changed after the game finished because the referee gave a wrong penalty to one of the teams. If they have said "it's going to be rated if and only if we won't have network problems", then fine, but in our case it should be rated :).
•  » » » » 6 years ago, # ^ |   +6 Programming contest is not a soccer game. People watch soccer game mostly for fun then for competitive. But here we want a fair contest first. And the network problem is hard to realize during the contest about how serious it was.
•  » » » » » 6 years ago, # ^ |   +28 Why do you have to take it that serious? Come on guys, it is not even a Final round or something similar. Of course we all don't want these issues to happen, but when it does, just deal with it in a positive way. Make your life and others' easier.
•  » » » » 6 years ago, # ^ |   +7 Indeed, but they don't start the match until everyone's on the field, do they? :)
 » 6 years ago, # |   -8 Great attempt guys to hide all other access
 » 6 years ago, # |   +6 What is the solution for E? (div1 C)
 » 6 years ago, # |   +26 Hard Contest.... Very Hard Contest! :)
 » 6 years ago, # |   -6 in div2 problems I think there is no tricky cases , how could many contestants make successful hacking ???I viewed all solutions in my room (room 3) but I couldn't find a wrong solution, even there was no successful hacking attempt in my room.
•  » » 6 years ago, # ^ |   +6 I made two hacks, there was O(N^2) solutions for A in my room
•  » » » 6 years ago, # ^ |   +4 I think you are lucky :) congratulations for your hacks
•  » » » » 6 years ago, # ^ |   -7 my solution also hacked.. i dono whats wrong :(
•  » » » » » 6 years ago, # ^ |   0 I also couldn't find a solution that can be hacked...That's my first time to attempt hacking.It is a little interesting.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 there was a lot of TLE solutions for problem div2 B. but it did'nt allow to make such a big test. why?
•  » » » » 6 years ago, # ^ |   0 I think you should use test generator
•  » » » » » 6 years ago, # ^ |   0 how should I use that?
•  » » 6 years ago, # ^ |   +2 in my room some contestants wrote gcd solution for problem A, but didn't check that gcd exists in input array
•  » » » 6 years ago, # ^ |   +2 nice to meet you. and thanks for the hack )))
•  » » » 6 years ago, # ^ |   0 Then how these codes pass sample test? 3 2 3 5 
•  » » » » 6 years ago, # ^ |   0 because if gcd==1, then the answer is -1.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I hacked two codes for the problem C with this input: 3 000000 100000 And same than previously said: O(N²) solutions
 » 6 years ago, # | ← Rev. 2 →   +69 Imho, this contest was one of the worst-balanced contests i have ever seen. A is too easy(comparing to other problems), C is easier than B (but their costs are same), and both B and C are too difficult for >80% of participants...I don't mind writing such a contest as usual round, but it's very bad idea to give it as qualification round
•  » » 6 years ago, # ^ |   +39 I think the idea is that, if you want to qualify, you should be able to do some really hard problems..
 » 6 years ago, # |   -16 Problem D,E is too difficult for Div.2...
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 E is not as hard as could be.
 » 6 years ago, # |   +3 I am happy, my C (div 2) solution passed the tricky 6th pretest!!!
•  » » 6 years ago, # ^ |   +6 But you know. admit you know. it's gonna fail on systest.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +4 I don't know. By the way, I only said that my solution passed this pretest. lol, I got AC!!!
•  » » » » 6 years ago, # ^ |   +5 congrats xD.
 » 6 years ago, # |   0 when will system test begin ?
 » 6 years ago, # |   -7 what about system test ?
•  » » 6 years ago, # ^ |   +9 it seems there is no one to run it :D.
•  » » » 6 years ago, # ^ |   +20 Admins are busy in the discussion of "whether contest should be rated or not"...:D
•  » » » » 6 years ago, # ^ |   -10 Plz the contest should be rated . It is my career best rank . I do not want to lose the increment in rating .
•  » » » » » 6 years ago, # ^ |   +29
 » 6 years ago, # |   +2 Why it's still pending system testing?
 » 6 years ago, # |   +34 Codeforces is really getting worse a contest after the other! The contest was a real pain! Every 5 minutes the site goes down, also the system test takes too much time to begin..
•  » » 6 years ago, # ^ |   +23 THIS IS CODEFORCES! A long time ago, it was always like today's contest. :)
•  » » » 6 years ago, # ^ |   -25 so experienced but green.
•  » » » » 6 years ago, # ^ |   +26 I sometimes go to div1, but I love div2!
•  » » » » 6 years ago, # ^ |   0 If you view his profile you will notice that he is an old contestant!
 » 6 years ago, # |   -38 When is system test bigin ?I hope it bigin soon today!
 » 6 years ago, # |   -16 Was in top20. My best result. But then my solution of C failed. And this is the reason. if(F > S) cout << "First"; if(F + 1 < S) cout << "Second"; if(F == S) cout << "Draw"; Fail...
•  » » 6 years ago, # ^ | ← Rev. 2 →   -6 S — F == 1 is draw when you don't have '1s' in the same position. Well, here is my solution.
•  » » » 6 years ago, # ^ |   -6 ..
•  » » » » 6 years ago, # ^ |   0 nice!!!
 » 6 years ago, # |   0 we i can't see other solution ?
 » 6 years ago, # |   -9 I really don't think this contest should be rated.
•  » » 6 years ago, # ^ |   -13 Yes, I'd like that too. But unfortunately, we all had the same chances. Some of us did really bad (I'm pretty sure Petr would like the contest to be unrated too :)).I'm surprised at how many red coders ranked really low. The contest difficult was high and strange. I tried problem A, got WA on Pretest 6, then moved on to problem B and got stuck there. With only 15 minutes remaining, I moved back to A, fixed a few things and got it accepted near the time limit.Horrible performance for me this time...
•  » » » 6 years ago, # ^ |   +5 I saw the problems 10 minutes after the contest begins.And then tried A and got WA,a few minutes later passed it.And then stuck on B for about one hour,then I move to C,and complete the code just after the end.I'm said.
•  » » » 6 years ago, # ^ |   +6 IMO decision on whether the contest should be rated or not must not be based on one's bad performance; let's stay objective.Arguments for the contest being unrated: lags for the first ~20 minutes (and therefore slightly increased variance in scores, because of additional time to refresh the page); statements for A, B, C available in div2 while div1 contest was not started (and therefore cheaters could start solving problems ~6 minutes earlier).Arguments for the contest being rated: variance in results because of lags is insignificant (and lags were fixed quickly), most of participants do not cheat, and if someone cheated, most likely it did not help him (at least I hope so).
•  » » » » 6 years ago, # ^ |   +5 Sorry,_I really don't think this contest should be rated._ just means that I just don't hope this contest to be rated because my bad performance,not objectively.I agree with your point mostly.And anyway,the contest has been rated.
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +2 Я, как и многие, открыл не тот раунд, думая, что это и есть контест, который надо писать.При этом мне сразу понравилась E, я ее прочитал и начал кодить.Это считается читерством?Или после этого я должен был благородно отказатся писать контест?
•  » » » » » 6 years ago, # ^ |   +3 Sorry for the Russian language in English thread, feel free to ignore it.Очевидно, не считается, это ведь не умышленно было сделано. Неужели действительно у большого количества народа была такая проблема? Я, например, всегда смотрю, в какой раунд захожу, т.к. div1/div2 контесты часто совмещены.
•  » » » 6 years ago, # ^ |   +38 Well, let's make the server available in random seconds during the contest. Yes, everyone has 'the same chanes'. But will it be fair if someone guess these seconds and get positive score and another don't? I don't think so.We all 'were in the same conditions' but these conditions were very random and made results valid +- 50-200 points only. That's up to +- 20 places (around 40th). I think it's enough for making this round unrated (however, it can remain eliminate round for the championship).
 » 6 years ago, # |   +3 any chance to receive a shirt for ranking 205?
•  » » 6 years ago, # ^ |   +9 I don't know about shirt but I surely know something about a little differently spelled xD
 » 6 years ago, # |   +17 Why we can't practice now?
•  » » 6 years ago, # ^ |   +8 same problem. why???
 » 6 years ago, # |   +9 This Cheered me up during the contest.
 » 6 years ago, # |   +10 so now it is rated only for offical?
 » 6 years ago, # |   +5 I participated in contest unofficially and my rating didn't update.
•  » » 6 years ago, # ^ |   0 Check it now.
 » 6 years ago, # |   0 I have software problems hacking solutions. Today I had time, locked my solutions, but just couldn't open the sources. I use chrome, have adblocks disabled and have the latest flash player. It's really frustrating. :( Can anyone suggest me what I should do?
 » 6 years ago, # |   +3 Ratings have been updated. Interesting :)
 » 6 years ago, # | ← Rev. 2 →   0 @admin there is a bug in the ratings.when i click tourist in the top rated column in the right side, then old rating is there in top rated column . same happens when i click on petr.however it works fine for other participants.EDIT : it is ok now.
 » 6 years ago, # |   +4 what is test 33 in div 2 problem C. it's like 100000 9 .........................................................................is it all contain '.'s ?
•  » » 6 years ago, # ^ |   +1 since the correct output is "NO" then clearly it have at least 9 adjacent "#"s
•  » » » 6 years ago, # ^ |   0 thanks :) my mistake. i just caught the error.
 » 6 years ago, # | ← Rev. 3 →   +22 Though I am not sure, in Problem D, assertion fails on 13th case. Is the given polygon convex really?Edit: So, convex polygon means they can have three collinear points on side? If so then the definition should have been provided properly. Why should one assume 3 points on side will be collinear?
•  » » 6 years ago, # ^ |   +12 It's common definition, that some figure is convex if and only if for every two points A, B inside it, segment [AB] lies inside figure too. For the convex polygon, where three vertices lie on the same line that condition is satisfied, so it's correct to name that polygon convex.Common way is to name convex polygons, where any three points aren't collinear strictly convex.
•  » » 6 years ago, # ^ |   +12 I asked if 3 points of polygon can be collinear during the contest, and got positive answer. Wikipedia agrees that there can be collinear points in convex polygon. Distinction between "convex" and "strictly convex" would be a good practice in statements, in my opinion.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +14 I think, people may continue to debate on definition of Convex Hull for all day long.I am giving some more reference to support my statement: http://mathworld.wolfram.com/ConvexPolygon.htmlLook, they said about sign. We assume sign to be + / -, not 0.http://www.mathopenref.com/polygonconvex.html (2nd google search result)I think, there is not any strict definition of Convex Hull, it is debatable topic. And as far as I have seen, it is common practice to mention whether it is strict or not in the problemset.
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   -16 i know how it feels broThat golden days . sigh!!!!!!!!!!!
 » 6 years ago, # |   +8
•  » » 6 years ago, # ^ |   -17 just a show off, there is nothing to learn from this screencast
•  » » » 6 years ago, # ^ |   +18 It would be pretty poor show-off, considering my start. Actually I just capture everything I write from laptop (as oposed to 2 monitor configuration on desktop). I do not have enough willpower to rewatch my screencasts before I post them, hence at the time of publishing I do not know whether there were something interesing or not
•  » » » » 6 years ago, # ^ |   -14 if you do not know whether there were something interesing or not, then dont post them, though i am getting negatives , but i know truth hurts
•  » » » » » 6 years ago, # ^ |   +20 just be calm.nobody force you to see Screencast, bro ;)
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   -6 just be calm.nobody force you to see my comments, bro ;)
•  » » » » 6 years ago, # ^ |   -13 i am trying to increase your contribution and wanna see you in first position
 » 6 years ago, # |   0 div 1 c:the problem ask you to calculate the number of solution of equation (a+b+c)^3-a^3-b^3-c^3=n and (a+b+c)^3-a^3-b^3-c^3=3(a+b)(a+c)(b+c) so the equation is n/3=(a+b)(b+c)(a+c) put x=a+b y=b+c z=a+c and x<=y<=z my solution is to enumerate all the x and all the y it seem as a o(n^1/3(n^1/2-n^1/3))=o(n^5/6) but it is really fast and I accept the system test.Is it a right way to do this problem?
•  » » 6 years ago, # ^ |   0 My solution: 1 <= x <= y <= z and x,y,z should be the lengths of the edges of a triangle, that is z < x + y. Also, we should have that x +y +z is even. Now: N = 3xyz. N >= 3*y^2 and N < 3xy(x+y) <= 6y^3. So we got the bounds for y: sqrt[3]{N/6} < y <= sqrt{N/3} The bounds for z : y <= z and z is such that N > 3yz(z-y). Iterate over all y and all z with the above conditions and compute x = N/(3yz) and see if the conditions stated above happen. If they do, increment the result with the total number of permutations of this triplet.My sol: submission/3606646
 » 6 years ago, # |   0 Could someone please post the link to solutions / hints for Div 2 problems? Thankyou.
 » 6 years ago, # |   +6 Change from IGM to GM to IGM to GM to IGM in last 4 contests :)
•  » » 6 years ago, # ^ |   -11 great indeed
 » 6 years ago, # |   0 How to count number of solutions of (x+y)*(y+z)*(z+x) = n?
 » 6 years ago, # |   +13 Editorial please!
 » 6 years ago, # |   0 If there's no editorial, maybe someone can explain approach for problems D and E?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +16 PROBLEM E: we can solve it using divided and conquer algo. just consider the paths go through the root,the paths in the subtrees is sub problems,so we can solve them recursively. for every root , we can run a dfs to get tot pairs (depth_i,sumofw_i),now the problem transformed to this:give you n pairs (ai,bi) , find the number of pairs( ai,bi aj,bj ) so that (ai+bi <= L && bi+bj <= w) ,we can sort the pairs first ,and then use algorithm like two pointers to solve it (sort the pairs first)ps:the root can't choose arbitrarily,because the depth of divided and conquer shouldn't be very big,so every time we should find the center of the tree(when it was deleted from the tree,the maxsize of the components is the smallest) overall the complexity is n*logn*logn theres is another similar problem for practice http://poj.org/problem?id=1741
•  » » » 6 years ago, # ^ |   0 Actually, if you just sort the pairs and iterate over them with two pointers, you'll end up counting some paths more than once, because you only need to consider pairs in different branches so that the path goes through the root (pairs in the same branch will be counted in the sub-problem of that branch).I'm still thinking how to solve that part...
•  » » » » 6 years ago, # ^ |   +5 Yes , you are right ,I forgot to say that point... the way is simple , just use a function calc(u) to count the pairs of nodesunder the root of u,and minus every calc(son_of_u) . you can see my code here the vector > ch[] stores the information of every son of u
 » 6 years ago, # |   0 What is the solution for problem B and C Div 1
•  » » 6 years ago, # ^ | ← Rev. 4 →   +19 For C, notice that: (a+b+c)^3 - a^3 - b^3 - c^3 = 3*(a+b)*(b+c)*(c+a) Number of divisor of an integer less than 10^14 is small (I remember it's around 20,000), thus you can brute force (a+b), (b+c), and check if a, b, c are positive integers.
 » 6 years ago, # |   +11 Maybe someone can explain approach for problems B(div.1) ?
 » 6 years ago, # | ← Rev. 2 →   0 Still no editorial?In the meantime, could someone give me a hint for D? What I tried is to find y_low and y_high for every possible x such that segment formed by (x, y_low) and (x, y_high) lies inside the polygon. The rest parts are just some formulas. However, my implementation got a 2e-6 precision error for a large test and I am not sure which one is wrong, my approach or my code.
•  » » 6 years ago, # ^ |   0 My approach gives even more precision error. But with long double on GNU it get AC.
 » 6 years ago, # |   0 I wonder if there exists solution for problem D (expected square area) without limitation on lattice points.
 » 6 years ago, # | ← Rev. 2 →   0 can you give me some hints for problem E? my best solution is in N*(logN)^3 and i don't know if it is fast enough...