Welcome to Codeforces Round #134!

After over two years, it is again my great pleasure to be the main problemsetter of a contest on Codeforces. Thanks a lot to Gerald for helping me organize the round. I hope you will enjoy solving the problems as much as we enjoyed preparing them for you.

Dynamic scoring will be used, but the problems will be ordered by their expected difficulty, from easiest to hardest. Are our predictions correct? I am eager to see. :-)

Good luck!

**Update:** The contest is over! Here are the results:

**First division:**

All contestants from the top seven solved three problems. Note that there was a tie for second place. :-)

**Second division**

In second division, seventeen contestants solved four problems. Nobody managed to crack E; it was also present in the first division as problem C, and proved tricky even for the experienced competitors.

Congratulations to the winners!

Анонс как-то слишком заранее сделан... Давно такого не было.

А CFR129 давно был? И в нем анонс еще раньше сделан.

Он будет утром... если сейчас не анонсировать кучу народа может просто подумать что контест завтра вечером и проспать (вообще наверное это надо было напомнить в топике).

Can someone translate this for me please? I feel left out!

...But when i do "you don't know what i am saying"

Thanks for your hardwork,and I must say that I love the sentence "but the problems will be ordered by their expected difficulty, from easiest to hardest" most.Hope to solve as much as I can.

Registration duration is diffirence,only 9 hour and 30 minutes, will be start 01:00AM,will be end 10:30AM

Why have negative votes,He is true.

As mentioned before. One does not simply try to understand negative votes on codeforces.

And the score distribution is… :-?

There is dynamic scoring. Read this for more information: http://codeforces.com/blog/entry/4172

Good luck, everybody!

and have fun!

and read every problem statement! ^_^

attentively

I'm so happy, that round start 5mins after full hour :D

Объясните, пожалуйста, D div 2) Больше часа на ней просидел( Explain , plz , D div 2)

translate from google:

`Explain, please, D div 2) more than an hour spent on it (`

Hint: use Euclidean algorithm.

Ok, thanks, I think about it

Think backwards: if a>b then (a, b) -> (a, b-a)

Great contest! All tasks were very interesting, even A(Div 2)!

Сорри, поспешил.

Problem B is fine. Solution is easy but I could not guess it during the contest...

Nice problem-set but two 500 pointers in div 2, and no 1500 or 2000 pointers in between 1000 and 3000 seemed odd.(Though it happened due to dynamic scoring)

It's a nice contest!Well done problemsetter meret!

How soon will the rating be refreshed?

Nice problems.I'm looking forward to tutorial because nobody solved all problems.

Wish meret would write the editorial.

I'm eager to learn to solve problem D and E.

Nice problem C div 2. I was studying Graph Theory some hours ago and I got AC in this problem with a DFS.

I use UFS in this problem.I think this problem is very flexible,and there's more than one way to solve it.

What is UFS, I never heard this algorithm, by the way I solved this problem with Union-Find Set.

Union-Find Set.A useful data structure.

shater -_-

UFS is a better choice.

Problem E is so Hard..

is there any other way (other than graph theory) to solve the problem C(div 2)?if yes,can anyone provide a hint..

You can use DSU.

sorry，what's DSU short for?

Disjoint-Set Union

Disjoint sets data structure

Just wrote a code that solves it without explicitly involving graphs: 2031563

The idea is the same as in the graph solution, you just assign each point to a group as you process the input (creating a new group when a point you just added has no other reachable point), and if necessary merge groups if a point is found that merges some groups together. The result is the amount of groups minus 1.

This problem can be solved in N log N time with union find. I think I wrote a good example http://codeforces.com/contest/218/submission/2046921

[user:meret]will someone write the editorial???

In Problem B Div.1 (Blackboard Fibonacci), I try to run the large test case (

`999997 999997`

) in`www.Ideone.com`

and my laptop then I got runtime Error. But when i submit it to Codeforces system, it accepted :-o (Although the final test has the same test case :-o)My submission:

Codeforces

Ideone

Can anyone tell me why?

Maybe problem is in stack size, because you use recursion.

Here, on CodeForces, stacksize is increased for g++ using compilation string

Thank you!

Upd:Another Online Judge don't increase stacksize :-(, so my solution can't get AC in some problems. Is it possible to increase stacksize in C++ source code :-(.As far as I know

`#pragma comment(linker, “/STACK: 268435456”)`

works only in MS Visual C++.How about G++ compiler ?

AFAIK, there no way to do in G++, but you can write your problem not recoursively(or use MSVC++, of course)

I don't know if DIV I — C was so hard or DIV I — B was hard enough that people spent a lot of time in that problem and didn't have enough time for problem C.

BTW... My solution for DIV I — B was hacked during the contest and I couldn't fix it... The test case? 1 1... I hardcoded it as

T

instead of

0 T

EDIT: Fixing that case passed system test after contest was over.

I feel your pain.

Thanks for holding a match at a different time than usual. I enjoy Codeforces contests but have a hard time competing at the usual time. I enjoyed these problems and hope I don't have to wait so long before my next contest.

To the opposite, it was really hard for me to compete here, in Russia, because of that awful Saturday morning:( I wish next time morning-contests would be held one or two hours later — just to have a good sleep... please!:-)

Oh, common, 11am is not a problem, SRM at 5am is :)

Please think about other countries.For example,the usual contest time(7:30PM Moscow Time) is 11:30PM in China.So I think we should have more contests at times like this one.

Ok, so why not to have contests always at different time?

Could anyone tell me how to solve Problem E of Div1?Thanks.

I have solved the problem.

YM I haven't solve C of Div1 now. I can't understand the code. So I play DotA.. How can you solve D and E?

Indeed，my solution is the same as panyuchao's

you need idea? or to know how solved problem?

authors and solutios:

Solutions 2032857 2029369 are very different.

Submissions 2033918 and 2028007 are also very different!

Could anyone tell me how to solve Problem C of Div1 (Problem E of Div2)? I have seen some codes but I still can't understand them. Who can give me some hints or useful conclusions to solve this problem? Thanks very very much!

It sufficient to look at the subsets of size 1 or 2, instead of all subsets of colonies {

c_{1}, ...,c_{n}}.Replace each '?' by either

c_{i}orc_{j},iandjbeing arbitrary for now. Look at the values in the four cases (c_{i},c_{j}) = (0, 0), (0, 1), (1, 0) or (1, 1).For example, for (

c_{i}&(c_{i}&c_{j})) we would get 0, 0, 0, 1. Note that there's only one way to get 1.iandj, and the answer will be "YES".c_{i}orc_{j}, the answer will be "YES".Thank you very much.Supose that F(ci,cj) is the result of permulation,what is the inital value of F(0,0) F(0,1) F(1,0) F(1,1)? Thank you.

You can compute the values taken in the four cases recursively. Look at this submission for a better idea: 2032900

Could any one can explain why "not all colonies are of the same type" is so important ? ..

“not all colonies are of the same type” is important for '((?^?)&?)'

I Got!..

Could anyone provide some tricky test cases for Div1-C? I am failing case 13 and its huge :/ (all the tests after 13 are huge too..) Thank you.

'((?^?)|(?^?))'

why the editorial is not uploaded yet ?

It looks weird to have 7 people in top 6 when the "6th" place is non-tied. If there is a 2-way tie at place n, I believe the standard way is to denote the next place (n+2), not (n+1).

This is how I did it in the code of the message, for some reason the system replaces it with the enumeration that you see.

No editorial yet ... :/

Here

I meant editorial for all problems. In the link given by you, there is no editorial for 218B - Airport. I was searching for its dp solution.