Hello Codeforces!

The Final Round of CROC 2016 will be held today at 17:15 Moscow time, where the best 50 participants from the Elimination Round will be competing for the valueable prices, as well as for their personal entertainment.

Everyone else will be able to participate in Codeforces Round #347 tomorrow at 19:35 Moscow time that will feature an almost identical problem set. It is going to be a usual **unrated** round, separate for each division.

The problem set was prepared by Evgeny Vihrov (gen), the one and only coordinator of Codeforces Gleb Evstropov (GlebsHP) and me. I would also like to thank Mike Mirzayanov (MikeMirzayanov) and all of the Codeforces team for the incredible contest development system and Alexander Fetisov (AlexFetisov) for test-solving the problems.

During the Final Round the contest scoreboard will be linked here, but the problems themselves will be available only tomorrow.

We hope that you like our problems. Good luck to the finalists and to everyone else tomorrow!

**UPD 1**: The link to the current standings: http://codeforces.com/spectator/contest/662/standings

**UPD 2**: Codeforces Round #347 will be unrated.

**UPD 3**: Scoring:

Div 1: 500 — 1000 — 1500 — **2500** — 2500

Div 2: 500 — 1000 — 1500 — 2000 — **3000**

**UPD 4**: Congratulations to the winners!

The Final Round of CROC 2016 | Codeforces Round #347 (Div 1) | Codeforces Round #347 (Div 2) |

**UPD 5**: Editorial: http://codeforces.com/blog/entry/44408

Finally, a rated round :D

