rb9's blog

A Network Problem
By rb9, 10 years ago, In English

Plz help me in solving this problem?

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

Comments Comments (4)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

link to problem?

→ Reply
»
10 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!).

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

    If possible can you plz explain me with code, it will be very helpful to me.

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

      Here is the code if you want to check some implementation details, but I suggest you code it and submit it yourself until you get AC.

      C++ Code

      → Reply