Doubt on the Question on ICPC Kharagpur's List Editing Question

This was the link to the question - http://www.codechef.com/ACMKGP13/problems/EDITLIST/
This was the answer’s link-
http://www.codechef.com/viewsolution/2916089
WE tried all possible test cases that we could generate.Can you pls help which test case went wrong?
Advance thanks

Is it because the answer should we make should be in the sorted order?? :frowning:
But i dont think so, because we did not find such a case in the question…

Unfortunately the problem statement for this question was not clear and many people have misinterpreted it.

Your solution is correct for the question that you have interpreted which even i feel is logical. However the actual question is to find the minimum number of moves while maintaining the sorted property of the lists. e.g. 1 4 5 and 1 3 4. according to your solution replace 5 by 3 to make them equal in one move which gives 1 4 3 which is not sorted. According to the expected solution, the answer will be delete 5 and then insert 3 to get 1 3 4 which is in sorted order.

This problem is equivalent to the Edit Distance problem for strings which has a pretty standard O(n^2) Dynamic programming solution.

2 Likes

@kcahdog: Thanks buddy…that was the same thing which we were thinking of…But finally we thought that will not be the way…We any how lost it…we were trying out with the same problem untill 12.30…now it it over…any how unfortunalty we did not qualfiy but now in the latest ranking we have got that AC.But had it been at that time we cud have gone for the last problem…Let us hope for the best next time…:slight_smile:

Exactly same with us. good luck for next year