PROBLEM LINKSDIFFICULTYEasy PREREQUISITESDynamic Programming, Levenshtein Distance <note> A lot of teams spent more time than they would otherwise have on this problem. No resolution will be fair to all the time, that everyone  setters, testers, admins and of course, all the students who participated  spent on the contest. But, I believe there is some justice in accepting solutions submitted in leu of the alternate interpretation as well as the solutions that were already accepted. PROBLEMYou are given two sequences of integers. You wish to make make both of them alike. You can perform the following three types of operations
In the end, you want to make both the sequences exactly the same, even the order in which the numbers are present. What is the minimum number of operations required to achieve this. EXPLANATIONLet us assume that
We can see that
There are two cases to consider A_{i} = B_{j}If it takes K operations to solve the problem for D(i1,j1), it will take K operations to solve the problem for D(i,j). No additional operation will be needed. A_{i} ≠ B_{j}In this case, we can do one of the followings replace A_{i} with B_{j} add B_{j} to the first sequence delete A_{i} from the first sequence Hence, the recursion of the Dynamic Programming algorithm looks like D(i,j) = min( D(i1,j1) if A_{i} = B_{j}, D(i,j1) + 1 if A_{i} < B_{j}, D(i1,j) + 1 if A_{i} > B_{j}, D(i1,j1) + 1 if A_{i} ≠ B_{j} ) The answer will be D(M,N). The problem in the practice section will accept such a solution. There is an alternate interpretation of the problem statement. The problem in the practice section will not accept solutions for the explanation below. ANOTHER EXPLANATIONThe problem statement failed to mention that the order of numbers should be the same in the end. Without this condition, the problem changes. Take for example the following test case. 3 1 2 3 3 2 3 4 Replacing 1 with 4 in the first sequence will give the sequence This problem can be solved by greedily eliminating all the matched numbers. Let match be the number of numbers that match in both the lists. Now, there are M  match numbers in the first list, none of which are equal to the N  match numbers in the second list. They can be made equal by replacing min( Mmatch, Nmatch ) numbers from the first list and add or delete max( Mmatch, Nmatch )  min( Mmatch, Nmatch ) numbers on the first list. Thus, the answer would be max( Mmatch, Nmatch ). The value of match can be found in O( M + N ) time. TESTER'S SOLUTIONCan be found here
This question is marked "community wiki".
asked 03 Nov '13, 11:15

This was really not at all expected from a contest of this stature. We spent almost the entire time solving this problem. Just because, you see more than 25% of the teams solving one question, it gives you a notion that this is the easiest problem of the set, and you really need to crack this one! How could you not... And then you end up with 6 WAs on the easiest question!!! You really dont know how frustrating that is during a competition... I would say, we missed an opportunity even to compete lest getting selected, just because of an improperly written description. You should have atleast made this clear in the testcases... Disappointment, it is!!! answered 05 Nov '13, 19:06
