MikeMirzayanov's blog

Codeforces Testing Round #3
By MikeMirzayanov, 13 years ago, translation, In English

Informal unrated contest Codeforces Testing Round #3 is scheduled on December, 2 (Friday), 15:00 (UTC). We will test the latest innovations on Codeforces that they do not affect the contests. If not, we will fix it quickly :) So, this round will take place "as is", no warranty about it.

Problems for the round may be famous to someone, but I'll try to make them such not for any of you. It will be 3-4 problems, as quite simple and something more tricky. The contest duratiuon is 1 hour.

I say thanks in advance to all those who will come and test the system. Thank you!

MikeMirzayanov
Announcement of Codeforces Testing Round 3
  • Vote: I like it
  • +81
  • Vote: I do not like it

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

Thank you for your hard work to prepare such a contest ,I will take it .

→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
I hope I can solve all problems in an hour:)
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Thx for testing round... I hope it will be beneficial who will join to contest.
→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Thanks a lot for your hard work .. 
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I will be here, thanks for your contest.
→ Reply
13 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

It was really funny contest with "hard" pretests :) 

→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
please, can anyone describe the idea behind problem B?
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    you should always increase minimum from (a,b) by maximum (a,b); if (a>b) b+=a;else a+=b;

    and if (a >=n || b>=n) then print number of steps.that was my solution.

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Notice, that you won't have (m, m + k) in the optimal way, where k is a positive integer, because (m, k) would have less moves. So you will have (m; n), n <= m. Backtrack all n.
    When you need to calculate moves for position (m; n), you can get only (n; m - n) from it. For fast calculations use an algorithm similar to gcd :)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks for the explanation. Why BFS doesn't work here?
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        well, I guess that it takes too much memory. If you take (n; m) as a state, I think that you have O(n^2) memory and time complexities. n can be a million.
        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I am confused about problem C. For sample 3, initially the fifth person has all the 5 cards with all 5 colors while other four people have nothing? But the statement said each people should have only one  color in the beginning, so it seems like a conflict for me. 

I must miss/misunderstand some important info, would anyone give me a hint? Thanks.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    There can be cards of the same colour as each other.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Sorry, I don't get it.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        In this example, the fifth person has 5 cards, and they are all her colour (thus she only has one colour, but 5 cards of that colour). There are no cards coloured for any of the other people.
        → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You can solve the problem C by Havel theorem with O(nlogn) time complexities.
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
We cannot see the details of hacks now? This useful feature is available before.
→ Reply