PROBLEM LINKS
DIFFICULTY
Easy
PREREQUISITES
Dynamic Programming, Levenshtein Distance
I helped check the judge data for this problem. Unfortunately, I never saw the possible mis-interpretation of the problem statement. An ill-fated comment certifying the wrong interpretation further added to the confusion and made a mess of things.
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.
PROBLEM
You are given two sequences of integers. You wish to make make both of them alike. You can perform the following three types of operations
- Add an integer at any position
- Delete an integer from any position
- Replace an integer at some position with another integer at the same position
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.
EXPLANATION
Let us assume that
- Ai is the ith number in the first sequence.
- A(i) is the sequence of the first i numbers from the first sequence.
- Bj is the jth number in the second sequence.
- B(j) is the sequence of the first j numbers from the second sequence.
- D(i,j) is the minimum number of operations required to solve the problem for A(i) and B(j).
We can see that
- D(0,0) = 0
- D(0,j) = j
- since all j characters will need to be added.
- D(i,0) = i
- since all i characters will need to be deleted.
There are two cases to consider
Ai = Bj
If it takes K operations to solve the problem for D(i-1,j-1), it will take K operations to solve the problem for D(i,j). No additional operation will be needed.
Ai ≠Bj
In this case, we can do one of the followings
replace Ai with Bj
Again, if it takes K operations to solve the problem for D(i-1,j-1), we will take only 1 more operation to cause this replace operation. The total operations for D(i,j) will be K+1.
add Bj to the first sequence
This will only be done if Ai < Bj. In this case, we must find the answer for D(i,j-1), since we have created a match for Bj.
delete Ai from the first sequence
This will only be done if Ai > Bj. In this case, we must find the answer for D(i-1,j), since we no longer need a match for Ai.
Hence, the recursion of the Dynamic Programming algorithm looks like
D(i,j) = min( D(i-1,j-1) if Ai = Bj, D(i,j-1) + 1 if Ai < Bj, D(i-1,j) + 1 if Ai > Bj, D(i-1,j-1) + 1 if Ai ≠Bj )
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 EXPLANATION
The 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 4 2 3. The order of integers is not the same as the second sequence in the test case. If it were required to be, the answer would have been 2.
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( M-match, N-match ) numbers from the first list and add or delete max( M-match, N-match ) - min( M-match, N-match ) numbers on the first list.
Thus, the answer would be max( M-match, N-match ). The value of match can be found in O( M + N ) time.
TESTER’S SOLUTION
Can be found here