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

×

KGP14B - Editorial

PROBLEM LINK:

Practice
Contest

Editorialist: Lalit Kundu

DIFFICULTY:

EASY

PRE-REQUISITES:

Dynamic Programming

PROBLEM:

Given two sequences S1 and S2 of characters {A,T,C,G} find the length of the smallest sequence that contains both the given sequences as subsequence.
Length of both sequences less than 1000.

EXPLANATION:

Let's say dp[i][j] denotes the answer for first i characters of S1 and first j characters of S2.
Now, recurrences will be as follows:

//note we are using 1 indexing.

//if both characters are matching
if S1[i-1]==S2[j-1]:
    dp[i][j]= 1 + dp[i-1][j-1]

//characters don't match
//first try to place S1[i] at the end
//then try to place S2[j] at the end
//take minimum of both
else:
    dp[i][j] = 1 + min(dp[i][j-1] , dp[i-1][j])

Note the base case:
If i<1, S1 doesn't exist, so answer will be j.
If j<1, S2 doesn't exist, so answer will be i.

Complexity: O(len(S1) * len(S2)).

Very basic DP similar to this is LCS.
Infact, another intuitive way to look at this problem is that we need to overlap as many characters of S1 and S2. So our answer would be len(S1)+len(S2)-len(LCS(S1,S2)), where LCS(X,Y) is longest common subsequence of strings X and Y.

IMPLEMENTATION:

Recursive DP with memoization is always easy to implement. See editorialist's code for implemenation details.

SOLUTIONS:

Editorialist's solution

This question is marked "community wiki".

asked 25 Dec '14, 00:05

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,682
×2,172
×1,672
×20

question asked: 25 Dec '14, 00:05

question was seen: 1,800 times

last updated: 23 Sep '15, 00:47