Minimum number of ways to write a string

Question

Consider the following question

There are K magical pens (numbered 1 through K). You are given strings P1,P2,…,PK (each of which consists of characters from 'a', 'b', …, 't') ; for each valid i, the i-th pen can only write letters from the string Pi

.

You want to write a word S of length N. All the characters of S are between 'a' and 't' inclusive. This string must be written from left to right. To write it, you pick up some pen and start writing; after you've written some prefix of S, you can put down that pen, pick up another pen, continue writing S from the point where you put down the previous pen, later pick up another pen (any pen) and continue writing S with that pen, and so on until you write the whole string S You may pick up each pen any number of times, including zero. You have to find a way of writing the word S such that the number of times you change the pen (put down the pen you're currently writing with and pick up another) is the smallest possible. If there are multiple solutions, you may find any one. It is guaranteed that it is possible to write S with the given pens.

I know that to represnt a pen as a number using bitset and solve it ,but how can i solve it faster.

Link for the question https://www.codechef.com/ICPCIN19/problems/PENS

Answer 1

First observation: As first pen you can always take a pen with which you can write the longest prefix.

Let's consider given pen-strings as bit stings. For each such bit string let's generate all substrings which correspond to subsets of an initial bit string and put them in hashtable. Moreover, let's generate them in descending (by nesting) order and when we generate some bit string which is already in hashtable, we terminate this branch of recursion. So each of $2^{20}$ possible bit strings will be generated at most twice.

Precompute for each prefix of string $S$ the number of times $i$-th letter occurs in it.

Then let's walk by string $S$ from left right and on each step let's check whether current prefix can be written with a single pen. We can do it in $O(1)$ using precomputed hashtable and prefixes.

So the overall complexity is $O(2^\alpha + K + N\cdot\alpha)$, where $\alpha$ is an alphabet size ($20$ in our case).

Answer 2

There's a simple $O(nk)$ greedy algorithm that assumes there is a solution:

1. Start with all pens in an array.
2. Eliminate all pens from your array that can not be used to write the next character. If this would remove all pens, instead output one of them and go back to 1.
3. Write the next character and go back to 2 if there are more characters to write.
4. Output one of the pens in your array and done.

If there are instances without a solution you need to detect, just check in step 2 whether you are removing all pens from a freshly created array.

Answer 3

"Making it faster" by tweaking data representation won't buy much. It could speed it up by, say, a factor of 2 if you are lucky (or the original is very badly written). To get real speedup you need to use another approach (change basic algorithm).

I suspect the obvious greedy algorithm succeeds: Take as the next pen those that allows you to write the longest prefix of what remains. There must always be one (as each symbol can be written by some pen), and no pen selection can block a later one (if you can write $\alpha \beta$, you certainly can write $\beta$ with that same pen).