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.

I'm assuming div2 people who qualified to Round 2 should participate in the non-Div2 round?

In last 3 raunds I've lost 204 points of rating, may I find some luck in this contest ))))

It's good news that participants from div 2 can participate in this contest ))))

I pray for irakli_p to increase his rating this time.

thanks )))

"A little bonus: top 200 official Championship contestants will receive t-shirts!" why only official ? give top 200 contestants from both official and unofficial.

http://i1.kym-cdn.com/photos/images/original/000/210/119/+_2acc5a8841f8752904d37f90a8014829.png

F5 power

I think, this contest should not be rated, due to the network problem.

When the contest first opened on my pc, many people had already submitted the first problem

yeah... so i think this contest should not be rated...

If they said it's going to be rated, it will be rated. End of story :)

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.

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.

The same happened here.

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.

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.

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 :).

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.

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.

Indeed, but they don't start the match until everyone's on the field, do they? :)

What is the solution for E? (div1 C)

Hard Contest.... Very Hard Contest! :)

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.

I made two hacks, there was O(N^2) solutions for A in my room

I think you are lucky :) congratulations for your hacks

my solution also hacked.. i dono whats wrong :(

I also couldn't find a solution that can be hacked...That's my first time to attempt hacking.It is a little interesting.

there was a lot of TLE solutions for problem div2 B. but it did'nt allow to make such a big test. why?

I think you should use test generator

how should I use that?

in my room some contestants wrote gcd solution for problem A, but didn't check that gcd exists in input array

nice to meet you. and thanks for the hack )))

Then how these codes pass sample test?

because if gcd==1, then the answer is -1.

I hacked two codes for the problem C with this input: 3 000000 100000 And same than previously said: O(N²) solutions

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

I think the idea is that, if you want to qualify, you should be able to do some really hard problems..

Problem D,E is too difficult for Div.2...

E is not as hard as could be.

I am happy, my C (div 2) solution passed the tricky 6th pretest!!!

But you know. admit you know. it's gonna fail on systest.

I don't know. By the way, I only said that my solution passed this pretest.

lol, I got AC!!!congrats xD.

when will system test begin ?

what about system test ?

it seems there is no one to run it :D.

Admins are busy in the discussion of "whether contest should be rated or not"...:D

Plz the contest should be rated . It is my career best rank . I do not want to lose the increment in rating .

Why it's still pending system testing?

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..

THIS IS CODEFORCES! A long time ago, it was always like today's contest. :)

so experienced but green.

I sometimes go to div1, but I love div2!

If you view his profile you will notice that he is an old contestant!

When is system test bigin ?I hope it bigin soon today!

Was in top20. My best result. But then my solution of C failed. And this is the reason.

Fail...

S — F == 1 is draw when you don't have '1s' in the same position. Well, here is my solution.

..

nice!!!

we i can't see other solution ?

I really don't think this contest should be rated.

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...

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.

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).

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.

Я, как и многие, открыл не тот раунд, думая, что это и есть контест, который надо писать.

При этом мне сразу понравилась E, я ее прочитал и начал кодить.

Это считается читерством?

Или после этого я должен был благородно отказатся писать контест?

Sorry for the Russian language in English thread, feel free to ignore it.

Очевидно, не считается, это ведь не умышленно было сделано. Неужели действительно у большого количества народа была такая проблема? Я, например, всегда смотрю, в какой раунд захожу, т.к. div1/div2 контесты часто совмещены.

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).

any chance to receive a shirt for ranking 205?

I don't know about shirt but I surely know something about a little differently spelled xD

Why we can't practice now?

same problem. why???

This Cheered me up during the contest.

so now it is rated only for offical?

I participated in contest unofficially and my rating didn't update.

Check it now.

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?

Ratings have been updated. Interesting :)

@admin there is a bug in the ratings.

when i click

touristin thetop ratedcolumn in the right side, then old rating is there intop ratedcolumn . same happens when i click onpetr.however it works fine for other participants.

EDIT : it is ok now.

what is test 33 in div 2 problem C. it's like 100000 9 .........................................................................

is it all contain '.'s ?

since the correct output is "NO" then clearly it have at least 9 adjacent "#"s

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?

It's common definition, that some figure is convex if and only if for every two points

A,Binside 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.

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.

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.html

Look, 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.

i know how it feels bro

That golden days . sigh!!!!!!!!!!!

Screencast

just a show off, there is nothing to learn from this screencast

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

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

just be calm.

nobody force you to see Screencast, bro ;)

just be calm.

nobody force you to see my comments, bro ;)

i am trying to increase your contribution and wanna see you in first position

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?

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

Change from IGM to GM to IGM to GM to IGM in last 4 contests :)

great indeed

Editorial please!

If there's no editorial, maybe someone can explain approach for problems D and E?

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

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...

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 nodes

under the root of u,and minus every calc(son_of_u) . you can see my code here the vector<pair<int,int> > ch[] stores the information of every son of u

What is the solution for problem B and C Div 1

For C, notice that:

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.

Maybe someone can explain approach for problems B(div.1) ?

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.

My approach gives even more precision error. But with long double on GNU it get AC.

I wonder if there exists solution for problem D (expected square area) without limitation on lattice points.

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...