Hi all!

Authors of today's round are craus and dalex. We just couldn't miss the round with such a beautiful number, so at 19.30 MSK you will solve problems which were invented by Pavel and prepared by me.

We thank Gerald and Delinur for their help in contest preparation and MikeMirzayanov for creating Codeforces.

Scoring system and score distribution will be published when the round starts. Anyway this information makes no sense unless the round begins.

We wish you accepted solutions and successful hacks!

**UPD.** Contest is over, congratulations to the winners!

Div. 1:

1. Petr

2. tourist

3. Egor

Div. 2:

1. k3e18

2. tongcx1988

3. LeMieux

**UPD. 2** Problem analysis is published.

Does that mean there will be some problems have tricks, and there will be a chance to hack for getting higher scores?:D

That was a great contest! Good problems! New ideas!

Thank You!

"Scoring system and score distribution will be published when the round starts. Anyway this information makes no sense unless the round begins."

lol, I guess the setters are fed up with comments like "Only 10min/5min/30sec left before contest and there is still no updates!!"

Best wishes to every one!!

Don' t have time to take part, what a pity. Anyway, wish everyone a high rating [By the way, this is the 222ed round, so I guess there will be some prblems about twos. So try to search for some information ~ . Well,just kidding ]:):)

Keep in mind that this will be a historic round, because today for the first time I'll become a redcoder :P.

Aha, Good luck to you. I'll pay attention to your performance on this round. :D

may the (code)force be with you ;)

I hate starwars.

You Sith !!

Now I hate it more!

Good Luck Swistakk:) May God with you today :)

Congratulations =)

Did it :D!

Wow... Congrats! You barely made it, but I would like to have your confidence. Because I have lost it competing here :D

congratulation :D Swistakk

By 1 point :D Happy New Year :)

Congratulations!!!

`Astonished`

seeing your confidence !!!! Great !!! :)and you really made it!!! congratulations man :)

challenge succeed!!!.... what a confidence!!! congratulation....

You can't wish us accepted solutions and successful hacks! That's a paradox. :D

Or maybe after we get hacked a few times we'll finally reach the good solution / program?

thats always the case with wishing 'high ratings' also as it is designed in such a way that if one gains someone else loses.

Please vote "I like it".

Is this the new trend or something? Seems like there is always somebody asking for upvote or downvote in every contest. I am kind of curious now to see how long this will continue :p

I did not read related comments before, therefore I do not know that others ask for up-vote or down-vote. Just do it for fun, nothing more.

Yep. Good luck to me and everyone else ~

We wish you accepted solutions and

`successful hacks`

!(Y)

What's the idea behind putting STRONG pretests?! Hacking is almost impossible!

Well, when hacking is "I know one tricky case, and I'll check if all solutions works on it" It's not very interesting too.

Pretests aren't strong today BTW at least in Div1.C. My solution is absolutely wrong but passed them.

Well, it's not even like this. Even the extreme cases (big input) were present in the pretests! Some people in div2 got TLE because their algorithms were not to run in time under the problem constraints, I'm amazed that such cases were included in the pretests!

Possible, in Div2 A, there is no test when

a=b;)I hacked three submissions with a==b test. ^_^ .. Happy today.

Maybe they wanted to make a more classic contest, but Codeforces is neither a classic type of contest nor an ACM type. So there is no point in very strong pretests. Problem C on Div2 could have had some cases not included in the pretests (like the case with all the matrix full, when the DFS should not be called at all).

I didn't use dfs at all, my solution is kLogn + kLogm using segment tree, some people used sqrt segmentation.

PS: failed sys test

It's fun to see a problem about Dota 2 :P

the second last codeforces round of this year and nice one..

Just got a popup message there is another round on 30th, which will be rated for both Divisions

Incredibly simple A (and impossible to hack as I've seen), simple DFS on C, hard to understand the statement on B (the explained sample though saved the day), not so hard solution (here the intuition on why it works was more important than the proof itself). Nice round for the 2nd last contest of this year. "Authors of today's round are craus and dalex" — keep up the good work.

Three succesful hacks on A. :P

Well, at least in my room, most solutions to A had the case a==b included in them (I tried at least 10 submissions).

I was able to hack on A LOL :D

In Div2 B, I forgot to make size of my array which contains merged

aandbto 2 * 10^{5}. Instead the size was 10^{5}. I wonder, will it fail or not? :|Probably it will fail, but, as all of us know, everything is possible. Tell us if it failed or not.

I tested my code on "custom test". I thought it would get AC or RTE but not WA. As in "custom test" there were no RTE, I gave up resubmitting. And now I got WA 37. :)

