Sereja's blog

Codeforces Round #156
By Sereja, 12 years ago, translation, In English

Hello everyone!

Codeforces Round #156 will take place on Sunday, December 16th at 19:30 MSK. This is my second Codeforces round and I hope not the last.

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

Problems’ point values are standart: 500-1000-1500-2000-2500.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

Contest is over, I hope it was interesting for you :)

Congratulations to div1 winners:
1). YuukaKazami
2). al13n
3). rng_58
4). Bigsophie
5). KADR

and div2 winners:
1). ShadowSong
2). ynbpdy072
3). jiaobu

You can view editorial here.

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

Comments Comments (111)
| Write comment?
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

More like "lack of lag and luck" — when you say it with the right accent it sounds really hilarious, but still makes sense :D

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

Does this contest require any file input or output ?

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

    I don't think so.

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

    Usually, we don't need to get input from files. The two last contest were exceptionnal, because it was for a local stage in Saratov. If it isn't indicated, the input and output are standard.

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

      Moreover we can write code that will check if such file exist and then read and write here, otherwise use standard IO.

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

        Usually we don't have permissions to read files :P

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

      Thanks ! I will have that in mind from now on ! :)

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

Will the scoring be dynamic or standart?

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

    No dynamic scoring, I promise.

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

      And will it be 500-1000-1500-2000-2500, as usual?

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

        I don't know, temporary.

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

        If problems will not be sorted by difficulty, I don't think that scoring will be 500-1000-1500-2000-2500 as usual.

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

        I strongly recommend you to read ALL the problems.

        You see :D i don't think the score will be the same as usual :D

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

          As a matter of fact we have contest in both divisions and as each contester can see the others' problem so it is hard to separate problems . :D

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

It's not the first time lots of solutions are in queue =(

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

I need a clarification, the integer 'q' in div2-C is always an positive integer ?

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

In Div2C does q need to be positive, because if no then in the second test case:10 20 10 30 the example can be 4 or I am missing something?

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

    yes, q can be -

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

    On problems page (dashboard) there is [ASK QUESTION] button !!! ( So you should not ask questions in blogs during contest) =)

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

      I didn't know this man. Take it easy, relax.

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

      I didn't know that. I am sorry if I disturbed someone.

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

hi can help me about problem c? i dont know what is say

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

    given a sequence b, find longest sequence q in the form of

    a,b,a,b,a..... where a and b are integers.

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

Well the server is tottaly trolling me. I submit on problem D and it cost more than a minute to running on test 8. I though it will TLE. Then I decided to resubmit it, When I resubmit it my last submission got passed. Now I get -50 for my submission and penalty minute.

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

    Sorry, but it was your choice. Lag is to be expected, you should've waited for the result.

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

