tunyash's blog

Codeforces Round #144
By tunyash, 12 years ago, translation, In English

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:

  1. tourist
  2. rng_58
  3. Mimino
  4. Dmitry_Egorov, Egor

div2:

  1. debug22
  2. ryz
  3. dvdreddy
  4. vinodreddy
  5. rdivyanshu

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

  • Vote: I like it
  • +201
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Score distribution?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

it will be dynamic :|

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    You are missed :D

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Standard! :)

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    The same question about Div 1 Task C :)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it 
      5 1000
1 10000000000000000
1 9999999999999999
2 9999999999999999
3 9999999999999999
4 9999999999999999

      ответ:

      20
20 
21
21
21
      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

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

        → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ??

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Testing is so fast today

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Was difficult

→ Reply
»
12 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

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

      → Reply
»
12 years ago, # |
  Vote: I like it +98 Vote: I do not like it

Solved only AB and second place...

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    congrats!

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    wuhao21 solved AB and 161st place! :\

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    so interesting XD

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +97 Vote: I do not like it

    Does this describe your feelings? :-)

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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...

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      orz

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      ooops...

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

past contest is much easier than this for div. 2

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    "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!

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :(

→ Reply
»
12 years ago, # |
  Vote: I like it -44 Vote: I do not like it

is this contest unrated ?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think so

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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]

        → Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Looking forward to the editorial.

→ Reply
»
12 years ago, # |
  Vote: I like it -18 Vote: I do not like it

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

Problem Designers: Problem??

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

will the Editorial be published?

→ Reply