No, it will be unrated. :(

UPD 2: Codeforces Round #347 will be unrated.Yeah I saw that earlier, Too bad :(

Unrated??? Oh no... :(

For this contest, it's good to be unrated, if this round was rated, it will be unfair round because of solution leak.

You've jinxed it...

NO! Why contest is unrated? We waited a lots of time and finally unrated?

best 50 participants from theQualification Roundwill be competingI think you mean Elimination Round..

Fixed, thanks. It is better to write about such mistakes through a private message.

Then do you give him positive contribution?

So, perhaps some people will have privilleged information about the problems appearing in the rated round tomorrow, e.g. friends of the 50 people competing today.

Exactly! I'm going to send the problems to everyone I know ohwait pretty much none of them compete these days

Won't the problems be harder than usual?

who is the champion? I cant open the standings page :(

Tourist!

"Everyone else will be able to participate in Codeforces Round #347 tomorrow at 19:35 Moscow time that will feature an almost identical problem set. It is going to be a usual rated round, separate for each division." There are something error? I've seen the code of tourist and everyone else, and the problem are the same :)

Just when I thought "finally a rated contest"

Another month for a rated Codeforces Round I guess?

So, everyone can participate in the round except for you :3

Are you trolling? I hope you are...

how to solve D?

I saw the problems and didn't know the contest was private

Well D was truely what you call a brilliant problem, try reversing the queries (like in problem Parking Lot (480E)) it will be really easier, since everybody may not want to see the solution see it at previous edit.

EDIT: Oh !! i just noticed that you guys that didn't participate onsite (well i did) could be lying that you saw the problems :OOOOOOO !!!! >_< !!

Saw a funny bug after the rating updates:

So, Finally my dream of getting a better rating than tourist came true :D

As tourist's rating can get very high they count it modulo something, lol. I think the actual problem is rating overflow.

Which gives you hope that your contribution may one-day underflow :D

Well he has a long way to go....

I think it probably is an overflow haha

a link to the position participants not working

Cheat...

ADMINISTRATORS PLEASE STOP IGNORING. REPLY ANYTHING ABOUT PEOPLE WHO SAW PROBLEMS' CODES

IS THE CONTEST GOING TO BE RATED OR NOT? IF RATED THEN HOW?

Stay calm my friend :v

It's like all admins went to sleep or something. Standings page is broken. Winners haven't been announced. No one commented anything about leaked Accepted codes. Do they want to run the contest anyway but don't want to say that?

Funny thing is that my comment might get deleted now. I once commented "Seriously? Delay?" and they deleted it after 1 minute.

Please, stop complaining Mahmoud . You are not the only one who is confused about the contest .

A rated contest after a while !

Now it's not :(

You have just greatly complicate the life of Codeforces and generally behave like assholes. It sometimes happens that something goes wrong. Making onsite events — a very complex activity. Codeforces team worked ~32 hours with 4 hours sleep break to make CROC Final, and we really wanted to make it not only for 44 participants but for all community. Most organizers do not make such events like: parallel rounds of onsites but Codeforces hold them many times. It is difficult and requires huge effort, but we did it to give the contests for community.

Why do you do like that,people aren't competing for rating,they are competing because they want to solve the problems by themselves and see their level,just be honest with you and don't look at the problems/solutions.Respect at least the people who give you opportunity to compete with others in a contest.

Codeforces rule #1: Don't upset mike.

What was in this comment?

As far as I know, there were links to the solution sources.

UPD: sorry, looks like I'm wrong and the comment with links was actually deleted.

btw several people contacted me and I didn't send them anything

it was only to make the community disallow the contest being rated

links to touris's solutions. ..

I could send you a screenshot but I guess that would be a "CF rules violation"

No, I didn't post links. The comment of the guy who posted the links was simply deleted (not partially deleted and kept for voting)

I don't see why it was necessary to create a rated round with identical problem set a day after. Unless it's a mirror round in real time I don't see how it would work well — information always leaks.

It seems now we have to do the round unrated. It is really pitty. It was my mistake that I accidentally opened the solutions for 15 minutes. I upset the behavior of some of the participants who did not give opportunities to others to fully take part in the round. I involved in programming contests for 15 years and I'm sure that this community rests on mutual respect and honesty. Yesterday it was impossible for us to run round in the same time or just after the Finals.

Why???

No rated contest today. Stay hungry :P

good luck on the journey from +129 contribution to -129 contribution :D

any chance of changing the problemset a bit ?

I understand, but sadly it takes just one person to ruin it for everybody. Hopefully the unrated round will still have high participation

I'm sure now that it's unrated more people will participate, because they will be sure that someone beating them because he has the codes wouldn't affect their rating.

well I dont know about Div1 but this would not affect Div2 guy's rating that much if you didnt spread it :| being in top 100 in Div2 would likely increase your rating and before spreading it at most 10 people had the solutions . i dont see that much effect . also it would be obvious that a Div2 guy cant solve all the problems so fast and it would be easy to catch cheats

oh really? how much did I spread it?

I'm not saying "CF is bad". it's just that the contest simply can't be rated if

atleast oneparticipant has the codes. And even if you catch someone who "obviously cheated", he can change the code and you won't have a proof for that he cheated (unless you want to do like Mike did with my comment that "violated CF rules")yeah well i can say that the writers of any contest can give the problems to their friends and no one can prove they have cheated ... i am not saying it's a good thing people saw the solutions but since the number of such people is so low they can be ignored

Well, Codeforces has a great history of conducting such rated rounds after onsite events, and usually it works ok. As for this round, two factors combined: Mike's mistake (that happens sometimes, we all are humans and perform mistakes) and dumb behavior of some members of community.

Shit happens, at least trying to conduct a round is better than doing nothing at all.

So there are going to be people in today's contest that already have the solutions for the problems? If today's problem set is identical to yesterday's, then they should probably call it off since there will be people that cheat their way to the top. Kind of unfair, hopefully there's some solution to this.

Edit: Looks like MikeMirzayanov is just going to make it unrated. That sucks, but I guess it's the best solution.

I've been waiting for a rated round sooooo long. Huh...oh wait my luck just steped in. U know what gray kinda suits me.

not rated :(

i think unrated contest is the best solution in this situation because the solutions have been revealed

The announcement still says "usual rated round" . Which is it rated or unrated ?

Any chance for changing problemset a little bit?

You can change constraints a bit, for example: from

n= 100 000 ton= 200 000. If somebody submits a solution with old constraints — ban it! :DVery funny

Can the problem set of Educational Codeforces round be used? It is going to take place in just a few days.

Nice Idea!!!!!

Generally speaking, the problems in an Educational Codeforces round are some of the more "classical" problems unfit for a regular contest. In any case, it would not be a good idea anyway, changing all the problems last-minute.

I think Codeforces must be having some tested-and-ready-for-programming-contest problems. They can be used. Please have a rated round :|

maybe we can make the Educational round rated, it would be sad to wait for another two weeks to participate in a rated round :(

I think this may be a good idea. If necessary they may delay the round. After all, it has been a long time since a rated contest .

In my case, I will take part on the contest if it is unrated, since being rated makes mee feel unconfortable given the situation. Being rated or not, trying to solve the problems is interesting.

Mike, can we please have a final confirmation from your side whether the round will be rated or not , it will greatly resolve the confusion ...

please look at the end of the post !

oh thanx , just saw that :)

It's unrated as is stated in UPD2.

see UPD2

So bad>_<... Can't participate in any rated contest in long time. TAT

Codeforces Round #347 will be unratedGot too excited after seeing a rated codeforces round :v But, UPD 2: this round will be unrated :( Have to wait :(

And that was the reason why, on 4/16/2016, I decided to quit competitive programming. Good bye CF community!

If I asked you to go and kill yourself, will you post an image for my request saying "that was the reason why I killed myself", then go kill yourself?

Only if you make me realise that I'm a loser like he did.

Clearly , he is just making fun of this dude,who want him to leave CF

Right, May we forgive ourselves :}.

Sorry "repeated comment"

too many unrated rounds recent times :(

"It is going to be a usual unrated round, separate for each division."

Once upon a time rated rounds were usual not unrated ones.....

people calm down it isn't that big of a deal. first, tweety did nothing wrong in fact he was making sure the rules weren't violated. second, so a rated round turned unrated so what I'm gray I'm dying for a round and still I'm not bothered by the fact that someone turned it unrated (what would you all do if it was mike who said there were leaks and the round will be unrated???) third, I can't believe that the whole CF community was shaken by such a small mistake.

A, B, C was tasks for improve realization) LoL)))

