Hi all!

Codeforces round #144 is going to be today.

Round is prepared by: KAN, fdoer, Skird, tunyash. Special thanks to Gerald for coordinating round preparing, many awesome ideas and making statements easy-understandable. Also I thank MikeMirzayanov for enjoyable problem-preparing system, Delinur for statements translation.

I hope, that all will be well and you will enjoy solving problems.

Good luck!

**UPD:** Score distribution will be announced a few minutes before the start of the contest.

**UPD2:** score distribution is 500-1000-1500-2000-2500 in both divisions

**UPD3:**

Congrats to winners.

div1:

div2:

**UPD:** editoral for all problems, except div1.D is ready

Score distribution?

Will be announsed in a few minutes before the start of the contest.

usually every time they say : Score distribution will be announced a few minutes before the start of the contest.

it will be dynamic :|

You are missed :D

I wouldn't be so sure.. Well, the organizers have to intrigue us by anything, including the score distribution:)

Standard! :)

Any ideas on what is so special about Div 1 Task B Pretest 3?

The same question about Div 1 Task C :)

ответ:

Спасибо. Все оказалось банально: int вместо long long...

Ideas for Div2 D ?? I was finding out a pattern that if I fill some N sized array by some arrangment , The same thing I could do with next N + N arrangement . This was going for matrix exponentiation. Altough I could not completely formalize it.

Was I going in the right direction ?? Or there is some other way ??

Lets define F(C) as the number of colored cells in column number C. IMHO, the key observation is that F(X) = F(X + N) = F(X + 2N) and so on.. DP solution can be found, but I failed on pretest 3 as mentioned above.

You mean to say that we could find F(X) by using DP and rest we have to do is exponentiation of F(X) by ceil(N/M)

We can use dynamic programming here .

state would be [cur_pos(0...n-1)][rema(0....n^2)]

base case : dp[n][x] = 1 if x= 0 dp[n][x] = 0 if x!= 0

recurrence : dp[i][j]= sum over x=0 to min(j,n) pow(nCr(n,x) ,ceil( m/n ) ) * dp[i+1][j-x]

P.S : need to make sure that we don't use pow function every time and need to memorize it as base can have at most 100 distinct values

For div2-A, when n = 3, "2 3 1" seems like a perfect permutation, is there any mistake I made?

P[P[1]]=P[2]=3 which is not equal to 1 as question says P[P[i]]=i

OK, I knew my mistake now, thank you all!

It is wrong , P[3]=1, But P[1] != 3

No, i = 1. So, P[P[1]] = P[2] = 3, but it must be 1, as phantom11 said.

here p[p[3]] = 2 which is not equal to 3!!!

System Test still pending :/ ... I am too anxious!

how long does it take generally for system testing to complete?

I have seen very few system testing before. In my experience they all took around one hour. But today's system test seems really fast. I guess it will be done in half an hour. It's a new experience :D

Testing is so fast today

And now it's slow.

It seemed to have slowed down at the end...

Was difficult

Very difficult div. 1 problems! Even for tourist, rng_58 and Egor!

Score distribution should be 500 — 1000 — 2500 — 2500 — 2500 =)

500 was not usually 500... It was difficult and not trivial. So, I think that score distribution should be 1000 — 1000 — 2500 — 2500 — 3000;(

Solved only AB and second place...

congrats!

wuhao21 solved AB and 161st place! :\

so interesting XD

Does this describe your feelings? :-)

Muhaha ...

GJ man

It's the trend! There was a contest last week where Egor solved only 250 and came first :P

Problem setters are trying to make problems harder and harder, while the number of reds are becoming less and less :)

And ASPIRINKA hack :) Without this you should be 12st :(

That sounds crazy..... Next Div I round is written by me >_<...I promise it's VERY EASY LOL...

So bad for me, my train from Saratov (we participate in ACM ICPC competition there) arrives home just one hour before contest and I won't be able to come home in time...

Everyone in China knows difficulty of YuukaKazami's contests. I'm not saying that they are "very easy".

orz

I thought that problems is not so hard. About ten people solved C, but there were many pitfalls in it. One guy solved E, but he had some bugs too.

ooops...

past contest is much easier than this for div. 2

Is there someone who can tell me the direction to solve Div1.C ?

Vertex |D(n-1)| + 1 is cutpoint. Because of this, if min(a,b) <= |D(n-1)| + 1 and max(a,b) >= |D(n-1)| + 1, path will contain |D(n-1)| + 1. We should solve same problem for pair (a, |D(n-1)|) (a, 1) (b, |D(n-1)|+1) and graphs with orders k-1, k-1 and k-2 respectively.

Hi, Div2 judge is stuck. please fix it. thanks

Hi, I have a doubt in C div 2. For k = 3 why I can not draw a graph with 4 nodes and these relationships, (1 — 2 — 3), (1 — 2 — 4) and (2 — 3 — 4). Maybe I did not understand very well when statement says "A cycle of length 3 is an unordered group of three distinct graph vertices a, b and c, such that each pair of them is connected by a graph edge". Thanks in advance.

Then there will be cycle (1-3-4) and in total there will be 4 cycle but not 3.

Thanks, I got it!!!! Have a nice day.

Try to draw this graph. To have cycles 123, 124, 234 you need edges 13, 34, 41. Which creates a new cycle 134.

Thanks!!!

"A cycle of length 3 is an unordered group of three distinct graph vertices a, b and c, such that each pair of them is connected by a graph edge". 1 is connected to 3 (from 123), 3 is connected to 4 (from 234) and 1 is connected to 4 (from 124), so your graph actually have 4 cycles of length 3 (123,124,234,134). CMIIW!

Edit: sorry for reanswering a question, when I write this hza's and BOBAS' comments aren't there yet!

Thanks!!!

Did anyone else had a problem when challenging? I challenged someone and the verdict was something like "Judgement protocol not found or unavailable." This lead me to try to challenge the same code again, but then the previous challenge turned out to be unsuccessful... There goes 50 points :(

is this contest unrated ?

I don't think so

There is no reason to be unrated !! hard problems isn't acceptable reason as i think ..

2 problems with no one solved them during the contest for both divisions!!! seems strange !!

In div2 problem B , Can it be solved using binary search (for finding the value of x) ?

I think no , because binary search property isn't applied here as there is no value of x the equation is true above and false below

I don't think so.....

x^2 + s(x)*x

x = 8, 8^2 + 8*8 = 128 ; x = 9, 9^2 + 9*9 = 162 ; x = 10, 10^2 + 1*10 = 110 <- It drops here ; x = 11, 11^2 + 2*11 = 143 ;

If the increase in value was uniform, then we could have used binary search. But now we can't be sure on which half the correct value lies.

I believe you can't, since it's perfectly possible to have x * x + x * s(x) > y * y + y * s(y), even though x < y. For example x = 9, y = 10 : 9 * 9 + 9 * 9 > 10 * 10 + 10 * 1

yes, if you use some delta to check the rightness of answer. my solution here

the binary search in your solution isn't responsible for the result .. the loop after the binary search do all the work i think !

binary search lowers the answer interval to [x-delta; x+delta], it is simpler than some solutions where is the answer within [sqrt(n)-delta; sqrt(n)+delta]

I'm happy ... +149 points!!!

Me too. I was progressing during four last contests, I gained 317 points in total and finally I'm in the first division :).

Looking forward to the editorial.

That moment when No one could solve C&E(Div. 1) :

Problem Designers: Problem??

will the Editorial be published?

it's published