CLETAB - Editorial

editorial
, , , ,
21

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

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

22

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;
}
23

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.

4 Likes
24

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

25

@gkcs Thanks! I now understood it!

1 Like
26

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
:slight_smile:

27

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

28

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

29

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

1 Like
30

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!!!

31

Can someone please explain the need for seen_before vector used in the authorā€™s solution

32

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

33

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

34

NICE QUESTION BASED ON OPTIMAL PAGE REPLACEMENT ALGORITHM.

35

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

36

Iā€™ve added an answer that uses optimal page replacement algorithm.
Iā€™ve commented it so that everyone can get the idea.
Do have a look if you are stuck.