How solve problem C ???

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

    Maintain a list of indices for each different value. I missed just a couple of characters in my code, and I got WA :(

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

< I spend 10 minutes to debug a mistake which I type "Furlo" to "Furio" .... Maybe I played too much WOW ...

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

What's the trick in D? Why counting a number of sequences in which number (n-k) appears exacly (n-k) times and there isn't any other number q that appears exacly q times is wrong?

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

    I guess number of i such that a[i] appears exactly a[i] times should be equal to n — k.

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

    There may be some numbers s_i such that each number s_i occurs exactly s_i times and the sum of all s_i is n-k.

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

      Let's assume n = 4 and k = 1. Does the sequence 1, 2, 2, 4 is good? There are 2 possibilities: either first person always tell the truth or second and third does. We can't know anything for sure.

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

        For the fourth person we are sure that he is lying. Each of the first three people may be telling the truth. So the sequence is correct.

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

I have some trouble understanding Div1D. If 0<k<n, then nobody can answer 0. How can Serge with such answers find out that not everybody is a liar (if everybody is a liar, then everybody can answer anything)?

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

    If X people tell the truth then exactly X people must answer X.

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

    I had the same trouble for a while.

    For example, suppose that there are two people A and B, and they answered 1 and 2, respectively. Then there are two possibilities: {A honest B liar} or {A liar B liar}. You can conclude that B is a liar, but you have no information about A. You concluded that k = 1 people (B) is a definitely liar.

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

      do you have an algorithm that does not require to make a table beforehand?

      I can only figure out a solution with time complexity n^4 :(

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

        Author solution is n^4 dynamic programming. And precalc (n is power of 2).

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

          umm...so why not just make n<=50?I don't know the intention of force competitors to make a table :(

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

        My solution is O(n^4) too.

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

      OK, thank you! I thought Serge would be able to say that there are exactly k people lying (no matter which), not that there are exactly k people for which he knows that they are lying.

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

funny!! couldn't understand div2-C in contest time. :(. i could solve it... :(

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

    please explain your algorithm

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

      you can see solution of others within a very short time :)

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

        where can see solution?

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

          enter in the contest> go to status link> click a row of the '#' column where prob C has verdict as AC.

          (you can filter status page using 'status filter' portion in the right side)

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

Did anybody use binary search in div2-D, or it's bad idea to do it?

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

    I think many people would have done it using binary search on the number of steps.

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

      I could count numbers until this wave will reach any wall, but what to do then?

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

        You can find out the number of cells filled in T steps in O(1). It is easier if you consider the simpler problem where we start filling an A*B (A<B) box starting with the bottom left cell filled.

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

        Then you should count cells switched on which are outside of board.

        These cells formulate a triangle. There are at most four triangles (one for each side). And some of them can overlap.

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

          Thx for clear explanation, I'll try)

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

        count how much of them out of the field using arithmetic progression

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

          border1, border2, cap1, cap2 is distance to border and top from start. if cell on edge, then here coord are abs(bx — x) + abs(by — y) = step, step is current number of step, x, y from input. After we have line of fill edge cell on each side, we can calculate square with (a-1) * b /2, a-how mach cell if fill on this edge, b — is height step out borber, (step — distance to this side)

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

    I think so.

    Interval is 0..2n-2

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

    This problem was similar with last COCI exam !! Isn't it ??

    UPD: I mean solution of them were similar.

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

I must learn to read problems really. I have misunderstood DIV2-E :@ :@ Complicated it for nothing :@

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

So slow

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

    So obvious :P

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

    There are two reasons to try to solve a problem faster .

    1. First one is to get more points
    2. Second is to see if your solution is correct and sleep without any worries (except rating change) ! =)

    UPD: Now I can sleep and relax. No problems with my solutions. I prefer sleeping than waiting for rating change and be late for school tomorrow.

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

      Thanks for the advice, but actually I meant slow system testing phase

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

It seems the systest will take a big amount of time... a previous round written by me also have this problem... It is because put so much big test in problem A or B, that kind of easy problem has many submissions, so if one submit need 50 seconds, then the whole judging will last for hours :(... so I hope the later writers can take care of it :)....

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

and one thing....who is Bigsophie ?

maybe there will come someone like Petr2 or ACRush2 ? (just joking :) )

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

    may be WJMZBMR2 !!!!

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

    I found who he is by his code....

    a hint: he use lemon() a lot :)

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

      And what does it mean?

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

      By the way, his solution of todays div1-B (2777959) includes many useless procedures and functions, it seems that he's trying to make his code difficult to read, and it's a bit unfair because, I think, CF rules include some prohibitions like that.

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

        this is not the case.... that code is an solution for a another problem, which is the same as today's B but has many point at the start not one. this is very difficult indeed and require tons of code.. he just use that big weapon to shoot at this easy problem.. this is ok bcz CF allow you to use previous code written by you.

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

          But his solve2(), slove3() .... etc are equal to each other! :D

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

            read carefully...they're not equal and every one work for some case... but indeed it can be replaced by 4 rotation ...

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

          oh, my mistake, they are different))

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

      I know who you talking about. :)

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

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

