JamieVardy's blog

SRM 644, Medium
By JamieVardy, 11 years ago, In English

How to solve SRM 644 Div 1 Medium? The problem statement has not been linked to in the Problem Archive, so please log in to the arena to get the complete details about the problem. Roughly, the question goes :-

There are N competitors, numbered 1 through N. The tournament will have exactly K rounds. In each round, some of the competitors will drop out of the tournament and some will advance. The competitors who advance from round K are the winners of the tournament. A valid tournament must have at least one winner.

Each round of the tournament must look as follows.

At the beginning of the round, the competitors are divided into rooms.

Each room must contain two or more competitors. The competitors in each room must have consecutive numbers.

In each room the competitors compete against each other. The best competitor in each room advances and all others drop out of the tournament.

After the round, the advancers are assigned new numbers 1 through R, where R is the number of rooms.

A contestant with a smaller current number will always get a smaller new number.

For n = 6 and k = 2, ans is 4: That is, for the first round, we can — Choose first 4 and next 2, first 3 and next 3, 3 groups of 2 each, first 2 and next 4. The second round is defined uniquely then.

n <= 10**18, k <= 6

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

Comments Comments (9)
| Write comment?
»
11 years ago, hide # |
← Rev. 5  
Vote: I like it +15 Vote: I do not like it

Let's solve it by DP first. If every room has exactly 2 competitors, we will have this simple format:

Round 1: 1-2, 3-4, 5-6, 7-8, ...
Round 2: (1,2)-(3,4), (5,6)-(7,8), ...
Round 3: (1,2,3,4)-(5,6,7,8), ...

We modify the numbers such that each room can contain more than 2 competitors:

Round 1: 1-1-2, 3-4, 5-6, 5-6, 7-8, ...
Round 2: (1,1,2)-(3,4), (5,6)-(5,6)-(7,8), ...

By this way of assigning numbers (from 1 to 2^K) for competitors, we can sufficiently define a tournament format. Hence, the DP state is (i, j) where i is the index of the competitor and j is his assigned number. We have 2 kinds of transition: x to x + 1 and x to x — y + 1 where y is the value of the rightmost bit 1 in x (this case means we have more than 2 competitors for the current room).

The last part is to convert this DP approach into matrix multiplication which should be straightforward.

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

    Could you explain the modification step in a little more detail. I mean what exactly 1-1-2 mean and how does 5-6 appear twice? Are these not the indexes of the competitors in a particular round?

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

      1-1-2 means that the first room in round 1 contains 3 competitors. 5-6 appears twice means that the second room in round 2 contains 3 competitors. These numbers are not the indexes but represent the positions in the tournament format.

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

        Please don't get angry, but I still don't understand. :(

        I mean if 1-1-2 means that 1st room in 1st round has competitors 1-3, then how does 5-6 appear twice?

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

          It looks like this:

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

            Ohh, now I get it!! What a beautiful idea!! :D

            I would like to thank you from the bottom of my heart!! I can finally sleep peacefully now! :D

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

    What does x stand for?

    UPD: Got it! Thanks for the explanation, it would be easier if you used the same variables for the whole explanation.

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

Somebody please explain! I haven't slept properly since 4 days!! :(

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

I think that the way below is more straightforward. Lets build tournament tree competitor by competitor. The only thing allowed is that a tree can have nodes with one child on the rightmost path. In dp state we should store amount of competitors and a mask of K bits. This mask represents a state of the rightmost path. If k-th bit is on well then node of depth k has only one child. Look at the picture. Adding a new competitor means that a rightmost path will be changed and it is only allowed to branch deeper than last one-child node. Look at the picture. Here from state 010011000 it is possible to move to the states 010011000, 010011001, 010011011 and 010010111.

→ Reply