Hello everyone!

Codeforces Round #153 will take place on Thursday, December 6th at 19:30 MSK. This is my third Codeforces round and I hope there will be more.

I'd like to thank Shtrix, Seyaua, sdya and Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I hope you will like the problems.

Good luck and have fun!

**UPD**: Complete version of English editorial is now available.

Congratulations to the winners!

Division 1:

Division 2:

All that red color suggest a hard contest :)

I guess that not hard but interesting :)

Thx for negative votes :D

You're always welcome)

It's better to not write anything :)

It looks like NiVeR is trying to reach a new low of negative comment rating and he's doing a pretty good job at it. :)

And hes not alone :d

LMAO GUYS YOU'RE SO FUNNY)))))))))))))))))

OH MY GOD IT'S THE BEST JOKE I'VE HEARD!!!!)))))

Hope so :)

So gì mà so

This was discussed a short time ago: http://codeforces.com/blog/entry/5975

AT LAST !!

I have to go to school on Dec.7 Maybe i can't do this.

T T

:| who cares ??!!

Chinese education only has exams!

One guy already said WHO CARES but i think we should repeat it. WHO CARES.

So better go to school. You can use "virtual contest" in Codeforces, but you can't use "virtual life" option.

I understand you.

omg

yeees!Can you make more contests,please?It's boring when there's nothing on codeforces...:)

Are the scores of the problems decided? edit: Sorry, I was not asking for the scores of the problems, but if they will be static or dynamic :)

I think contest had better be arranged in Friday or Saturday，in that case more people can compete in contest.

No it wouldn't be better because we would had to wait more. Everyone is getting bored from waiting.

Let's hope the server will stable during competition

Let's pray for the welfare of the server. 42. Amen.

Seyaua, sdya are the same person ! :D****No. They are twins :D **** [link]

hmmm...but their pictures are same... how can it be?

I think it has been long since last competition. Thanks for all the contests and their makers, I really enjoy myself in the contests!

Good Luck Everybody!

Good luck everyone!! Have fun!! :D:D

Was I the only man who had "error 502" now?

There is one thing that I will never forget about this contest

There's only one thing Petya likes more than numbers: playing with little Masha.Little Petya likes "a lot of things" a lot :D

Sometimes you get a mistake, the author is the same :D Sorry for my bad english :p

I solve problem B of Div.1

then lock my answer

and go hack two contestant with same Test Case

but unfortunately when i checked my hack TC too my code , I saw my solve give WA too :|

What was the challenge case for Div 1 Problem B? No one did many challenges in my room, so my solution could be wrong :( .

2 3

2 1

2 1

Answer: NO

3 3

2 3 1

3 1 2

Answer: YES

Now that someone tells me, I'm scared of testing my code on it...

My code managed to pass those tests. Do you mind sharing what test you used to hack me?

4 3

2 3 1 4

3 1 2 4

YES?

Something like

4 7

2 1 4 3

2 1 4 3

NO?

Correct answer is "NO".

1 1 1 1

Answer NO :)

I think if there was no challenges, it would be a lot of WA. This task checks contestant's attention.

Very slow system testing :(

Are the solutions being checked manually?

Seems that they put too many test cases in Little Xor.

Sooooo slow system testing :(

The problems are harder and harder?T T need to work hard^ ^

Sorry to say but it's easier than the last contest :)

Unlike Codeforces Round #152, this contest has a very low speed system testing... :(

Everybody seems to get WA in test case 12 in Div 2 -problem B. I wonder what that test case is ?

I guess a case with n<3.

I think many people think that "-1"'s case is only on n <= 2 and all array fill whit the same number. if N = 3 and array is {2, 1, 2} we can't do any swap.

You can see this test case after the contest.

System testing has already lasted 20 minutes, but checked solutions of first 15 minutes of contest, that's amazing speed:)

why you need that too many test cases !!! :o

very slow test system(((

Seems strange, but I think Problem B was harder than Problem C. Problem C was quite standard, and non-standard problems cause much more trouble for the competitors:)

It is so bad of me that I even did not check the tricky case that I generated for Div 2 B.

Thank you for really nice problems and amazing contest :)

Here is my solution to problem B div 1: http://codeforces.com/contest/251/submission/2710934 The veredict was: "Runtime error on test 1". But I tested the same test in my computer with the same code and it worked fine. Has anyone had this problem?

For Problem B ,Div 2 , an O(n^3) solution is also passing [code]

I noticed through the test case that it is actually never going O(n^3) when all elements of the array are not the same and when n is large . But I can not understand why this happens .Can anyone explain please

The complexity of this solution is O(N).

Suppose N > 3. Then it's enough to check only 3 different pairs of distinct integers. One of them will be the solution we are looking for. The reason is that these 3 pairs lead to 3 different arrays, but there are only 2 possible sorted arrays, so one of these 3 arrays will be unsorted.

+1 to that. Thanks.

.. . How to solve Problem E. ? ... QAQ

I'll post the complete editorial in a few days. Now I can give you a hint.

Suppose there exists a node of degree 3. Let's take any such node and call it a root. Then we can reduce our problem to the following one: given a non-root node

vwe need to calculate the number of ways to place the sub-tree of nodevon a rectangle 2xK for someKwith the restriction thatvis placed to the upper-left corner of this rectangle. Note that the value ofKcan be determined uniquely from the size of sub-tree. This problem can be solved with DP in linear time.The reduction to the described problem is also non-trivial, but at least it's easier than the whole problem.

。。。THX alot !...

editorial in English too, I hope? Google Translate doesn't work well sometimes.

How to solve problem D div 1 ?

BFS + DFS + Bitmap + convex hull (Y)

Can anyone show me the logic in choosing 0 (numbers that divide lcm(2..k)) to be the mediate value in problem C div 1?

In case you misunderstood my words (I assume that by seeing those down votes), this is merely a question :)

Anyone can tell me how to solve C div 1 :( Just a hint, plz :D

The essential trick was that if your current integer is divisible by all numbers from 2 to k, then the only thing you can do is to decrease this integer by one. Therefore, you can use dynamic programming to count how much time you need to reduce your integer by LCM. For instance, suppose a=80, b=3, k=3. Then LCM(2,3)=6. So you count separately the time you need to get from 80 to 78, then from 78 to 72, the from 72 to 66, ..., from 12 to 6, and finally from 6 to 3. It's easy to notice that all of those in the middle are equal.

P.S. That's a shame that I didn't see this trick during the contest, but I was thinking of some DP with LCM...

Then LCM(2,3)=62 what ????

I don't get your question. LCM(2..k)=LCM(2,3)=6.

Sorry, I already understand your answer :D Okay :D thanks for your hint :)

Fail (( My solution in D(div2) was correct ... I just forgot to clear my array ...

Editorial is published in Russian here @ http://codeforces.com/blog/entry/6054

I wonder if it is possible for someone to please kindly translate that into English for me?

http://translate.google.co.jp/translate?sl=auto&tl=en&js=n&prev=_t&hl=en&ie=UTF-8&eotf=1&u=http%3A%2F%2Fcodeforces.com%2Fblog%2Fentry%2F6054&act=url

Google Translate often does not do a sufficiently adequate job, eg. grammar and syntactical structure is not preserved.

Where can i see the editorial?

Are there any editorial?

only published in Russian, I'm afraid.

I'll publish the complete editorial on both languages soon. Currently I'm out of country and don't have enough time for editorial. Sorry for the delay.

I can't understand the Russian tutorial of Div.1 E. >_< I hope the English tutorial will be published soon. :)