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

×

KGP13G - Editorial

PROBLEM LINK:

Practice
Contest

Editorialist: Jingbo Shang

DIFFICULTY:

Easy - Medium

PREREQUISITES:

Dynamic Programming, Trie

PROBLEM:

Given K words W[1..K], determine the minimum number of words need to exact cover (without any overlaps) a given string S[1..n].

EXPLANATION:

It is worth to note that although the number corresponds many characters, each character is only mapped to one number. Therefore, we can translate the characters to numbers.

After that, we can further observe that the exact cover can be performed in order such that each time the covered part is the prefix of the string. That is, given any possible solutions, we can always arrange the order of words to make sure that the covered part is always a prefix of the string. This gives us the opportunity of dynamic programming.

Use f[i] to stand for the minimum number of words needed to cover S[1..i]. Then we can get the recursion:

f[0] = 0;
f[i] = min{ f[j] + 1 };  for all 0 <= j < i and S[j+1 .. i] is a word.

This dynamic programming is O(nKL) if we implement by trying all words. Here L is the maximum length of words. We can improve this situation by building a Trie for the word list. With Trie, the time complexity can be improved to O(nL), because we do not perform any extra matching between the string and words.

This question is marked "community wiki".

asked 29 Dec '13, 11:27

admin's gravatar image

0★admin ♦♦
19.8k350498541
accept rate: 36%

wikified 29 Dec '13, 11:28

kunal361's gravatar image

4★kunal361
6.0k133272

can anyone explain this with an example?

(20 Mar '14, 09:28) milindshah0771★
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,852
×2,212
×1,722
×186
×14

question asked: 29 Dec '13, 11:27

question was seen: 1,657 times

last updated: 20 Mar '14, 09:28