You are not logged in. Please login at www.codechef.com to post your questions!

×

Easy

# PREREQUISITES

Dynamic Programming, Levenshtein Distance

<note>
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.
</note>

# 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

This question is marked "community wiki".

asked 03 Nov '13, 11:15

2.4k128183169
accept rate: 14%

19.7k350498541

 15 This is bullshit . Our team spent whole of the 2 hours trying to solve this problem, which gave WA at that time. We were not able to move on to other questions because of this Stupidly written problem statement. Sucks to know that this happened in such a Big contest . answered 05 Nov '13, 14:56 114●2●3●9 accept rate: 0% yeah. Same for our team! We submitted the code in 15 minutes of starting of the contest and kept getting WA for the rest 2 hours!! (05 Nov '13, 16:06)
 6 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 106●2●3●4 accept rate: 0%
 2 Give this EDITORIAL to the admin who said "order isn't necessary". GUESS WHAT Mr. admin????? IT WAS VERY NECESSARY answered 07 Nov '13, 23:57 38 accept rate: 0% 3★kcahdog 10.0k●28●54●129 1 Please mind your language!! They have made a mistake but this is no way to talk. P.S. The earlier comment was not appropriate and was edited (08 Nov '13, 22:07) kcahdog3★
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,477
×3,704
×2,085
×12

question asked: 03 Nov '13, 11:15

question was seen: 3,808 times

last updated: 13 Nov '13, 17:48