And after all this mess tweety did't participate :3 .

Electricity in Syria is not always on. I usually save my laptop's battery for CF contests, but today I had to waste it on silly arguments here (after which I turned out to be a bad guy who

forcedCF team's decision to make the round unrated). I wish one could participate from his smartphoneI did't have electrical power ,too :\ .

Yes you're evil, you're more than evil.

You saved me too because my electricity gone at the middle of contest....

Is there raining too?

"middle"

No, But in Syria the electricity cuts every 3 hours for 3 hours.

You could have commented on smartphone!

Oh shit...

Checkmate tweety, where's your problem solving skills now?

Codeforces should hold more rated contests and soon, as there is clearly a lack of rated contests. We finally a rated contest, and even that becomes unrated. :( Something has to be done about this.

All of us might feel bad that we lost a rated contest. I agree with you'll, even I was waiting desperately for a rated contest. However, we need to look at the bigger picture guys/gals. There was a solution leak a day in advance.. this is a major mistake and something should have been done about it earlier itself. Instead, all moderators and codeforces team decided to ignore the mistake and just remain silent and let a contest full of cheaters and wrong solutions take place.

I guess this is very wrong. It almost becomes a matter of luck something like "I saw the solution its my lucky day! let me increase my rating.." Then some guys like Tweety prevented this from happening and made people aware that the soultions are available and have been leaked. They , tired of the silence from codeforces moderators decided to share their codes so that such cheating does not happen.

For me , tweety saved me. I prefer a unrated contest than such cheating happening behind ignorance and a wall of silence. Thank You!.All hail tweety our saviour/ martyr (because some of his upvoted comments were deleted).

On a more serious note, I totally agree with you. I was going to participate blindly if it wasn't for tweety, and I would've probably lost a lot of my points because I didn't know that the solutions were leaked.

Let's all remind ourselves that it wasn't tweety who leaked the solutions. He was the one to draw attention to the fact, refusing to stand by while a few individuals took advantage of the situation.

The organizers might not like him for that, but it is something very common to have a scapegoat around for your screw ups and what better scapegoat than the one who drew attention to their mistakes in the first place.

Aaand now I feel like a superhero

Not his upvoted comment were deleted, but some comment which he has replayed to it were deleted.

I hope, next really rated round will be soon..

My hacks B:

Test:

`(0-5 ones)3098`

, Answer:`(1-6 ones)3098`

Test:

`(0-5 ones)3099`

, Answer:`(0-5 ones)3099`

Test:

`099999999`

, Answer:`1099999999`

You ruined my world :D

Good test on Rebus:

Answer is Impossible, right?

1 + 1 + 1 + 1 — 2 = 2

Now i knew why i couldn't get pretests passed for it :(

Even "Pretests passed" solutions fails on this test.

Try chrome (11th place) solution for instance.

Here is my brute-force solution,without any cases

Thanks, I was afraid of being in first hundred in unrated round:D

P.S. Hmmmmpphhh.... I still in first hundred:D

Why is everyone angry i can't believe that doing the good thing can make u hated a lot Really "no good deed goes unpunished " Tweety did the right thing reporting the cheaters For all we know the ones who are saying ban tweety could be one of the cheaters

I think tweety need to do rated contest. Let it be his apologize to the community.

I think that the one who accidentally left the solutions open to the public should make a rated contest soon.

Could you publish the onsite results now?

The moment I see the word 'unrated', I just want to cry :'(

Why? Why? Why? And why?

Haha I solved a totally different problem on B.

Given a list of abbreviations in order, find the smallest year matching each that hasn't been used before.

I didn't get that the queries were independent and only realized the true intent of the problem after an unsuccessful hack. I guess I tried to go too fast this time :)

So do I, I didn't realize IAP'00 is a valid abbreviation until got hacked T.T

ok i solved the same problem as yours only now i found out my mistake :))

