bluemmb's blog

Forgetful Waiter ( LA 6354 )
By bluemmb, 8 years ago, In English

Hi.

There are n<=100 customers round a table. i'th of them wants food of type a[i] but waiter has brought food of type b[i] for him! ( note that [b] is a permutation of [a] ).

Now customers want to move foods such that each of them get his favorite food. At each second each of them can perform one of these :

1 : pick one of the foods in front of him and give it to the person on his LEFT side

2 : pick one of the foods in front of him and give it to the person on his RIGHT side

3 : (1 + 2) simultaneously

There is one additional limitation that at each second no one can have more than 5 foods in front of him. We want to know the minimum time needed to do the job. ( each customer get his favorite food )

Sample : ( Squares are customers with their favorite food and Circles are foods on table. )

We need 2 seconds.

Can you help me to solve this problem ? It's kind of you :)

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

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Special thanks to Kerpoo and Reza_H. They suggested the solution for this problem in ACM group ( Iranians Telegram Group ).

Solution : We can use BinarySearch on solution + BipariteMatching.

Actually we create a whole graph for BipartiteMatching such that left side nodes are Foods and right side nodes are Customers. Then we put an edge from foods to customers that have the same type with cost of their distance.

Now we do a binary search on solution , At each step we are just allowed to use of edges that their cost is <= K. Lowest K that satisfies the matching is the solution.

So what about Limitation ( not more than 5 foods in front of customers ) ?

It is provable that with a good strategy we won't have more than 3 foods in front of each customer at the same time.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Could you clarify how a "good strategy" works? I'm having trouble visualizing that.

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

      Sorry for my late reply.

      Move all the foods that have to be moved since the beginning of the time ( I mean if answer is 5 seconds and we have a food that must be moved 1 time , move it at second 1 and don't keep it for next seconds ).

      Now for each customer, suppose that there are some foods that have to be passed from one side of him to another side. All of them will pass from front of this customer , but at each moment just 2 of them will be in front of him ( those have the same distance from him )

      → Reply