FAILEDT_TI am interested is problem D Solvable by (Binay Search of Answer)+(Data structure)?

Let's find the amount of days we need to fix bugs with binary search. Now, let's check that k days is enough to do it. First of all sort the bugs. Then iterate through them and for each of them find a student with the minimal c that can fix(b >= a[i]) the bug using set<pair<int,int> >. And he also will fix next k — 1 bugs. If every time we have a student to do it(set is not empty) and the sum of all c is less or equals to s then we can do it. P.S for some reason my solution gets TLE on 9 test :(

can't submit in the last 10s ? I submit my solution in the last 10s,but failed to submit

Wow! Amazing strong-willed victory by Petr!

Congratulations :)

Failed Div2 Problem D because my program output N0 instead of NO ...

In Div 2 A all different possible test cases is 6*6 = 36 but there is 38 test cases LOL :)

Thank you for the nice contest! I've enjoyed it :). By the way, I got RE on problem B div1. But I've correct output at CF server (and on my local machine), and I can't see why it got RE. Can somebody tell me what I've done?

My submission is here. => http://codeforces.com/contest/377/submission/5561801

(UPD)I've submitted same code at practice, and got AC. http://codeforces.com/contest/377/submission/5562952It seems to depends on the version of glibc.

Using glibc with version 2.15, I got RE.

I hope this information is useful.

Using the GNU C++ library debug mode, I get

on that test, which means that you attempt to access an empty priority queue.

It seems you had undefined behavior as mentioned by andreyv. But New Year will be soon, so it's time for miracles. Usually I do not do it, I rejudged your solution and got OK. Ratings will be updated soon. Happy New Year!

To : numa and andreyv

Thank you for investigating environments and my code! I'll be careful from now on. I'm glad to know the reasons :).

To : MikeMirzayanov

Thanks for the rejudging! It seems that I was very lucky!

And again, thanks for all whom tried to help me, and craus and dalex for helding a wonderful contest. Happy New Year for all!

Very Fast system test. Loved it :)

Why am I Expert with rating 1703 !?

and I am Specialist with 1501!

And I am

Pupilwith rating 1504 !!Thanks :D...I do on ideone without making it private.Have to take care from next time :(

Maybe your solution and another one's solution were same.

Div. 1Div. 2More info

Hi If you visit my profile, KiAsaGibona my rating is 1504. And when I take my mouse at the graph, it says

EXPERT, But I am stillPupil. As far I know 1501-1700 isExpertrange. But I am 1504 and stillPupil. I want to be blue :( :(I saw this bug in other profiles too. I think it will be fixed soon.

Its not a bug. Let the system alone it is working hard coloring coders :D

Let's hope so, As I am going to be

Bluefor first time. Yayyy :)[1500,1699] is Expert range not [1501,1700] . :)

I have the same problem. My rating has changed BUT the title and color is still NOT updated yet... Hope someone could help? Thanks!

I took part in this contest but my rating hasn't changed (I submitted for problem A, div 2). I noticed that the ratings of other Div 2 participants has changed, but mine not. Could someone tell me why this happened?

Same here. For a moment, I thought that my rating remained constant, which is rare :P

Are you sure you registered for the contest?

I'm sure. the submission during the contest: http://codeforces.com/contest/378/submission/5553767

and the registered participants: http://codeforces.com/contestRegistrants/378/page/10?order=BY_RATING_DESC #2316

My rating didn't change too

My rating is the same

Can someone explain why DFS works for Div2 C?

flood fill s-k cells, that will remain empty. Mark the rest as 'X'.

@dbaluta As given graph is connected & consists of

sempty cells, so, Run DFS from any empty cells & mark only(s-k)cells visited. Then, simply print the solutionwriting empty unmarked cell X. Thats all :)For any cell, i can delete it if i am sure it won't block the path to any other "not deleted" node.

So from every cell (x) ,we run dfs to delete cells reachable from (x).

After deleting them, if i want to delete more cells, then it is safe to delete cell (x).

--> Consider all the blocks where you have '.' as nodes..

--> Now as you can read in the problem description , all the '.' are initially connected..

--> So now you have a connected component with you..

--> You have to now turn K '.' cells into WALL so that the component is still CONNECTED..

--> Now , the Picture of DFS comes into the mind.. DFS will traverse all the nodes and will backtrack as soon as it reaches 'LEAF' node.. If you turn those leaf nodes into WALL your graph will still be a connected one!!

Hope it helped!! :-)

Thanks a lot guys! Now is all clear :).

