By yummy, 7 years ago,

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 MiracleFaFa deserve a special shoutout for solving all seven problems!

CROC 2016 — Elimination Round

CROC 2016 — Elimination Round (Rated Unofficial Edition)

• +214

| Write comment?
 » 7 years ago, # |   -117 Hope for hard data structures!
•  » » 7 years ago, # ^ |   -93 Why am I getting so many downvotes? Does everyone else here just want math?
•  » » » 7 years ago, # ^ |   -20 I guess its 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
•  » » » » 7 years ago, # ^ |   +32 Karma police, I see your work
•  » » 7 years ago, # ^ |   -22 I do hope too. Constructive-only problems are lame in most of cases.
 » 7 years ago, # |   +69 Will ratings be updated differently for both editions ? Or final rating changes would be based on combined leader-board of both editions ?
•  » » 7 years ago, # ^ |   +52 I think it is unreasonable to rate differently for the two rounds.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +47 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!
•  » » » » 7 years ago, # ^ |   +16 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?
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +37 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.
 » 7 years ago, # |   +10 MooooOOMOoOOOOMOoOOOoMOOoOooMOooOoOMOOooOOMOOoOoo
 » 7 years ago, # |   +37 7 problems and 2 hours ? :(
•  » » 7 years ago, # ^ |   +8 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.
•  » » » 7 years ago, # ^ |   +47 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...
•  » » » » 7 years ago, # ^ |   +2 We expect that it will be 2 hours, maybe 2:30 hours if we decide the problems are on the hard side.
•  » » » » » 7 years ago, # ^ |   +15 seems like problems are in easy side (?)
 » 7 years ago, # |   +62 I think that there should be one contest and you should just select first 50 registered participants to go to the finals.
 » 7 years ago, # | ← Rev. 2 →   -21 Oh thank god! A rated contest is here.Btw, I registered, but I am unofficially participating. Will the round be rated for me then?
•  » » 7 years ago, # ^ |   +6 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...
•  » » » 7 years ago, # ^ |   0 CROC 2016 — Elimination Round (Rated Unofficial Edition): for all others. I somehow missed this line, my bad :/
 » 7 years ago, # |   +25 finally rated round.
 » 7 years ago, # |   +32 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 ?
•  » » 7 years ago, # ^ |   +47 I postponed registration to IndiaHacks 2016 to make it clear.
 » 7 years ago, # | ← Rev. 3 →   -49 nothing. thanks for reply and votes..
 » 7 years ago, # |   -7 is there a way to submit my solution after the contest is finished ?
 » 7 years ago, # | ← Rev. 2 →   +123 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?
•  » » 7 years ago, # ^ |   +74 Totally agree.
•  » » 7 years ago, # ^ |   +82 In the last minutes in the qualification round MiracleFaFa 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 MiracleFaFa can not compete well in the official version, we all know who MiracleFaFa 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.
•  » » » 7 years ago, # ^ |   +3 It's Too Difficu1t to FST.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +8 I am wondering participating in which of the rounds will get him better rating change?
 » 7 years ago, # |   +6 Hopefully I can handle these problems lol. Otherwise I guess I'll be dropping back to Newbie again.
 » 7 years ago, # | ← Rev. 3 →   0 Good luck
 » 7 years ago, # |   +30 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 ? :\
•  » » 7 years ago, # ^ |   +6 I think this is affecting the number of participants since only around 2500 people have registered so far in both rounds.
•  » » 7 years ago, # ^ |   +3 I passed the qualification round and I registered for the Unofficial Edition, no problem at all
•  » » » 7 years ago, # ^ |   0 may be because I registered for the official contest then canceled my registeration then tried to register for unofficial version
 » 7 years ago, # |   +3 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 :)
 » 7 years ago, # |   +12 will you merge the standings for calculate ratings ? or ratings will be calculated separately ?
 » 7 years ago, # |   +78 My performance on Codeforces is getting worse:I'm afraid today I can solve only 2 problems :((
•  » » 7 years ago, # ^ |   +17 But your rating was increasing except the last one :/ :/ :/
•  » » » 7 years ago, # ^ |   +7 and his rank was decreasing except the last one :|
•  » » 7 years ago, # ^ |   +1
 » 7 years ago, # |   +28 I am hoping to see tourist surpass rating 4000.
•  » » 7 years ago, # ^ |   -9 Yes, I am hoping too)
•  » » 7 years ago, # ^ |   +27 I guess Codeforces should then think about adding another title named "tourist" :D
•  » » 7 years ago, # ^ |   0 Legend says one day tourist will cause an integer overflow!
 » 7 years ago, # |   0 I sure hope I won't get a rating change smaller than -40! (that's an exclamation mark, not a factorial)
 » 7 years ago, # |   0 not able to submit E
 » 7 years ago, # |   +165 The best problemset I've seen on Codeforces during the last time.