Could anyone share their idea how to solve Div1 E?

Here's a sub-problem:

you are given at most 200000 "selected" 20-bit numbers. For each possible 20-bit number and each number k, find how many selected 20-bit numbers differ from this number in exactly k bits. This is done using DP.

You can compute freq[x] = number of times the bitmask x appears Also, compute cost[x] = min of (number of 1s, number of 0s).

You want to compute minimum over all j of the sum freq[j^x] * cost[x] (i.e. we flipped the rows according of to the bitmask of j).

You can compute sum freq[j^x] * cost[x] for all j in n*2^n time using a variant of fft. (You can see the editorial here: https://www.hackerrank.com/contests/back2school14/challenges/xor-subsequence for code).

An approach slightly different from the one described by Petr (might be easier to come up with, but is much slower): let's iterate over the first 13 bits. If the first 13 bits are fixed, each number becomes pair (distance on the first 13 bits, last 7 bits) — there are only 2

^{7}·14 such numbers. So, with this we can iterate over the last 7 bits and solve the task with brute force. The number of operations is 2^{13}·(100000 + 2^{7}·(2^{7}·14)), which is small enough.Obvious but slow solution: fix a mask of rows that we're going to flip. Now, for each column we can achieve

`min(ones(column[i] ^ rows_mask), n - ones(column[i] ^ rows_mask))`

ones (`^`

is XOR operator,`ones(X)`

is the number of bits equal to 1). Compute the sum of these values for all columns and find a minimum over all row masks. The complexity isO(2^{n}·m).Optimization: Split the rows into two groups of sizes A and B. Iterate over all masks of rows from group A and let's assume it's fixed now (and equal to X). For each column compute how many bits are equal to 1 in XOR of X and that column (let it be C[i]) and also let R[i] be a mask of remaining B rows for that column. Let's compute how many columns have the same values of C[i] and R[i] for all pairs of (C, R) (the number of these pairs is

A·2^{B}). Now, let's fix the mask of rows from group B (let it be Y) and iterate over all pairs of (C, R), each group will contribute`min(ones(Y ^ R) + C, n - (ones(Y ^ R) + C)) * cnt(C, R)`

