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

- A
_{i}is the i^{th}number in the first sequence. - A(i) is the sequence of the first i numbers from the first sequence.
- B
_{j}is the j^{th}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

##A_{i} = B_{j}

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.

##A_{i} ≠ B_{j}

In this case, we can do one of the followings

**replace A _{i} with B_{j}**

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 B _{j} to the first sequence**

This will only be done if A

_{i}< B

_{j}. In this case, we must find the answer for D(i,j-1), since we have created a match for B

_{j}.

**delete A _{i} from the first sequence**

This will only be done if A

_{i}> B

_{j}. In this case, we must find the answer for D(i-1,j), since we no longer need a match for A

_{i}.

Hence, the recursion of the Dynamic Programming algorithm looks like

D(i,j) = min( D(i-1,j-1) if A_{i}= B_{j}, D(i,j-1) + 1 if A_{i}< B_{j}, D(i-1,j) + 1 if A_{i}> B_{j}, D(i-1,j-1) + 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 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