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

×

BIGO01-Editorial

Problem Link :

Practice
Contest

Author: Amrutansu Garanaik , Abhishek Patnaik
Tester: Keshow Sablaka, Amit Das
Editorialist: Amrutansu Garanaik , Amit Kumar Sahu

Difficulty :

Easy-medium

Pre-requisite

Levenshtein distance algorithm, Longest common subsequence

Problem :

Given four strings, find minimum number of charater removal required to make all the strings equal.

Explanation

Approach 1

The problem is a standard dynamic programming problem. This can be solved using Levenshtein distance algorithm, also known as Edit distance algorithm. For the given problem, we had to extend the algorithm for four strings. See the setter solution 1 for implementation.

Approach 2

Since we are to make the strings equal only by removing certain elements, the resulting strings must be equal to the longest common subsequence of the strings. So, finding the length of the longest common subsequence is required which is also a standard dynamic programming problem. After finding the length of the longest common subsequence, we can subtract it from the lengths of the each strings. The difference is the number of characters removed from the string. The sum of the results of the four subtractions is the required number of characters removed. See the setter solution 2 for implementation. N.B. If you can solve it using some other methods, please share in the comments.
This question is marked "community wiki".

asked 03 Apr '15, 20:15

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%


All you need is a bit of maturity to generalise :) obviously you can never imagine in 4 th dimension !! Nice :)

link

answered 03 Apr '15, 23:32

anh1l1ator's gravatar image

6★anh1l1ator
142618
accept rate: 11%

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,639
×2,167
×1,672
×15
×2

question asked: 03 Apr '15, 20:15

question was seen: 971 times

last updated: 03 Apr '15, 23:32