By yummy, 8 years ago, In English

Hey Codeforces!

The Elimination Round of the CROC 2016 Championship will take place on Friday, March 18 at 16:35 UTC. After our last round, Yang Liu (desert97), Michael Kural (pi37) and I realized that we haven't had enough, so we joined forces with Kevin Sun (ksun48) and Daniel Chiu (waterfalls) to prepare another problem set for you guys. Our contest will be for combined divisions and consist of seven problems. And although only those who pass the Qualification Round can participate officially, the round will be open to and rated for all Codeforces users. As always, we'll be taking the tractor to Bovinia for some farmland algorithmic adventures with Farmer John, Bessie and her best friend Elsie!

Before we begin, we'd like to thank GlebsHP for doing a wonderful job as contest coordinator—we'd be hopeless without you. We would also like to thank MikeMirzayanov and the Codeforces staff for creating the awesome Codeforces and Polygon platforms. And finally, we're immensely grateful to abacadaea for providing one of the problem ideas and to winger and AlexFetisov for test solving our round.

Formally, there will be two rounds on the same problem set (both rated):

  • CROC 2016 — Elimination Round: for registered Championship participants who have passed the Qualification,
  • CROC 2016 — Elimination Round (Rated Unofficial Edition): for all others.

To take part in the official round you have to be registered for the Championship and solve at least one problem in Qualification round. Both the elimination round and its unofficial edition will be rated. The only difference is that the top 50 participants in the official round will be invited to join the Finals in Moscow. Finalists will be responsible for organizing their trip (tickets, hotel, visas and so on). Each participant may claim reimbursement for transportation expenses not exceeding ~135 USD. Invitations should be accepted no later than March 25.

We hope you enjoy our problems and our cow-flavored text even more than you did last time! Good luck!

UPD1: System testing is delayed because we are investigating some technical issues.

UPD2: The editorial has been posted here. Thanks for participating!

UPD3: Since last ~15 minutes judging system was incorrectly configured for F in the contest "CROC 2016 — Elimination Round" (it is interesting story how it happened), you may appeal your rating change if it affected you much. If you have submitted a solution for F in last 15 minutes and you have strong arguments why incorrect verdict (WA/RE on the test 1) significantly affected your place, please write MikeMirzayanov to make your participation unrated. Sorry about the issue. You can do it before March, 19, 23:59 (UTC).

UPD4: I'd like to congratulate the winners of each round, as well as the top 50 in the Elimination Round for progressing to the CROC 2016 Championship Finals! In addition, Petr and jqdai0815 deserve a special shoutout for solving all seven problems!

CROC 2016 — Elimination Round

  1. Petr
  2. tourist
  3. vepifanov
  4. rng_58
  5. I_love_Tanya_Romanova

CROC 2016 — Elimination Round (Rated Unofficial Edition)

  1. jqdai0815
  2. anta
  3. Alex_2oo8
  4. NaiveNaive
  5. eddy1021
  • Vote: I like it
  • +214
  • Vote: I do not like it

| Write comment?
»
8 years ago, # |
  Vote: I like it -117 Vote: I do not like it

