You are not logged in. Please login at www.codechef.com to post your questions!

×

CLETAB - Editorial

7
1

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

This question is marked "community wiki".

asked 11 Aug '14, 15:13

darkshadows's gravatar image

5★darkshadows ♦
3.0k91161186
accept rate: 12%

edited 11 Aug '14, 18:58

shivam217's gravatar image

4★shivam217
8123515

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?

(11 Aug '14, 18:01) nisargshah953★

@nisargshah95 it's fixed now. Thanks

(11 Aug '14, 19:00) shivam2174★

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

(11 Aug '14, 19:13) puneeth_m3★

12

@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. :-)

link

answered 11 Aug '14, 16:21

gkcs's gravatar image

5★gkcs
2.4k11025
accept rate: 9%

edited 11 Aug '14, 16:21

Thanks! It was helpful.

(11 Aug '14, 17:44) sunny2102★

For all "Whats wrong with my approach" questions, here is a python script to generate input file

from sys import stdout
from random import randint 
T = randint(1,100)
stdout.write(str(T)+"\n")
while T:
    N = randint(1,200)
    M = randint(1,400)
    stdout.write(str(N)+" "+str(M)+"\n")
    while M:
        stdout.write(str(randint(1,400))+" ")
        M = M-1
    stdout.write("\n")
    T = T-1
    
Commands:
python generator.py > input
cat input| ./a.out > output
cat input| ./c.out > outputcorrect
diff output outputcorrect

Take any successfull solution compile it. Compile your solution and compare output of both. And seriously, stop expecting people to debug your code for you. Very few people have the time and commitment for that. Learn to debug yourself.

You can tweak the parameters to generate smaller testcases that you can debug with pen and paper.

link

answered 12 Aug '14, 14:09

nitinj's gravatar image

5★nitinj
2.2k111926
accept rate: 5%

edited 13 Aug '14, 14:03

A very important thing for any programmer is debugging his own code. And that includes generating weird test cases. Nice answer :-)

(12 Aug '14, 23:57) gkcs5★

Simply implement the optimal page replacement algorithm

link

answered 11 Aug '14, 21:17

neo.nish's gravatar image

3★neo.nish
46114
accept rate: 0%

1

for all those asking for boundary test case: 1

3 31

7 11 17 10 7 10 2 9 2 18 8 10 20 10 3 20 17 17 17 1 15 10 8 3 3 18 13 2 10 10 11 output 18

(14 Aug '14, 23:50) neo.nish3★

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

link

answered 11 Aug '14, 16:30

s1h33p's gravatar image

3★s1h33p
329239
accept rate: 15%

0 not allowed.!

(11 Aug '14, 17:06) j1k7_75★
2

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

(11 Aug '14, 21:40) shivam2174★

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?

link

answered 11 Aug '14, 15:32

ketanhwr's gravatar image

6★ketanhwr
1.9k21644
accept rate: 15%

1

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.

(11 Aug '14, 18:08) n2n_5★

@gkcs Thanks! I now understood it!

link

answered 12 Aug '14, 15:57

ketanhwr's gravatar image

6★ketanhwr
1.9k21644
accept rate: 15%

@ 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 ?

link

answered 11 Aug '14, 16:01

sunny210's gravatar image

2★sunny210
1011512
accept rate: 0%

Please look at my answer

(11 Aug '14, 16:15) gkcs5★

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

link

answered 11 Aug '14, 18:56

arpit0410's gravatar image

2★arpit0410
1
accept rate: 0%

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

link

answered 11 Aug '14, 20:24

AnoopNarang's gravatar image

3★AnoopNarang
183
accept rate: 0%

1

3 31

7 11 17 10 7 10 2 9 2 18 8 10 20 10 3 20 17 17 17 1 15 10 8 3 3 18 13 2 10 10 11 output 18 your 21

(14 Aug '14, 23:41) neo.nish3★

can anyone please tell me why iam getting wrong answer ALGO is same as editorial

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

link

answered 11 Aug '14, 22:50

hitesh_saini's gravatar image

3★hitesh_saini
11
accept rate: 0%

Hi

Can someone pls provide me the corner case for which my code is giving wrong ans

public static void main(String[] args) throws IOException {
    st = new StringTokenizer(br.readLine());

    int numberOfTestCase = Integer.parseInt(st.nextToken());

    for (int i = 0; i < numberOfTestCase; i++) {
        st = new StringTokenizer(br.readLine());
        int noOfTables = Integer.parseInt(st.nextToken());
        int noOfOrders = Integer.parseInt(st.nextToken());
        List<Integer> orders = new ArrayList<Integer>();
        st = new StringTokenizer(br.readLine());
        int count = 0;
        List<Integer> list = new ArrayList<Integer>();
        while (st.hasMoreElements()) {
            int orderNumber = Integer.parseInt(st.nextToken());
            list.add(orderNumber);
        }
        for (int j = 0; j < noOfOrders; j++) {
            if (orders.size() == noOfTables) {
                if (!orders.contains(list.get(j))) {
                    int temp = 0;
                    int found = -1;
                    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
                    for (int o : orders) {
                        boolean present = false;
                        int count1 = 0;
                        for (int r = j+1 ; r < list.size(); r++) {
                            if (list.get(r) == o) {
                                present = true;
                                count1++;
                                map.put(count1, o);
                            }

                        }
                        if (!present) {
                            found = 0;
                            break;
                        }
                        temp++;

                    }
                    if (found != 0) {
                        Map<Integer, Integer> m = sortByKeys(map);
                        Object myKey = m.keySet().toArray()[0];
                        temp = orders.indexOf(m.get(myKey));

                    }

                    orders.set(temp, list.get(j));
                    count++;
                }
            } else {
                if (!orders.contains(list.get(j))) {
                    orders.add(list.get(j));
                    count++;
                }
            }
        }
        log.write("" + count);
        log.newLine();
        log.flush();

    }
}

@SuppressWarnings({ "rawtypes", "unchecked" })
public static <K extends Comparable, V extends Comparable> Map<K, V> sortByKeys(
        Map<K, V> map) {
    List<K> keys = new LinkedList<K>(map.keySet());
    Collections.sort(keys);

    // LinkedHashMap will keep the keys in the order they are inserted
    // which is currently sorted on natural ordering
    Map<K, V> sortedMap = new LinkedHashMap<K, V>();
    for (K key : keys) {
        sortedMap.put(key, map.get(key));
    }

    return sortedMap;
}
link

answered 12 Aug '14, 13:07

ravjsing's gravatar image

2★ravjsing
11
accept rate: 0%

edited 12 Aug '14, 13:08

Ok, I deduced the "farthest of time" thing after I was doing something with frequency, but still I kept getting WA even when I used Deque for same implementation. Can I please get the test file or case for which my code fails, I am pretty sure it is correct. WA, CLETAB

link

answered 12 Aug '14, 14:16

abcdexter24's gravatar image

2★abcdexter24
309211
accept rate: 3%

For all those who want a tricky test case, take this one

1

3 20

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

ans is 9 :)

link

answered 12 Aug '14, 23:19

knauls93's gravatar image

3★knauls93
11
accept rate: 0%

My accepted solution is here:- http://www.codechef.com/viewsolution/4565844 Can anybody comment on this solution regarding its quality and improvement? Thanks a lot!!!

link

answered 15 Aug '14, 21:59

c000p's gravatar image

2★c000p
11
accept rate: 0%

Can someone please explain the need for seen_before vector used in the author's solution

link

answered 15 Aug '14, 23:39

ronaldo_007's gravatar image

3★ronaldo_007
3112
accept rate: 20%

http://www.codechef.com/viewsolution/4551310 plzz anyone help me of why i m getting WA

link

answered 27 Aug '14, 11:42

anshubhuwania's gravatar image

3★anshubhuwania
1
accept rate: 0%

What's wrong with this approach? http://www.codechef.com/viewsolution/4543202

link

answered 30 Aug '14, 19:21

rots's gravatar image

2★rots
111
accept rate: 0%

NICE QUESTION BASED ON OPTIMAL PAGE REPLACEMENT ALGORITHM.

link

answered 12 Jan '15, 23:44

tezaswy_singh's gravatar image

1★tezaswy_singh
1
accept rate: 0%

Hi. I tested and debugged my code. Getting wrong answer for following test cases.

1

3 31

7 11 17 10 7 10 2 9 2 18 8 10 20 10 3 20 17 17 17 1 15 10 8 3 3 18 13 2 10 10 11
My Answer : 19 Correct Ans : 18

1

3 20

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

My Ans : 10 Correct Answer : 9

Please REVIEW my code and hint if anyone can see some other vulnerability.

I suspect that some how the PriorityQueue is messing it as couldn't really verify that.

Thanks in Advance.

Link to my Solution : https://www.codechef.com/viewsolution/12889979

link

answered 19 Feb, 23:21

pyrocoder's gravatar image

0★pyrocoder
1
accept rate: 0%

edited 19 Feb, 23:23

-1

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

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

link

answered 11 Aug '14, 16:27

j1k7_7's gravatar image

5★j1k7_7
01
accept rate: 0%

-1
link

answered 11 Aug '14, 20:15

uj2295's gravatar image

2★uj2295
0
accept rate: 0%

-2

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?

link

answered 11 Aug '14, 15:32

ketanhwr's gravatar image

6★ketanhwr
1.9k21644
accept rate: 15%

2

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. :-)

(11 Aug '14, 16:02) gkcs5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,590
×780
×716
×31
×13

question asked: 11 Aug '14, 15:13

question was seen: 7,614 times

last updated: 19 Feb, 23:23