CLETAB - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vinayak Garg
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

DIFFICULTY:

Simple

PREREQUISITES:

Greedy Algorithms, Simulation

PROBLEM:

You have N(<201) tables for costumers. M(<401) constumers will place orders. Each customer will place an order and if he is not already seated, a table will be cleaned and will be given to him. If no tables are empty some customer(of your choice) will be asked to leave and the new costumer will be placed on the empty table after cleaning. You are given the sequence in which customers place their orders. Find the minimum number of tables that must be cleaned.

EXPLANATION:

Let’s say a customer comes with an order:

If he is already seated, do nothing. We don’t have to clean a table.

If not seated, two cases arrive:

  1. Empty table is available: We clean the table and give a table to him. Any empty table will work.
  2. No empty table is available: We have to remove someone from the table. We would prefer to remove someone who doesn’t places an order in future. If such customers are seated, we can remove anyone from them. If we remove someone who will order in future, we’ll have to clean one extra table which we won’t have to if we pick greedily. If no such customer is present who’ll NOT order in future, we’ll pick a customer who will order in future in farthest of time. This will ensure that minimum number of swaps are to be made.

Once the greedy approach is clear, implementation is very easy. It can be solved in O(N*M). Using heaps/priority queue we can also solve in O(N log M).

Links: The theoretically optimal page replacement algorithm.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

8 Likes

In 2nd case, when no tables are available, what if we ask that particular customer to leave, who will be giving the order least number of times after that? Why choose someone who will give the order farthest in time? Can you prove why it is correct?

2 Likes

In 2nd case, when no tables are available, what if we ask that particular customer to leave, who will be giving the order least number of times after that? Why choose someone who will give the order farthest in time? Can you prove why it is correct?

1 Like

@ ketanhwr Thumbs up! I’ve done the same way.
@ Editorialist I don’t know if I can ask this here. Can you give me a test case which differentiates your approach with the one mentioned by ketanhwr ?

The solution wont work because there may be a case where a person will order once more after 1 second, and another will order 10 more times all after 3,4,5… seconds. Your algo will kick out the first guy, then reinvite, then kick him out again. Thats 3 tasks instead of the optimal 1 task. I have posted the odd test case. :slight_smile:

2 Likes

Please look at my answer

@ketanhwr and @sunny210. Hope this helps.

Take the case:
1

2 10

1 2 3 1 3 1 3 1 3 2 2 2 2 2

Your approach:

–

1-

12

32

12

32

12

32

12

32

rest will be same. Thats 9 cleaning jobs.

Optimal approach:

–

1-

12

13

nothing till

23

Thats just 4 jobs. I guess my hands are more tired typing this than the guy cleaning tables. :slight_smile:

10 Likes

Can someone help me.
I got 19 WA.:’(
Algo:
Same as Editorial.
:’(

http://www.codechef.com/viewsolution/4542472

1

3 20

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

output

9

2 Likes

0 not allowed.!

Thanks! It was helpful.

Shouldn’t it be “If no such customer is present who’ll NOT order in future, we’ll pick a customer who will order in future in farthest of time.”? Or did I not understand that statement correctly?

It is equivalent to the Optimal Caching problem when the future is known. Check https://cseweb.ucsd.edu/classes/wi12/cse202-a/lecture4-final.pdf for the theory.

1 Like

Even I implemented the same Optmal age Replacemennt Algo, and for commented test cases too its working correctly. Can somebody tell me where I am wrong.

Here is my solution:
http://www.codechef.com/viewsolution/4480487

@nisargshah95 it’s fixed now. Thanks

can someone tell me the mistake in my code. Algo that i used is same as the one given in editorial n i got WA.

http://www.codechef.com/viewsolution/4535880

http://www.codechef.com/viewsolution/4515928
Problem with this?

It would be of great help if any one could provide some tricky test cases or find the error:
http://www.codechef.com/viewsolution/4497989

I used set to maintain the customers currently occupying the table
And array of queues to store the future positions of customers

Simply implement the
optimal page replacement algorithm

3 Likes

replace 0 with any other number which is not already in list for example 5 .

2 Likes