### tunyash's blog

By tunyash, 10 years ago, translation,

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

• +201

 » 10 years ago, # |   +18 Score distribution?
•  » » 10 years ago, # ^ |   +3 Will be announsed in a few minutes before the start of the contest.
 » 10 years ago, # |   +5 usually every time they say : Score distribution will be announced a few minutes before the start of the contest.it will be dynamic :|
•  » » 10 years ago, # ^ |   +24 You are missed :D
•  » » 10 years ago, # ^ |   +1 I wouldn't be so sure.. Well, the organizers have to intrigue us by anything, including the score distribution:)
•  » » 10 years ago, # ^ |   0 Standard! :)
 » 10 years ago, # |   0 Any ideas on what is so special about Div 1 Task B Pretest 3?
•  » » 10 years ago, # ^ |   +11 The same question about Div 1 Task C :)
•  » » » 10 years ago, # ^ |   +3 5 1000 1 10000000000000000 1 9999999999999999 2 9999999999999999 3 9999999999999999 4 9999999999999999 ответ: 20 20 21 21 21 
•  » » » » 10 years ago, # ^ |   +9 Спасибо. Все оказалось банально: int вместо long long...
 » 10 years ago, # | ← Rev. 2 →   0 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 ??
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 10 years ago, # ^ |   0 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)
•  » » 10 years ago, # ^ | ← Rev. 2 →   +1 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!= 0recurrence : 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
 » 10 years ago, # |   0 For div2-A, when n = 3, "2 3 1" seems like a perfect permutation, is there any mistake I made?
•  » » 10 years ago, # ^ |   0 P[P[1]]=P[2]=3 which is not equal to 1 as question says P[P[i]]=i
•  » » » 10 years ago, # ^ |   0 OK, I knew my mistake now, thank you all!
•  » » 10 years ago, # ^ |   0 It is wrong , P[3]=1, But P[1] != 3
•  » » » 10 years ago, # ^ | ← Rev. 2 →   +1 No, i = 1. So, P[P[1]] = P[2] = 3, but it must be 1, as phantom11 said.
•  » » 10 years ago, # ^ |   0 here p[p[3]] = 2 which is not equal to 3!!!
 » 10 years ago, # |   +1 System Test still pending :/ ... I am too anxious!
 » 10 years ago, # |   0 how long does it take generally for system testing to complete?
•  » » 10 years ago, # ^ |   0 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
 » 10 years ago, # |   0 Testing is so fast today
•  » » 10 years ago, # ^ |   +3 And now it's slow.
•  » » 10 years ago, # ^ |   0 It seemed to have slowed down at the end...
 » 10 years ago, # |   +8 Was difficult
 » 10 years ago, # |   +17 Very difficult div. 1 problems! Even for tourist, rng_58 and Egor!
•  » » 10 years ago, # ^ |   +34 Score distribution should be 500 — 1000 — 2500 — 2500 — 2500 =)
•  » » » 10 years ago, # ^ |   +27 500 was not usually 500... It was difficult and not trivial. So, I think that score distribution should be 1000 — 1000 — 2500 — 2500 — 3000;(
 » 10 years ago, # |   +98 Solved only AB and second place...
•  » » 10 years ago, # ^ |   +8 congrats!
•  » » 10 years ago, # ^ |   +27 wuhao21 solved AB and 161st place! :\
•  » » 10 years ago, # ^ |   0 so interesting XD
•  » » 10 years ago, # ^ |   +97 Does this describe your feelings? :-)
•  » » » 10 years ago, # ^ |   0 Muhaha ...
•  » » » 10 years ago, # ^ |   0 GJ man
•  » » 10 years ago, # ^ |   +42 It's the trend! There was a contest last week where Egor solved only 250 and came first :P
•  » » 10 years ago, # ^ |   +3 Problem setters are trying to make problems harder and harder, while the number of reds are becoming less and less :)
•  » » 10 years ago, # ^ |   +8 And ASPIRINKA hack :) Without this you should be 12st :(
•  » » 10 years ago, # ^ |   +10 That sounds crazy..... Next Div I round is written by me >_<...I promise it's VERY EASY LOL...
•  » » » 10 years ago, # ^ |   +3 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...
•  » » » 10 years ago, # ^ | ← Rev. 2 →   +16 Everyone in China knows difficulty of YuukaKazami's contests. I'm not saying that they are "very easy".
•  » » » 10 years ago, # ^ |   0 orz
•  » » » 10 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 10 years ago, # ^ |   +5 ooops...
 » 10 years ago, # |   0 past contest is much easier than this for div. 2
 » 10 years ago, # |   +5 Is there someone who can tell me the direction to solve Div1.C ?
•  » » 10 years ago, # ^ |   0 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.
 » 10 years ago, # |   +5 Hi, Div2 judge is stuck. please fix it. thanks
 » 10 years ago, # |   0 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.
•  » » 10 years ago, # ^ |   +5 Then there will be cycle (1-3-4) and in total there will be 4 cycle but not 3.
•  » » » 10 years ago, # ^ |   0 Thanks, I got it!!!! Have a nice day.
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 Try to draw this graph. To have cycles 123, 124, 234 you need edges 13, 34, 41. Which creates a new cycle 134.
•  » » » 10 years ago, # ^ |   0 Thanks!!!
•  » » 10 years ago, # ^ | ← Rev. 3 →   0 "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!
•  » » » 10 years ago, # ^ |   0 Thanks!!!
 » 10 years ago, # |   0 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 :(
 » 10 years ago, # |   -44 is this contest unrated ?
•  » » 10 years ago, # ^ |   0 I don't think so
•  » » 10 years ago, # ^ |   +1 There is no reason to be unrated !! hard problems isn't acceptable reason as i think ..
 » 10 years ago, # |   -16 2 problems with no one solved them during the contest for both divisions!!! seems strange !!
 » 10 years ago, # |   +2 In div2 problem B , Can it be solved using binary search (for finding the value of x) ?
•  » » 10 years ago, # ^ |   0 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
•  » » 10 years ago, # ^ | ← Rev. 3 →   +1 I don't think so.....x^2 + s(x)*xx = 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.
•  » » 10 years ago, # ^ |   0 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
•  » » 10 years ago, # ^ |   +3 yes, if you use some delta to check the rightness of answer. my solution here
•  » » » 10 years ago, # ^ |   0 the binary search in your solution isn't responsible for the result .. the loop after the binary search do all the work i think !
•  » » » » 10 years ago, # ^ |   +1 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]
 » 10 years ago, # |   +10 I'm happy ... +149 points!!!
•  » » 10 years ago, # ^ | ← Rev. 3 →   +6 Me too. I was progressing during four last contests, I gained 317 points in total and finally I'm in the first division :).
 » 10 years ago, # |   +11 Looking forward to the editorial.
 » 10 years ago, # |   -18 That moment when No one could solve C&E(Div. 1) :Problem Designers: Problem??
 » 10 years ago, # |   0 will the Editorial be published?
•  » » 10 years ago, # ^ |   0 it's published