to the overall sum. Notice that we actually don't need to iterate over all pairs (C, R) as it's enough to compute prefix sums for all C for a fixed R and then we can compute the minimum inO(1) using them. The complexity isO(2^{A}·(N+ 2^{2B}+ 2^{B}·A)) assuming that`ones(X)`

works inO(1). To choose A and B properly I just used a simple`for`

loop that tried all possible pairs, although one could easily find it on paper (e.g. for the max test the optimal values are A=12 ans B=8).UPD: ilyakor has already mentioned this approach without prefix sums

Thank you all a lot for three completely different solutions!

@Petr — I tried this approach during the contest, but didn't manage to do the DP — It's good to know that it's possible to finish that and now it's clear from your code how to do it exactly, thanks!

@Lewin — wow, I didn't expect anything like that

@ilyakor and KADR — indeed, your approach is slower, but surely easier to come up with, nice!

Below are 2 codes for DIV2 C

http://codeforces.com/contest/664/submission/17351450 above solution passed pretests

http://codeforces.com/contest/664/submission/17351613 above solution gave tle on pretest 1

What is causing code 2 to run slower than code 1?

Although due to mis-understanding the constraints of the problem, my code failed the system testing, but my code passed pretests and your's gave TLE on pretest 1 because your preprocesing loop, the one filling the map, runs for ~(2*10^5) times. Mine runs exactly half of it.

It has been long since the last rated contest. Please make the upcoming Educational Round rated. Rated contests are definitely more fun and challenging.

when will sytests start ?

How to solve this problem: http://www.codeforces.com/contest/664/problem/B Unfortunately my solution got hacked. Can anyone tell me the correct approach? Thank you

just make every integer 1,then make one integer bigger if it makes ans more closer to n,until it can't be bigger or equality holds and do the next integer

It's so sad to know the contest is unrated after it's finished for a student who has stayed up late to be a Candidate Master:( If I knew it's unrated I would choose to go to bed early

Fortunately, I overslept.

Why the compiler doesn't execute a lot of problem A c++ solutions?

It would have been much more fun if the contest was rated. Anyways good contest !

Lol, only two people in my room managed to solve 2 problems)

If I'm not mistaking, problem C from div2 has only 3 pretests (and you know 2 of them from statement). It means that contestants should not rely on pretests :D

Yes, I've forgotten one 'if'. I think many participants had a similar mistake.

well, the 3rd test contains 1000 testcases in it

What is the logic for DIV 2 C ?

We have string representing our "short year" (call it S). Let's denote ans(S) that calculate answer. Fact: if we have suffixes of S S1 ans S2; |S1| < |S2| then ans(S1) < ans (S2). So we can build answer suffix by suffix. Assume we built answer for suffix Si (|Si| = i; ans(Si) = Ai). So A(i + 1) > A(i). A(i + 1) % 10^(i + 1) must be equal to S(i + 1) % 10^(i + 1) and A(i + 1) must be minimal. We can represent A(i) as k * 10^(i + 1) + r (0 <= r < 10^(i + 1)). Now we have 2 cases:

1) S(i + 1) % 10^(i + 1) > r. Then A(i + 1) = k * 10^(i + 1) + S(i + 1) % 10^(i + 1). Easy to see that A(i + 1) correct answer.