•  » » 7 years ago, # ^ |   0 Yes, many ways to solve a problem is a good stuff.
•  » » 7 years ago, # ^ |   +51 Thanks Zlobober! I'm glad you enjoyed our problems! :)
 » 7 years ago, # |   +71 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?
•  » » 7 years ago, # ^ |   +21 Same problem, 16795467.
•  » » 7 years ago, # ^ |   +44 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. :("
•  » » » 7 years ago, # ^ |   +28 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.
•  » » » » 7 years ago, # ^ |   +8 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.
•  » » » 7 years ago, # ^ |   +15 Phew, that doesn't make my solution incorrect (unless it gave correct answers on the pretests of G, which is negligible :D).
•  » » » 7 years ago, # ^ |   +10 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. :(
•  » » 7 years ago, # ^ |   0 For me — RE: 16795457
•  » » 7 years ago, # ^ |   0 The same.
•  » » 7 years ago, # ^ |   +10 Please, read UPD3. I'm sorry about it, it's my fault.
 » 7 years ago, # |   +22 Systest when?
•  » » 7 years ago, # ^ |   +1 It seems there are some problem with the problem F.
•  » » 7 years ago, # ^ |   +13 Brb, posting that picture of a button with "START SYSTEST" for tons of contribution.
 » 7 years ago, # | ← Rev. 2 →   +5 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?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +2 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.
•  » » » 7 years ago, # ^ |   +6 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.
•  » » 7 years ago, # ^ |   +3 4-th: no binsearch. Longest path + review edges and stop when all edges on the path viewed
 » 7 years ago, # | ← Rev. 3 →   +10 Seems like tourist is not going to get his 4k rating. UPD: He is. UPD2: He isn't. :(
•  » » 7 years ago, # ^ |   +29 You know, he's the master of last minute submissions
•  » » » 7 years ago, # ^ |   +18 He is.
•  » » » » 7 years ago, # ^ |   +3 WA66 :(
 » 7 years ago, # |   0 How to do E?
•  » » 7 years ago, # ^ |   0 Hint: if you want to count the numbers of distinct subsequences, you should make something like . Where is number of distinct subsequences ending with character c which came last to the end of string.
•  » » 7 years ago, # ^ | ← Rev. 4 →   +18 See the second accepted answer here http://stackoverflow.com/questions/5151483/how-to-find-the-number-of-distinct-subsequences-of-a-stringNow, in our case, we had to apply a simple greedy for filling the extra characters. At each step, we will put the character from the alphabet size k, which had occurred earliest (i.e. if last[c] denotes last occurrence of character c, then the character c with minimum(last[c]).
•  » » » 7 years ago, # ^ |   0 Do you pick the earliest character to minimise the loss from dp[last[s[i]] - 1]?
•  » » » » 7 years ago, # ^ |   0 Yes, yes. Precisely.
•  » » » 7 years ago, # ^ |   0 Thanks for the link. :)
 » 7 years ago, # |   +32 You must be kidding...
•  » » 7 years ago, # ^ |   -22 Windows 10... You must be kidding...Opera... You must be kidding..."You must be kidding..." Yeah I must be kidding...
•  » » 7 years ago, # ^ |   0 Thanks for sharing this screenshot. Through this I came to know about NBHEXT
 » 7 years ago, # |   0 Can robot rapping ordering competition be solved with dsu? :(
•  » » 7 years ago, # ^ |   +5 you can find who is the winner with dsu but i dont think u can solve the whole problem
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 Found the mistake. Gotta upsolve :)
•  » » 7 years ago, # ^ |   0 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.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +3 I found the mistake. Gotta upsolve :)
•  » » » » 7 years ago, # ^ |   0 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.
•  » » » » » 7 years ago, # ^ |   0 Yeah that's at least one of the mistakes :)
•  » » 7 years ago, # ^ |   +6 It can be solved with binary search+topological sort in NlogN.
•  » » » 7 years ago, # ^ |   +31 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.
•  » » » 7 years ago, # ^ |   +3 my solution using longest path is just O(V+E) (for the problem's limits = O(V))
•  » » » » 7 years ago, # ^ |   0 How did you do it without binary search ??
•  » » » » » 7 years ago, # ^ |   +3 find longest path (O(V+E)) and then review all egdes (O(E)) until they construct the longest path I found
 » 7 years ago, # |   +12 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.
 » 7 years ago, # |   +38 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?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +5 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...
•  » » 7 years ago, # ^ |   +5 +1, same problem. Pretests can theoretically be different from samples, but why then don't we have minuses in the scoreboard?
•  » » » 7 years ago, # ^ |   +18 Submissions that fail on pretest 1 are not counted in the scoreboard, right?
•  » » » » 7 years ago, # ^ |   +1 Yes
•  » » 7 years ago, # ^ |   +5 The same. Somebody should investigate it.
•  » » 7 years ago, # ^ |   -47 I think you forgot to delete blank line end of the output.
•  » » » 7 years ago, # ^ |   +18 It has to be not necessary!
•  » » 7 years ago, # ^ | ← Rev. 4 →   0 It is strange, but it seems like this problem appears only in the end of contest. Nobody passes this problem after 01:47.
•  » » » 7 years ago, # ^ |   0 They said that the problems appeared in the last minutes. My first submission 1:48:57.
•  » » » » 7 years ago, # ^ |   0 Yes, I have read that. I left this comment before Gleb told us about their problems.
•  » » 7 years ago, # ^ |   +22 I submitted "cout << 5 << endl; cout << 16 << endl;" in 01:56:56, but this code get WA on pretest1....
•  » » 7 years ago, # ^ |   +32 Please, read UPD3. I'm sorry about it, it's my fault.
 » 7 years ago, # |   +5 i solved C with ternary search can someone propose an alternative approach ?
•  » » 7 years ago, # ^ |   +3 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
•  » » » 7 years ago, # ^ |   0 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
•  » » 7 years ago, # ^ |   +9 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).
•  » » 7 years ago, # ^ | ← Rev. 4 →   +9 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 themin( 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.
•  » » 7 years ago, # ^ | ← Rev. 10 →   +2 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)
•  » » » 7 years ago, # ^ |   0 I almost wrote your described solution , but I'm not sure it pass SysTest. code
•  » » » 7 years ago, # ^ |   0 Isn't worst case complexity O(N^2)?
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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)
 » 7 years ago, # |   0 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. :/
 » 7 years ago, # |   0 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?
•  » » 7 years ago, # ^ |   +5 Yes.
•  » » » 7 years ago, # ^ |   0 Thank you :)
•  » » 7 years ago, # ^ |   +5 In this case you get a 50 points penalty.
 » 7 years ago, # |   +11 I was trying to hack this solution for problem 645C - Enduring Exodus CodeMy 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 test100000 500000000...000didn't fail this solution... =(Can anyone pls help?
•  » » 7 years ago, # ^ |   -23 It is similar to v.pop_front(), so it doesnt waste linear time
•  » » » 7 years ago, # ^ |   +10 But std::vector doesn't have pop_front() method
•  » » 7 years ago, # ^ | ← Rev. 2 →   +19 Bet on #define vector deque magic
 » 7 years ago, # |   +9 Tourist has now mastered the art of mind games! Again a last minute submission.
 » 7 years ago, # |   +52 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.
 » 7 years ago, # |   +113 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.
•  » » 7 years ago, # ^ |   +17 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 :)
•  » » » 7 years ago, # ^ |   0 Wrong answers on Pretest 1 don't count against your score anyways. =)
•  » » » » 7 years ago, # ^ |   0 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.
•  » » » » » 7 years ago, # ^ |   +5 Oh yes, good call, you are right! I'm sure they'll take that into account.
•  » » 7 years ago, # ^ |   +29 Estimated time till start of system test?
 » 7 years ago, # |   +114 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
 » 7 years ago, # |   0 Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).
 » 7 years ago, # |   +15 Pending system testing, same old story :3
•  » » 7 years ago, # ^ |   0 this is the fourth time in a row for div1 as far as I remember
 » 7 years ago, # |   0 Can somebody explain me problem D? I had only O(N^2) idea and then i stucked.
•  » » 7 years ago, # ^ |   0 Binary search on the number of edges and do toposort on it!
•  » » » 7 years ago, # ^ |   +11 it's easier to do dp to find longest path and check if the length is N, instead of toposort
•  » » » » 7 years ago, # ^ |   +3 kingofnumbers You are saying that Hamiltonian path problem is easier than topological sorting :P
•  » » » » » 7 years ago, # ^ |   +32 In a DAG it is :P
•  » » » » » » 7 years ago, # ^ |   0 Oh, yes, true. My mistake. I thought of generalized versions.
•  » » » 7 years ago, # ^ |   +20 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.
•  » » » » 7 years ago, # ^ |   +5 i have done exactly this .. getting wa on pretest 6 tho.. could u have a look at my submssion once pls! http://ideone.com/sMWkUO
•  » » 7 years ago, # ^ |   0 Binary search the answer.
•  » » 7 years ago, # ^ |   0 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.
•  » » 7 years ago, # ^ | ← Rev. 3 →   +5 Actually it's possible to solve it without binary search. Check if all matches give you unique answer. If not, print -1. 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. Create set {{a0, a1}, {a1, a2}, ....} Iterate through all matches and erase current match from set (if present). As soon as set is empty, we know the order.
•  » » 7 years ago, # ^ |   +13 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.
 » 7 years ago, # |   +1 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 -1Is this correct?
•  » » 7 years ago, # ^ |   0 How are you finding k this way? You're basically checking if answer is not -1. Please explain, I think I misunderstood you.
•  » » » 7 years ago, # ^ |   0 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.
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 7 years ago, # ^ |   0 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.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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) ).
•  » » » 7 years ago, # ^ |   0 If you label the edges by their index, the value of k will be the greatest edge on the path with the most edges.
 » 7 years ago, # |   +3 lol is solved D with binsearch + something like dijkstra or prim so it's O(nlog2n) not sure if it passes
•  » » 7 years ago, # ^ |   +3 "something like dijkstra or prim" should be topological sorting, I suppose.
•  » » » 7 years ago, # ^ |   0 yes u r right :)
 » 7 years ago, # |   +8 If it was some problems with the system testing, does this round remain rated ?
 » 7 years ago, # | ← Rev. 2 →   0 What is wrong in this solution for problem D? I used binary search + topological sort. Verdict : Wrong answer on pretest 11. My Code
•  » » 7 years ago, # ^ |   0 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.
•  » » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # | ← Rev. 2 →   +18 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.
•  » » 7 years ago, # ^ |   +8 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.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 I agree. In that case there will be some participants who failed the problem (like muratt below). They will ask for unrated round.
•  » » » » 7 years ago, # ^ |   +3 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 )
•  » » » » » 7 years ago, # ^ |   +3 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.
•  » » » » » » 7 years ago, # ^ |   +3 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.
•  » » » » » » » 7 years ago, # ^ |   0 I remember some such rounds. Let's wait for the decision of administration.
•  » » » 7 years ago, # ^ |   +10 What if participant found a bug, that does not appear in pretests? And resubmitted his solution?
•  » » » » 7 years ago, # ^ |   0 I think he means the first solution that passes system test
•  » » » » 7 years ago, # ^ |   0 Passed system tests, not pretests.
•  » » » » » 7 years ago, # ^ |   0 Ok. Sorry. Didn't notice
•  » » » 7 years ago, # ^ | ← Rev. 3 →   +5 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.
 » 7 years ago, # | ← Rev. 7 →   -7 After F's judged again i got WA in pretest 5. I found a bug after ~10 sec after WA
•  » » 7 years ago, # ^ |   0 Out of curiosity, what would your rank (approx.) be if it passed?
•  » » » 7 years ago, # ^ |   0 ~35
•  » » » » 7 years ago, # ^ |   0 So you (possibly) lost a place in the final round...
•  » » » » » 7 years ago, # ^ |   0 Yep :(
•  » » » » » » 7 years ago, # ^ |   0 Or not. Since you failed a more valuable problem.
•  » » » » » » » 7 years ago, # ^ |   +54 Now i feel better :D
•  » » 7 years ago, # ^ |   +25 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?)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 Yes, it is. Welcome to codeforces in 2016.
 » 7 years ago, # |   -13 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.
•  » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # |   +18 I am waiting for one day that contests come without delay :-"
 » 7 years ago, # |   0 What is the hack test for B? I solved it, buy I can't see some 'tricky' tests...
•  » » 7 years ago, # ^ |   +3 Answer doesn't fit in an int, that's how I was hacked.
 » 7 years ago, # |   +41 Enable upsolving please!
 » 7 years ago, # |   +12 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.
 » 7 years ago, # |   -20 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
•  » » 7 years ago, # ^ |   +22 I know, right?! It's killing me waiting, just tell us something!
 » 7 years ago, # |   +17 So MiracleFaFa was able to solve all problems in just 1:24 , this guy is the next big thing.
 » 7 years ago, # |   -26 It seems like the ratings are finally updated! tourist got Problem G wrong! Petr went up 181 points and MiracleFaFa 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 MiracleFaFa had competed in contest as tourist and Petr...
 » 7 years ago, # | ← Rev. 3 →   +21 My submission got AC, but i found test, where my code failedProblem : 645D - Robot Rapping Results Report7 61 22 33 44 53 66 7My output: 6Right answer: -1Code : 16818709
•  » » 7 years ago, # ^ |   +26 LOL, my solution(16818709) doesn't work on test:3 21 21 3My output : 2Right answer : -1WHAT???? HOW???...very good tests...
•  » » » 7 years ago, # ^ |   -7 Very poor test cases! Such solutions should not get AC! LOL ^_^
 » 7 years ago, # |   0 Serious question: does the final round have English problem statements?
•  » » 7 years ago, # ^ |   0 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.
•  » » 7 years ago, # ^ |   0 No. I mean the official round. The availability of English statements in final round will affect my decision of going to Moscow or not.
•  » » » 7 years ago, # ^ |   +10 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 :-)