rb9's blog

By rb9, 4 years ago, In English,

Plz help me in solving this problem?

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

link to problem?

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

    sorry for that, I have updated.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It's a greedy and brute force problem.

For any given message order, process the packets greedily. You should repeat the following process for each packet.

  • 1) Add the packet to the buffer.
  • 2) As long as the packet you should output next is stored in the buffer, output it and remove it from the buffer.
  • 3) Check the size of the buffer.

The minimum needed buffer size for the message order will be the maximum among all the buffer sizes at Step 3.

Since N ≤ 5, you can try out all possible orderings of the messages. Every packet will be added only once to the buffer and removed only once, so the process is linear for each ordering, hence the total complexity will be O(M * N!).