Can someone please explain the need for seen_before vector used in the author’s solution
NICE QUESTION BASED ON OPTIMAL PAGE REPLACEMENT ALGORITHM.
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
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.
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. 
2 Likes
Please look at my answer
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
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.
replace 0 with any other number which is not already in list for example 5 .
2 Likes
A very important thing for any programmer is debugging his own code. And that includes generating weird test cases. Nice answer
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
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
I think I have solved all the corner cases. I am getting a runtime error. Can anyone suggest why ?
https://www.codechef.com/viewsolution/26251204