3
$\begingroup$

I'm quite intrigued by an "easy" problem in recent Codeforces contest: Codeforces Subsequences.

In this problem, you have to create a string $T$ as shortest as possible such that $S = $ "CODEFORCES" appears as the subsequence (not substring) of $T$ at least $K$ times. We actually don't care about this $K$, for this puzzle at least, as we can reformulate the problem as the following:

Given $S = $ "CODEFORCES", find a string with length $N$ such that $S$ appears as subsequence as many as possible.

It turns out, this "simple" strategy works well (marked as spoiler, as this is also the solution for the original problem, but this is needed for the puzzle):

You try to clone the first letter 'C', then clone the next 'O', then clone the next 'D', and so on. After cloning the last letter 'S', you clone again the 'C' (so there are $3$ 'C's) then 'O' (so there are $3$ 'O's) and so on. You keep doing this until the length is $N$.

So if $N = 23$, then "CCCOOODDDEEFFOORRCCEESS" is optimal. There are $3^3 \times 2^7 = 3456$ subsequences of $S = $ "CODEFORCES" for your information.

Now the puzzle is this. Above strategy is pretty "obvious" to be correct for... most of possible $S$ and $N$. Surprisingly, for some people I think, actually it won't work for all possible $S$ and $N$. You task is to find such $S$ and $N$ so that above strategy is wrong!


Nb. Even if this problem is taken from the Competitive Programming contest, this puzzle should be done by hand, thus . A subsequence is a sequence generated from a string after deleting some characters of string without changing the order of remaining string characters.

$\endgroup$
1
$\begingroup$

Here's one possibility:

Take $S$ to be BASS, and $N$ to be $6$.

Our strategy dictates the final string should be

BBAASS, which has $4$ subsequnces equal to BASS.

But we can do better:

by taking BASSSS, which has $6$ of them.

$\endgroup$
1
  • $\begingroup$ Yup, this will do! How if two adjacent letter must be different? :) $\endgroup$ – athin Jun 19 '20 at 4:40
3
$\begingroup$

Take the string as "abcbc" and k=5. Now, according to the algorithm we have "aabbccbc"(three extra characters). But, due to the repitition of "bc", we can take the string as "abcbcbc"(which has just two characters extra). This will give us exactly 5 subsequences of "abcbc".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.