I got TLE when I sent Prob B div 2. I think this solution does not spend more than 2 second running. I lost 50 point in that.

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

The rate of comments in this blog is more than the rate of system testing !!!

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

Problem A turns out to be harder than expected

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

this systest need one codeforces contest time

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

I passed Div2 C with O(N^3). I even had prepared a test case where I fail because of time limit. I was lucky this test was not in the systest. I just fixed the two starting numbers — O(N^2) and then greedily find the longest sequence — O(N). So totally O(N^3).

I have added this: if (many[A] + many[B] <= ans) continue; and fooled the systest. But the test 1 2 2 3 3 4 4 5 5 6 6 7 7 ..... breaks my solution with time limit exceeded.

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

    It's your luck no one hacked you. But in this case of course it's fair

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

    And my solution of O(N^2+ Hashtable search) gets TLE :(

    EDIT -> Used Hashtables to map a particular element to one of the index in between [0,4000) and then called every reference with arrays and the code gets Accepted

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

    Your solution can be easily changed to O(n^2). When you are finding the longest sequence, you can only go through the elements that are equal to the one of those two fixed (not through the whole sequence like in your submission).

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

For Div 2 E , please tell whether my grundy number calculation is correct or not ??

In each step we should try to make y as large as possible. So we should try to make y to x^(1/2) in each step. We can keep doing this until we can make a move ie. 0<=y<x. finally grundy number will be the number of steps taken in this part.

please verify findXor function to calculate xor . link : http://www.codeforces.com/contest/255/submission/2782916

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

    No, we shouldn't try to make y as large is possible. Actually, if n=1 and x=25, it's better to take y=3 and win (Rublo can't change the number, because 1<3^(1/2)<2 and 1<3^(1/2)<2, there is no integer in this interval). Sprague-Grundy number of some state of the game is the minimum non-negative integer, that is not equal to Sprague-Grundy numbers of any state, which we can achieve from current state.

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

      Thank you for your reply, Now I have understood it. Actually I thought of taking sqrt(x) because I wanted to make state less. But I forgot the nice thing that I only needed to have grundy numbers upto sqrt(77777..... 12 times ) which was not so large.

      EDIT : solved the problem.

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

rating?

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

    probably having coffee around a corner of RAM with "paging system"....

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

    Ratings have been updated:)

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

Editorial in Russian available here @ http://mirror.codeforces.com/blog/entry/6161

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

    google translate makes a good translation for this editorial .... thanks for being google-translate friendly.....

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

    It would be really helpful if anyone could provide a dynamic programming solution to Div-2 C problem.( not the code, only the idea)

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

      Well there are only N different numbers so we can sort them and lower them to the range [0, N — 1] instead of [1, 10 ^ 6]. Now we can build a matrix DP[MaxN][MaxN] where DP[i][Numbers[j]] would be equal to the maximum length of some progression that has the last two elements Numbers[j] and Numbers[i]. Since we know the last two elements we know the last three since it equals (a, b, a, b, a, b, ... ) are Numbers[i], Numbers[j], Numbers[i] so we can use something of a very simple knapsack solution. Try to update DP[i][Numbers[j]] with DP[j][Numbers[i]] + 1 and in the end write maximum of the matrix + 1.

      Code for this idea: 2775826

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

      My dp solution: take all pairs (these pairs will end of our subsequence, subsequence must be like this: x y x y x y x) and try to find answers for them. Say, pairs are : a[i] and a[j], which i > j. So d[i][j] = d[j][k] + 1, which (k < j) and (a[k] = a[i]), of course we must know answer of d[j][k]. I tried to explain to you my solution, sorry for my bad english.

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

thank you for the contest , I think that these problems have fresh ideas

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

I cant believe it. My submission number 2812603 passes the test case 11 (458754) for which it gives the answer 667496909 on my computer.

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

is there any english editorial of round 156???? I'm thirsty of it

→ Reply