CROC Champ 2013 — Round 2
By Seyaua, 12 years ago, translation, In English

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
  • Vote: I like it
  • +108
  • Vote: I do not like it

Comments Comments (111)
| Write comment?
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -11 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -17 Vote: I do not like it

I pray for irakli_p to increase his rating this time.

→ Reply
»
12 years ago, # |
  Vote: I like it -111 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

F5 power

→ Reply
»
12 years ago, # |
  Vote: I like it +175 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +62 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +60 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it -31 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it -7 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +50 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      The same happened here.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +102 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it -10 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +28 Vote: I do not like it

          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.

          → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

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

        → Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

What is the solution for E? (div1 C)

→ Reply
»
12 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I think you are lucky :) congratulations for your hacks

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Then how these codes pass sample test?

      3
2 3 5
      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +69 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

when will system test begin ?

→ Reply
»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

what about system test ?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

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

        → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Why it's still pending system testing?

→ Reply
»
12 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it -38 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

we i can't see other solution ?

→ Reply
»
12 years ago, # |
  Vote: I like it -9 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 3   Vote: I like it +2 Vote: I do not like it

        Я, как и многие, открыл не тот раунд, думая, что это и есть контест, который надо писать.
        При этом мне сразу понравилась E, я ее прочитал и начал кодить.
        Это считается читерством?
        Или после этого я должен был благородно отказатся писать контест?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

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

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

          → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

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

      → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

any chance to receive a shirt for ranking 205?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Why we can't practice now?

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

This Cheered me up during the contest.

→ Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

so now it is rated only for offical?

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Ratings have been updated. Interesting :)

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

is it all contain '.'s ?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +22 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +14 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 3   Vote: I like it -16 Vote: I do not like it

        i know how it feels bro

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

        → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Screencast

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it -14 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +20 Vote: I do not like it

          just be calm.

          nobody force you to see Screencast, bro ;)

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
            ← Rev. 2   Vote: I like it -6 Vote: I do not like it

            just be calm.

            nobody force you to see my comments, bro ;)

            → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it -13 Vote: I do not like it

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

        → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Editorial please!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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

        → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the solution for problem B and C Div 1

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 4   Vote: I like it +19 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply