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

**CROC 2016 — Elimination Round**

**CROC 2016 — Elimination Round (Rated Unofficial Edition)**

Hope for hard data structures!

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

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

Karma police, I see your work

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

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

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

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!

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?

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.

MooooOOMOoOOOOMOoOOOoMOOoOooMOooOoOMOOooOOMOOoOoo

7 problems and 2 hours ? :(

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.

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

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

seems like problems are in easy side (?)

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

Oh thank god! A rated contest is here.

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

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

I somehow missed this line, my bad :/

finally rated round.

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 ?

I postponed registration to IndiaHacks 2016 to make it clear.

nothing. thanks for reply and votes..

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

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?

Totally agree.

In the last minutes in the qualification round TooDifficuIt 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 TooDifficuIt can not compete well in the official version, we all know who TooDifficuIt 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.

It's Too Difficu1t to FST.

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

Totally disagree.

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

Don't take too much stress, maybe today you will become specialist :D

Good luck

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 ? :\

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

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

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

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

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

My performance on Codeforces is getting worse:

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

But your rating was increasing except the last one :/ :/ :/

and his rank was decreasing except the last one :|

sometimes sequences are more complex than you think

I am hoping to see tourist surpass rating 4000.

Yes, I am hoping too)

I guess Codeforces should then think about adding another title named "tourist" :D

Legend says one day tourist will cause an integer overflow!

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

not able to submit E

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

Yes, many ways to solve a problem is a good stuff.

Thanks Zlobober! I'm glad you enjoyed our problems! :)

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?

Same problem, 16795467.

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. :("

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.

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.

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

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

For me — RE: 16795457

The same.

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

Systest when?

It seems there are some problem with the problem F.

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

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?

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.

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.

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

Seems like tourist is not going to get his 4k rating.

UPD: He is.UPD2: He isn't. :(You know, he's the master of last minute submissions

He is.

WA66 :(

How to do E?

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

cwhich came last to the end of string.See the second accepted answer here http://stackoverflow.com/questions/5151483/how-to-find-the-number-of-distinct-subsequences-of-a-string

Now, 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]).

Do you pick the earliest character to minimise the loss from

`dp[last[s[i]] - 1]`

?Yes, yes. Precisely.

Thanks for the link. :)

You must be kidding...

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

Opera... You must be kidding...

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

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

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

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

Found the mistake. Gotta upsolve :)

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 pairi,jof vertices either path existsi→jorj→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 ifborcis better.I found the mistake. Gotta upsolve :)

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.

Yeah that's at least one of the mistakes :)

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

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.

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

How did you do it without binary search ??

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

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.

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?

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...+1, same problem. Pretests can theoretically be different from samples, but why then don't we have minuses in the scoreboard?

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

Yes

The same. Somebody should investigate it.

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

It has to be not necessary!

You should be guess.

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

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

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

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

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

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

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

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

I used binary search on covered range

r. Then for each possible positioniof the farmer in the array I checked if[i-r, i+r]could accommodatekcows and the farmer. With an array of sums it's possible to check each position in O(1).How you used ternary search?

This is my approach-prefix sum of

zeroesfrom 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

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

so you can calculate the answer with O(N)

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

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

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)

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

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?

Yes.

Thank you :)

In this case you get a 50 points penalty.

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 test

100000 50000

0000...000

didn't fail this solution... =(

Can anyone pls help?

It is similar to v.pop_front(), so it does`nt waste linear time

But std::vector doesn't have pop_front() method

Bet on

`#define vector deque`

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

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.

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.

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

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

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.

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

Estimated time till start of system test?

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

Auto comment: topic has been updated by GlebsHP (previous revision, new revision, compare).Pending system testing, same old story :3

this is the fourth time in a row for div1 as far as I remember

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

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

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

kingofnumbers You are saying that Hamiltonian path problem is easier than topological sorting :P

In a DAG it is :P

Oh, yes, true. My mistake. I thought of generalized versions.

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.

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

Binary search the answer.

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.

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.

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.

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?

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

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.

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.

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.

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

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

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

"something like dijkstra or prim" should be topological sorting, I suppose.

yes u r right :)

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

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

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.

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.

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.

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.

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

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 )

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.

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.

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

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

I think he means the first solution that passes system test

Passed system tests, not pretests.

Ok. Sorry. Didn't notice

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.

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

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

~35

So you (possibly) lost a place in the final round...

Yep :(

Or not. Since you failed a more valuable problem.

Now i feel better :D

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

Yes, it is. Welcome to codeforces in 2016.

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.

Solution for

problem c:First

computeino(n) foreach room x"how many cows can I allocate if I occupy all places[0,x]inclusive?" store them asP[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 calculateP[b] -P[a- 1].And to actually

solvethe problem we do a binary searchcan I allocate cows making max distance of y?We can answer this question ino(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.I am waiting for one day that contests come without delay :-"

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

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

Enable upsolving please!

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.

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

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

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

It seems like the ratings are finally updated! tourist got Problem G wrong! Petr went up 181 points and TooDifficuIt 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 TooDifficuIt had competed in contest as tourist and Petr...

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

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

Very poor test cases! Such solutions should not get AC! LOL ^_^

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

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.

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

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