Hope for hard data structures!

  • »
    »
    8 years ago, # ^ |
      Vote: I like it -93 Vote: I do not like it

    Why am I getting so many downvotes? Does everyone else here just want math?

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -20 Vote: I do not like it

      I guess it`s because of your quite egoistic message. Tastes differ, so you shouldnt write about things that are really loved by small piece of community. 5-10% wants hard data structures (about 40% hate it, so they downvote) and 99% wants nice problemset. P.S. hope you uderstood what i had wanted to say

  • »
    »
    8 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    I do hope too. Constructive-only problems are lame in most of cases.

»
8 years ago, # |
  Vote: I like it +69 Vote: I do not like it

Will ratings be updated differently for both editions ? Or final rating changes would be based on combined leader-board of both editions ?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

    I think it is unreasonable to rate differently for the two rounds.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +47 Vote: I do not like it

      Seems like they will rate differenly since there are two different contests. I agree that it is unreasonable, it is stupid to rate differently just for having opportunity to go finals or not!

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        Well, things like hacks and separate scoreboards mean that the contests are not the same. It's similar to the three versions of the 8VC finals.

        Also yes problems should be sorted, why wouldn't they be?

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          Rev. 2   Vote: I like it +37 Vote: I do not like it

          I think it is not the same thing because in 8VC people seperated by their score at contest before, also there were different problemsets for each round.

»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

MooooOOMOoOOOOMOoOOOoMOOoOooMOooOoOMOOooOOMOOoOoo

»
8 years ago, # |
  Vote: I like it +37 Vote: I do not like it

7 problems and 2 hours ? :(

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

    Possibly not. We aren't sure about scoring or time yet. Please do not feel any angush over this! When the contest rolls around, we are sure that you will be amoosed by our puns.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +47 Vote: I do not like it

      You've got 10 hours before it begins and you can't provide the duration?

      I'd really appreciate that info — it's hard to decide whether to compete or not without that information...

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

        We expect that it will be 2 hours, maybe 2:30 hours if we decide the problems are on the hard side.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          seems like problems are in easy side (?)

»
8 years ago, # |
  Vote: I like it +62 Vote: I do not like it

I think that there should be one contest and you should just select first 50 registered participants to go to the finals.

»
8 years ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

Oh thank god! A rated contest is here.

Btw, I registered, but I am unofficially participating. Will the round be rated for me then?

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

    please read the blog post carefully once instead of asking so many questions and remaining confused all the time...this is not specifically for u.. for everybody in genereal...

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

      CROC 2016 — Elimination Round (Rated Unofficial Edition): for all others.

      I somehow missed this line, my bad :/

»
8 years ago, # |
  Vote: I like it +25 Vote: I do not like it

finally rated round.

»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

lol now it becomes really messy !

the registration for IndiaHacks 2016 is started i registered in Div1 contest what would happen if i become Div2 in this contest ?

»
8 years ago, # |
Rev. 3   Vote: I like it -49 Vote: I do not like it

nothing. thanks for reply and votes..

»
8 years ago, # |
  Vote: I like it -7 Vote: I do not like it

is there a way to submit my solution after the contest is finished ?

»
8 years ago, # |
Rev. 2   Vote: I like it +123 Vote: I do not like it

I think the division of the contest in two is not a good idea.

Right now I can opt to register to either of the two contests. I could register to the Unofficial Round OR I could sign up to CROC Championship and then register to the Official Round, because I passed Qualifications. Basically, I can pick who I want to compete against. This isn't fair.

Couldn't you make a single contest and then filter (or just handpick) the top 50 participants that meet the requirements of participating in the Final Round?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +74 Vote: I do not like it

    Totally agree.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +82 Vote: I do not like it

    In the last minutes in the qualification round jqdai0815 re submitted a wrong code in first problem which passed the pretest so that fail and not be qualified and he now registered in the unofficially version of the Elimination round, while the official round has 7 LGM and many other great coders.

    I do not mean that jqdai0815 can not compete well in the official version, we all know who jqdai0815 is, but I think is it not fair to have 2 separate versions of the contest and 2 separate standing which will make one of them easier than the other one, and become in the top 10 ( in the unofficially ) much easier than the official.

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

      It's Too Difficu1t to FST.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      I am wondering participating in which of the rounds will get him better rating change?

»
8 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Hopefully I can handle these problems lol. Otherwise I guess I'll be dropping back to Newbie again.

»
8 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Good luck

»
8 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I passed the qualification round

and now when I register for the Unofficial Edition I get a message :

please register to the official edition , but I don't want :3

why you don't make one contest ? :\

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

    I think this is affecting the number of participants since only around 2500 people have registered so far in both rounds.

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

    I passed the qualification round and I registered for the Unofficial Edition, no problem at all

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

      may be because I registered for the official contest then canceled my registeration then tried to register for unofficial version

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Seems like not much people are participating compare to other rounds,that means harder to climb rating Xp. But I will participate anyway. Hope this contest go well,nice and smooth for the round organizer and participants :)

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

will you merge the standings for calculate ratings ? or ratings will be calculated separately ?

»
8 years ago, # |
  Vote: I like it +78 Vote: I do not like it

My performance on Codeforces is getting worse:

I'm afraid today I can solve only 2 problems :((

»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

I am hoping to see tourist surpass rating 4000.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I sure hope I won't get a rating change smaller than -40! (that's an exclamation mark, not a factorial)

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

not able to submit E

»
8 years ago, # |
  Vote: I like it +165 Vote: I do not like it

The best problemset I've seen on Codeforces during the last time.

»
8 years ago, # |
  Vote: I like it +71 Vote: I do not like it

How is it I got WA on pretest #1 in problem F?

I did a custom invocation and the answer was OK. Does pretest 1 differ from the one in the statement?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Same problem, 16795467.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +44 Vote: I do not like it

    Got this response from jury:

    " We're really sorry, somehow the system broke in the last 5 or so minutes. It is accidentally running your code on G instead of F. Gleb is busy right now with other issues and we can't do anything about it.

    We really apologize. :("

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

      Ok, then if my solution is indeed correct, they should run it on system test and I should get the score for the problem. The same for all contestants who submitted it and got WA on pretest #1.

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

        Totally agree with you. I'm really surprised and frustrated about the fact that there wasn't some broadcast message about this problem — they clearly knew about it before I asked a question. That way me (and other people with the same problem) could at least spend last minutes doing something useful.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Phew, that doesn't make my solution incorrect (unless it gave correct answers on the pretests of G, which is negligible :D).

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      But for some people, they may be confused about the testing result and do useless things.

      They missed one or more chances to check their codes on pretests, which may be helpful to fix some small bugs.

      As for me, if the pretests ran well, I may be possible to fix "ans" to "(ans+mod)%mod" to avoid printing negative numbers. :(

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

    For me — RE: 16795457

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

    The same.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Please, read UPD3. I'm sorry about it, it's my fault.

»
8 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Systest when?

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

    It seems there are some problem with the problem F.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Brb, posting that picture of a button with "START SYSTEST" for tons of contribution.

»
8 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

3 WA's on 3rd question. Is ternary search the solution? Also for 4th question, finding longest acyclic path in a dag and binary search? Would this work?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    For 3rd question, I used a sliding window for O(N) time. I'm not sure how ternary search would work.

    For the fourth, I binary searched until the graph was a valid one (that there was a valid ordering of nodes), but I think the way I checked graphs might be wrong. I found the winner of the graph (node without any parents) and continuously found the next best rapper.

    I got stuck on D for ~20 minutes because of a bug in my binary search T_T.

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

      I think you can check if unique ordering appears by searching for a hamiliton graph on that DAG, which equals topo sort while you can never find more than one node to remove each time.

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

    4-th: no binsearch. Longest path + review edges and stop when all edges on the path viewed

»
8 years ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

Seems like tourist is not going to get his 4k rating. UPD: He is. UPD2: He isn't. :(

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do E?

»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

You must be kidding...

  • »
    »
    8 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    Windows 10... You must be kidding...

    Opera... You must be kidding...

    "You must be kidding..." Yeah I must be kidding...

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

    Thanks for sharing this screenshot. Through this I came to know about NBHEXT

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can robot rapping ordering competition be solved with dsu? :(

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

    you can find who is the winner with dsu but i dont think u can solve the whole problem

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

    I don't think so, because dsu assumes undirected edges, and the problem reduces to whether for a subset of the edges E, for each pair i, j of vertices either path exists i → j or j → i. The trouble with this of course, is a set of edges like , where dsu will conclude ok, but actually we don't know which if b or c is better.

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

      I found the mistake. Gotta upsolve :)

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

        I don't understand, why would the values in the two DSU values be the same for a graph where there exists an ordering? Do the values not depend on the way you break ties between two components with the same size when you merge them? And hence they could be different even for a series of matches which determine an ordering.

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

    It can be solved with binary search+topological sort in NlogN.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +31 Vote: I do not like it

      You don't need binary search, actually -- once you sort the contestants with topological sort, the only edges you care about are edges between contestant number i and contestant number i+1 (in the ordered list). The number you should output is then the index of the last edge of this form.

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

      my solution using longest path is just O(V+E) (for the problem's limits = O(V))

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

        How did you do it without binary search ??

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

          find longest path (O(V+E)) and then review all egdes (O(E)) until they construct the longest path I found

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

At the end of the match, I received a message saying that your solution has been hacked or resubmitted. It had killed me until I realized after refreshing page a lot of times that, not my solution, but the solution I was viewing was hacked or resubmitted.

»
8 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Something weird just happened, i sent my F code. it was correct for first 2 test. But i got wrong answer in pretest 1. Are you guys sure there is a checker?

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Yeah, the same thing happened to me. I think there's a problem there... I got correct answer in custom invocation too.

    At first I got TLE in Test 6, so I decided to optimize and submit again, only to get WA on pretest 1. I was like " What the...?! ". Maybe they have to recheck that...

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

    +1, same problem. Pretests can theoretically be different from samples, but why then don't we have minuses in the scoreboard?

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

      Submissions that fail on pretest 1 are not counted in the scoreboard, right?

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

    The same. Somebody should investigate it.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it -47 Vote: I do not like it

    I think you forgot to delete blank line end of the output.

  • »
    »
    8 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    It is strange, but it seems like this problem appears only in the end of contest. Nobody passes this problem after 01:47.

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

      They said that the problems appeared in the last minutes. My first submission 1:48:57.

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

        Yes, I have read that. I left this comment before Gleb told us about their problems.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I submitted "cout << 5 << endl; cout << 16 << endl;" in 01:56:56, but this code get WA on pretest1....

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Please, read UPD3. I'm sorry about it, it's my fault.

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

i solved C with ternary search can someone propose an alternative approach ?

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

    I applied sliding window and then binary search. I think I did some overkill with my bs as I did it two times for odd length and four times for even length, but wanted to be absolutely sure... Lets see what happens after the system testing .. an overkill or an overwaste :v

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

      The key is just to try ALL possible farmer's positions and for each of them cows' positions are easy to compute with a window sliding along with farmer's position

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

    I used binary search on covered range r. Then for each possible position i of the farmer in the array I checked if [i-r, i+r] could accommodate k cows and the farmer. With an array of sums it's possible to check each position in O(1).

  • »
    »
    8 years ago, # ^ |
    Rev. 4   Vote: I like it +9 Vote: I do not like it

    How you used ternary search?

    This is my approach-prefix sum of zeroes from left to right. Fill Closest_left_0_of_i array and Closest_right_0_of_i array, then use sliding window(or simply do an l=upper_bound() on zeroes array for each i where zeroes[i]>=k+1) to find the range [l,(r=i)] where they can fit, find midpoint of this range, and check the
    min( max(|l-Closest_left_0_of_i[mid]|,|r-Closest_left_0_of_i[mid]|),max(|l-Closest_right_0_of_i[mid]|,|r-Closest_right_0_of_i[mid]|).
    Take minimum over all i, and also for mid+1 in cases where l+r is odd.

    ps: Formatting here is a little annoying. One can't simply get to a new line with return alone.

  • »
    »
    8 years ago, # ^ |
    Rev. 10   Vote: I like it +2 Vote: I do not like it

    let "lf" be the left most room has been booked and "rh" right most and c the place of owner of cows.so the answer of problem( f(c) ) will be max( c — lf , rh — c).

    next[i] means next 0 room for room i.(left to right)

    first "lf" is the first 0 and "rh" is (k+1)th 0 and c is "lf" and do it until "rh" overflows:

    while( f(c) <= f( next[c] ) )  set c next[c] and set ans min(ans , f(c) )
    
    then set lf = next[lf] and rh = nex[rh]

    so you can calculate the answer with O(N)

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

      I almost wrote your described solution , but I'm not sure it pass SysTest. code

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

      Isn't worst case complexity O(N^2)?

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        no! c , lf and rh iterate each element of array just once! and each turn lf and rh increase so it at worse 3*n that it's O(n)

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The last two minutes were very intense... we got the only two "correct" submissions for the last problem during that short time. :P Anyway, this contest was a huge fail for me. :/

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a query. If I submit a solution and it gets WA in pretest in test 2 and test 2 is included in samples. Will 100 points still be detected from my score?

»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I was trying to hack this solution for problem 645C - Enduring Exodus

Code

My hope was on "v.erase(v.begin(), v.begin() + 1);"

Is it true, that std::vector can erase first element faster than in O(size) time? Otherwise, I don't know why test

100000 50000

0000...000

didn't fail this solution... =(

Can anyone pls help?

»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Tourist has now mastered the art of mind games! Again a last minute submission.

»
8 years ago, # |
  Vote: I like it +52 Vote: I do not like it

About problem F, I think that all contestants who submitted a correct solution but got WA on Pretest 1 should get the score for the problem.

Please check who submitted the problem and got WA #1, then run those solution with full test case and see if they get correct answers within the time limit. If so, all that people should get score for the problem. It would be really unfair otherwise.

»
8 years ago, # |
  Vote: I like it +113 Vote: I do not like it

We are sorry but systesting will be delayed for a while. At the end of the contest we've noticed some technical issues that affected some participants. System testing and rating change is delayed until the full investigation of this case.

We decided to make the tomorrow round combined for both divisions, so you should be able to start to register.

We apologize for the inconvenience.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    A similar thing happened a few months ago, where the checker was wrong for one single test case. It was then decided that said test case should be ignored, and all solutions that got correct answer in the remaining tests got Accepted in the end.

    I think a similar course of action has to be taken here: All solutions submitted during the last 5 minutes should be run on Full Test Set for Problem F, and those who pass System Test should get the score for the problem. In case a user submitted many solutions with WA #1, I believe the first correct solution should be considered in order to minimize penalty.

    I don't know if all this can be done, I'm not very familiar with Codeforces system inner working, but it would be great if you could do it. Let's hope for the best :)

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

      Wrong answers on Pretest 1 don't count against your score anyways. =)

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

        No, but some users might have submitted their last solution many minutes later because they got WA #1, when actually the first solution was indeed correct.

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

          Oh yes, good call, you are right! I'm sure they'll take that into account.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Estimated time till start of system test?

»
8 years ago, # |
  Vote: I like it +114 Vote: I do not like it

Per Codeforces tradition, we'll update this post with the score distribution just before the contest.

this is exactly codeforces tradition; saying that but then not updating anything

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).

»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Pending system testing, same old story :3

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain me problem D? I had only O(N^2) idea and then i stucked.

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

    Binary search on the number of edges and do toposort on it!

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

      it's easier to do dp to find longest path and check if the length is N, instead of toposort

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

      Alternatively, do toposort on the final graph and see when the last edge was added that connected two vertices that were adjacent in the toposort.

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

    Binary search the answer.

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

    binary search on answer. To check whether an answer is posible or not , just add those edges and see if a unique topological sort exists or not.

  • »
    »
    8 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    Actually it's possible to solve it without binary search.

    1. Check if all matches give you unique answer. If not, print -1.

    2. If order is unique, let's assume that robot with index a_0 is better than one with index a_1, which is better than one with index a_2 etc.

    3. Create set {{a0, a1}, {a1, a2}, ....}

    4. Iterate through all matches and erase current match from set (if present).

    5. As soon as set is empty, we know the order.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I didn't use binary search. I did a topological sort and then checked the maximum value of edges among consecutive vertices in toposort. Values of edges are index of match.

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

My idea for D (couldnt implement it tho):

Add all edges in the graph, then check if only 1 vertex has in-degree 0 (lets call it source). If there is no source or there are multiple sources, answer is -1.

Else, find farthest vertex from source (lets call it sink) using dp. If the distance from source to sink is N-1 then print the greatest edge in the path, else print -1

Is this correct?

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

    How are you finding k this way? You're basically checking if answer is not -1. Please explain, I think I misunderstood you.

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

      If the answer is not -1 , you can reconstruct the path from source (robot with greatest strength) to sink (robot with smallest strength), and check the index of all edges in this path. The answer is the edge with greater index.

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Got it! Since there can't be more than 1 edge with same u and v, and transitive property holds true, we can do this, because there can be at most one path with n-1 edges. Thank you for explaining :)

        Finally solved it with topological ordering.

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

        Could you please explain how to find the longest path from source to sink? It's not the first problem I couldn't solve because I can't think of a way to do it.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          This will get TLE. I then used topologial ordering to solve this(queueing 0-indegree vertices in a loop, and removing these vertices from graph(obviously their edges will go too) ).

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

      If you label the edges by their index, the value of k will be the greatest edge on the path with the most edges.

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

lol is solved D with binsearch + something like dijkstra or prim so it's O(nlog2n) not sure if it passes

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

If it was some problems with the system testing, does this round remain rated ?

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What is wrong in this solution for problem D? I used binary search + topological sort. Verdict : Wrong answer on pretest 11. My Code

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

    As I can see, your isDist returns true iff there are no cycles? E.g. consider test 4 3 1 2 1 3 1 4 It looks to me your code will not output -1 though it should.

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

      My code give output "-1" and i think it's correct.In my isDist function when i'm doing topological sort,if i find more than 1 element in queue that means we can choose next element in more than one ways.So the topological sort must not be unique.So i return false.

»
8 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

I made 6 submissions by F and got 6 WA1. Now all my submissions are passed. Will you ignore my last 5 submissions?

UPD: Thanks, they are ignored.

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

    I think, jury should system test all WA#1 submissions and select the first passed (if there are such submits :D) as the final result.

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I agree. In that case there will be some participants who failed the problem (like muratt below). They will ask for unrated round.

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

        Yes, despite of the time of the issue (1:47) it has a big influence to results. You would have been able to check/debug your code, challenge somebody or even solve another problem. I got WA#1 (now Pretests Passed) at 1:47:30 and wasted 12 minutes, while rng_58 solved E at 0:09... (however, unfortunately I'm not rng :D )

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

          I think that about everyone who passed F will want rated round. Actually I think they will do what you said and ask for those who wants unrated round individually. On my mind it will be the best solution.

          But another problem is that this round is the elimination round to the CROC finals. Anyway we should wait for the decision of the administration.

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

            Is it possible to make the round unrated only for those affected by the problem?

            I, for instance, failed problem F because of TLE, but I believe I still want the round to be rated because I did pretty good anyway.

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

              I remember some such rounds. Let's wait for the decision of administration.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      What if participant found a bug, that does not appear in pretests? And resubmitted his solution?

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 3   Vote: I like it +5 Vote: I do not like it

      Such way allows to fix all bugs or speed up with no penalty, which is not honest too. Anyway, seems like there is no way to solve this issue absolutely honest.

»
8 years ago, # |
Rev. 7   Vote: I like it -7 Vote: I do not like it

After F's judged again i got WA in pretest 5. I found a bug after ~10 sec after WA

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

    Out of curiosity, what would your rank (approx.) be if it passed?

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Similar situation — my two WA#1's changed to TLE#7's; which can be trivially fixed by removing redundant "% mod" in the inner cycle. (actually, an interesting question why it takes 8 seconds on server — locally it was below 2 seconds even with this redundant mod (and "Run on server" functionality wasn't working in the last 5 minutes); does it mean that GCC compiler is actually GCC32?)

»
8 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Solution for problem c: First precompute in o(n) for each place x "how many cows can I allocate if i own all places from 0 to x inclusive?" Now we have the capacity to ask in 0(1) how much cows I can allocate if I own places from any (a,b) just getting P[b]-P[a-1]. And to actually solve the problem we do a binary search "can I allocate cows making max distance to y?" We can answer this question in o(n). Test each position for the farmer's place and test if the amount of cows from the position -y to the position+y fits in k.

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

    Solution for problem c:

    First compute in o(n) for each room x "how many cows can I allocate if I occupy all places [0,x] inclusive?" store them as P[x]

    Now we have the capacity to ask in 0(1) how many cows I can allocate if I own places from any [a,b] if we calculate P[b] - P[a - 1].

    And to actually solve the problem we do a binary search can I allocate cows making max distance of y? We can answer this question in o(n). Test each position for the farmer's place (called W) checking if the amount of cows in the range [W - y, W + y] is higher or equal than k+1.

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I am waiting for one day that contests come without delay :-"

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the hack test for B? I solved it, buy I can't see some 'tricky' tests...

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

    Answer doesn't fit in an int, that's how I was hacked.

»
8 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Enable upsolving please!

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

Do you forget to give permission to see other's solutions after the contest? If not why is it so delayed? This was the case for the last contest as well.

»
8 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Seriously man! You don't change ratings, you don't let us upsolve, just sitting here refreshing cause too fresh to go to sleep. Stop wasting my time

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    I know, right?! It's killing me waiting, just tell us something!

»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

So jqdai0815 was able to solve all problems in just 1:24 , this guy is the next big thing.

»
8 years ago, # |
  Vote: I like it -26 Vote: I do not like it

It seems like the ratings are finally updated! tourist got Problem G wrong! Petr went up 181 points and jqdai0815 went up 137 points, while tourist's rating went up, however only 14 points. It would have been interesting to see if these would be different if jqdai0815 had competed in contest as tourist and Petr...

»
8 years ago, # |
Rev. 3   Vote: I like it +21 Vote: I do not like it

My submission got AC, but i found test, where my code failed

Problem : 645D - Robot Rapping Results Report

7 6

1 2

2 3

3 4

4 5

3 6

6 7

My output: 6

Right answer: -1

Code : 16818709

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    LOL, my solution(16818709) doesn't work on test:

    3 2

    1 2

    1 3

    My output : 2

    Right answer : -1

    WHAT???? HOW???

    ...very good tests...

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Serious question: does the final round have English problem statements?

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

    Same question. This is what I found in the announcement page:

    "The official language of the competition is Russian.".

    But I think if there will also be a parallel round they will also have the statements in English.

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

    No. I mean the official round. The availability of English statements in final round will affect my decision of going to Moscow or not.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      It will be problem statements in English too. But I'd like to remind that your trip is completely on you (including visa, tickets, hotel booking and all other routine). For example, I do not think CROC can send you official invitation for visa, because it is formal process in Russia (including registration in special bureaucratic institution). In 2013 (or 2012?) rng_58 visited Finals and we were excited his visit. Hope to see foreigners on the Finals this year :-)