i got wa on test 89 :( I had done bfs and marked levels.Then removed k nodes which have the highest levels.

Actually BFS should work : 5554249

Now tourist really have to be ranked FIRST if he wants to increase his rating :o

Думаю он может подняться со 2, если первым будет rng (судя по тому как считается рейтинг)

if his rank will be 2,and rng_58 rank 1,his rating will increase ;)

See these solutions : 5560186 5560332

Hey my raiting chnged to 1501 but y i am still graded as pupil?

As noone has already done it, I will present solution to Div1 C, because in my opinion it is pretty funny and short.

We just have to completely forget about n-m weakest heros and bruteforce remaining ones in O(2^m * m) using simple dp on masks. Why it is correct?

In short, if we pick — we pick strongest one and if we ban a "bad" hero it doesn't matter which one (from the "bad" ones) we ban. It is obvious that if someone have to pick a hero, the best choice is to pick the strongest hero from remaining ones. So in a fixed moment of the game, if players will have to make k decisions, all picks will be among k actual best heros. Let us call that other heros are bad. Bad heros will never be picked. Since that, there is no point in missing a ban, because we can ban the weakest from remaining heros and that won't affect our solution, because noone will ever want to pick it. So if we consider an optimal sequence S1 of decisions for both players we can create another sequence S2 which will be still optimal for both players and chooses heros only from those m strongest ones. If there occurs missing a ban or banning a hero which can't be banned in S2, we ban the weakest remaining hero in S2 and there is no difference between those 2 choices in future picks, so these two states are equivalent.

Learn Russian, there are lots of comments with discussions of solutions after each round in our language =)

If I'm not mistaken E is fairly easy. I will describe a solution with assumption that everything is continuous, not like in the problem statement (it's essentially the same problem, but easier to describe). Think about a whole process in a coordinate system OX — time axis and OY — cookies axis. Firstly sort buildings due to cookies per second (= possible slopes of our cookie graph) and process them in this order. After adding each building we want to maintain a graph of "maximum number of cookies we can achieve in a time t" — this graph consists of consecutive segments of lines with ascending slopes. It can be kept in a vector. When adding a building, we have to find first moment T (by binary search) when we can afford building it and update our graph (that means, finding an intersection of our graph and line passing through (T, 0) with slope corresponding to this building production. Just pop a few last elements of vector and push_back a new one. If we won't process buildings b such that there exists a building c such that c is cheaper and has bigger production, we can achieve O(n) time not O(n log n) by omiting binary search.

This is convex hull optimization right? I didn't do contest because it was too late and I was tired, but I looked at questions and that is what I thought, but I wasn't sure because it was E and I thought it must be more complicated :P

Edit: Actually I think I was wrong.

Can anyone explain me how to solve Div2 C/Div1 A?

Can any one tell me about Good Bye — 2013 contest in detail? :)

Well , my solution in Div2C is based on BFS , then there has a BFS tree when we run BFS then we can disconect their leaves( this are the nodes more farthest) .

My submission. Code

please can any one explain how good bye round will be for both divisions !? and how the rating system will be ?

You can see here :)

Wow, Zlobober became the new International Grandmaster, Congratulations! :)

How do you solve Div 1 Developing Game?

I think there is a much simpler Greedy solution to Div 2 C. For each row note the number of empty cells in that row. Now if we have to delete k of the cells then we can completely convert the initial rows to X,such that the no of cells left in the row (which u have just processed ) is more than the number of cells left to convert to X. Now if there are some cells still left to convert ,except the cells which are connected to the row just immediately down u can convert into X. This algo works since when we convert entire intial rows to X the remaining is still connected.

In the problem B div 1, can anyone tell me why my JAVA solution got TLE (I do it in O(nlogn^2) : (.

(http://codeforces.com/contest/377/submission/5559914)

After the contest, I tried to rewrite it in C++ and got AC in 156 ms : (

Try to use classes with ints instead of Pairs of Integers and PriorityQueue instead of TreeSet.

Thanks, I tried to use classes with ints instead of Pairs of Integers and got Accepted @[email protected]

The objected data is so slow @[email protected]

Screencast

I think the test data of Div.1 E (Cookie Clicker) is not so strong for a Div.1 E problem. A simple

O(n^{2}) solution passes all the tests. In 5604868 I just deleted all the buildings which cannot be used in the optimal answer, using the method mentioned on the top of the editorial, and then used simpleO(n^{2}) dynamic programming.Thank you! It seems that in random tests this condition:

`if(a[q[qe-1]].v<a[i].v)`

is false very often.You have TL now.

I've rejudged all accepted solutions that were submitted after the contest. Contest submissions are OK.