vepifanov's blog

Codeforces Beta Round #37
By vepifanov, 14 years ago, translation, In English
Good evening!

Today I am the author of problems. I'm studying in Nizhny Novgorod State University (2 year, Mechanics and Mathematics). I want to thank the staff codeforces for assistance in preparing the contest, and, personally, Artem Rakhov and Maria Belova (for translations of problems into English). Also special thanks to Alexei Shmelev (NNSU) for writing alternative solutions.

P.S. Unfortunately, this round could be in error to register a team. For teams participating in this round will be counted "out of competition", ie, rating of participants does not change. If you register a team by mistake, you can unregister and register in person.

UPD: After the contest start, it will be available PDF-versions of the statements:
UPD: The contest is over, congratulate Ivan Popelyshev, who won this round. He was the only one who has successfully solved all five problems.

Link to results.

UPD: Tutorials are available.

Regards,
Vladislav Yepifanov.
Прослушать
На латинице

Announcement of Codeforces Beta Round 37
  • Vote: I like it
  • +79
  • Vote: I do not like it

Comments Comments (32)
| Write comment?
14 years ago, # |
  Vote: I like it +10 Vote: I do not like it
Good luck to everyone.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What's the tricks in Problem B?? orz
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You should stop when the boss is died. Even before applying the item.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What was pretest 3 in Problem C?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Pretest #3:
    10
    4 4 4 4 4 4 4 4 4 4
    Possible answer:
    YES
    0000
    0001
    0010
    0011
    0100
    0101
    0110
    0111
    1000
    1001


    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      How about pretest 4 in same problem, please?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it 
        Test #4:
        20
        6 7 7 7 7 6 7 7 7 7 7 7 7 7 7 7 7 7 6 7

        Possible Answer:
        YES
        000000, 0000110, 0000111, 0001000, 0001001, 000001, 0001010
        0001011, 0001100, 0001101, 0001110, 0001111, 0010000, 0010001
        0010010, 0010011, 0010100, 0010101, 000010, 0010110



        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What's the pretest 3 in Problem B?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Test #3:
    10 100 5
    61 3
    55 2
    12 6
    39 5
    21 10
    39 7
    16 1
    10 1
    70 5
    100 7

    Possible answer:
    YES
    21 6
    0 10
    15 9
    17 1
    18 2
    19 6
    20 5
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
sorry but when will be the practice available ? find out my mistake  5 minute later, after the contest ended. (Problem c)
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
how to get all pretest during contest???
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
So, what is the idea about problem C ??
I have constructed a prefix tree like that in Huffman coding, and traversed it to get the solution, and if I can't add the new item then it is invalid

so what is wrong in this solution, as I failed in case 21 in the final test!!

Thanks in advance,
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can anyone tell how to do the problem C ?
Thanks
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Hi arpit_s

    1- Sort the data, but keeping information about original positions.
    2-Starting with an empty string s ( representing a binary number), do the following for each number:
       -If s is not the empty string, increment s by one. If this implies using an additional binary digit, then just     print NO.
       -Add as many zeros to s so that it has as many digits as the value for the current number.
    3-In this way you build a prefix-free dictionary, so now you just have to print it in the desired order.

    Regards.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I'd apreciate test 87 for problem B.....Thx in advance
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      А по-русски, кто нибудь может изложить план решения задачи С? Спасибо.
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Imagine a big binary tree which has empty string as root, and traversing left appends a "0" and to right appends a "1". So all possible 0-1 strings of same length are at same level. Each node in the tree is associated with its corresponding 0-1 string, which is just the path from root to it.

    Now, count the number of strings of each length we need from input. You start at "0" : len=1 and keep moving.

    1.) We are at level k and we need n strings of length k . If you are at node X, you can pick nodes X , X+1 , X+2 , . . . , X+n-1 ( each node has a 0-1 string associated with it, and +1 is just binary arithmetic ) .

    2.) After picking n strings at this level, you have to move to next level below. But, that should not have the previously chosen ones as your prefix. So, move right one more time and then go down left, such that none of its ancestors were chosen before.

    3.) If n=0, you can just go down left. Going down is same as X*2 ( left shift by 1 = one more 0 at end )

    In step 1, if X+n-1 exceeds length k, then its not possible "NO". Try on paper with the tree figure to make it clear. I have used this in contest. So here is my code for reference http://www.ideone.com/tkipH .
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
And test 8 of problem C as well...
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
As there is no a function to see test cases, maybe you could share the folder with these tests, so that we could have a look at them in the following way: codeforces.ru/contests/37/tests/C?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I think this is a good idea, just like the Topcoder SRM.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
May you provide me with test 76 in problem B?
Thanks.
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
I have found that the 3rd case of problem D has Xi = 0, but the problem statement guarantees that Xi > 0.
This makes some contestants' solution get wa.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    My apologies ... in the problem D in one point there was a typo. Initially, the restrictions on X and Y were as follows: 0 <= Xi, Yi <= 100.
    → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
There is a mistake in problem D

The problem said 1<=Xi<=100.But in pretest 3,the Xi becomes 0 which causes me get wrong answer  on it during the competition.

But it's too late now...

Someone should take the responsibility of the mistake!!!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Why late?
    I think your solution will be rejudged.
    Email private message to the contest's author.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I read accepted solutions for problem E, but I couldn't understand. How do you paint this board in 4 days?

13 13
WWWWWWWWWWWWW
WBBBBBWBBBBBW
WBWWWBWBWWWBW
WBWBWBWBWBWBW
WBWWWBWBWWWBW
WBBBBBWBBBBBW
WWWWWWWWWWWWW
WBBBBBWBBBBBW
WBWWWBWBWWWBW
WBWBWBWBWBWBW
WBWWWBWBWWWBW
WBBBBBWBBBBBW
WWWWWWWWWWWWW
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    0000000000000
    0111110111110
    0122210122210
    0123210123210
    0122210122210
    0111110111110
    0000000000000
    0111110111110
    0122210122210
    0123210123210
    0122210122210
    0111110111110
    0000000000000


    First time we paint all the board into black.
    Second turn - all cells except cells with distance 3 into white.
    Third - all except 2 and 3 into black.
    And last - cells, except cells with 1, 2, 3 (cells with distance 0) into white.
    → Reply