2) S(i + 1) % 10^(i + 1) <= r. Then A(i + 1) = (k + 1) * 10^(i + 1) + S(i + 1) % 10^(i + 1).

Now if we assume A(0) = 1988, then A(|S|) = ans(S).

Example. S = "015".

A(0) = 1988 = 198 * 10 + 8. S1 = 5. 5 <= 8 => A(1) = 199 * 10 + 5 = 1995.

A(1) = 1995 = 19 * 100 + 95. S2 = 15. 15 <= 95 => A(2) = 20 * 100 + 15 = 2015.

A(2) = 2015 = 2 * 1000 + 15. S3 = 15. 15 <= 15 => A(3) = 3 * 1000 + 15 = 3015.

So answer for S = "015" is 3015.

You want to know what number chose that suffix. Simple observation from that is that each suffix of the suffix (except itself) was chosen before.(otherwise there was at least one smaller than itself,and it wouldn't choose it).

Now this is how I find the number. Let's take 3098 for example. You can also see that one which chose 8 is before the one who chose 98. Now the greedy approach is simple.Calculate who took the suffix with length 1,call it VAL. Calculate who took the suffix with length 2 and it's >VAL,... and so on. If you want to find the number which has the suffix p,the number looks like prefix+p (0<=pref<=inf).

In my solution I just binary searched prefix,and took the prefix which gave the smallest number > VAL. I saw other people just brute-force to find prefix(even if for prefixes of length 1 and 2 it takes some hundred steps,for other lengths is seems like it takes maximum 10).

Hope I helped you understand the greedy approach.

Example: IAO'1999 => from right to left: 9 => 1989 | 99 => 1999 | 999 => 2999 | 1999 => 11999

Can upsolving be enabled for the official contest? In particular one problem is not shared (Gambling Nim) and I want to submit for it.

EDIT: It's been enabled!

So much drama in one blog

How to solve Div1C / Div2D : Graph Coloring ?

well , we have two options for the final color (1 — red , 2 — blue )

suppose we want to color the graph with red

for each component this is the algorithm :

suppose we have a vertex v in this component .

again we have two options : change the color of all edges adjacent to vertex v , or don't do anything with v .

when you choose this option , you can run a dfs from this vertex , and you will know for each vertex of this component , what you should do with it ... (change it or not)

after that , you know what to do with the vertices of that component :D ( while running dfs , if you changed one vertex , you can mark it in a bool array or sth ..)

now you can easily know , what would be the color of the edges of this component ... (by using the information of each initial edge and the bool array we used) .

if all of them were equal to the final color (here it is red) , add the changed vertices to a list.

now , after you tested the 2 options for each component , if just one of them worked , just add it the the list of vertices for the final color which should be changed .

if both of them worked , add the one with the minimum number of vertices

and if none of them worked , sadly we can't color all of the edges with this especial color ( which was red here)

now do the same thing for the blue color

if you had 2 final list , print the one with minimum vertices

if you had only 1 list , just print it

if you hadn't any , print -1 :D

special thanks . I am trying to understand it...

That's why I hate Dynamic Scoring..

Why? I don't understand. Problem A of purple someone will fall anyway, but now you have 100 additional points.

Read the problem)))

Hopefully we will get the editorial soon.

Will there be an analysis of all the problems?

Can anyone tell me why the following approach fails for D div.2 (Graph Coloring):

By flip i mean change all edge color going from and to the node. Is the approach correct? Maybe I have an implementation problem.

This is what I did and the tests passed. I guess you didn't apply the idea for each connected component.

Any Idea for solving DIV 2 D , using DSU ?

though this problem is quite similar to 228 E.

Hey, for problem "To hack or not to hack", the tests are really weak, aren't they. I do a very silly greedy and still pass: Iterate through the list and try to minimise anyone higher. Is there anyone else having the same idea?