0
$\begingroup$

Recently I am training for an algorithm contest. One of the older textbooks for that contest contains this question:

Generate all strings $S$ that contained the letters $\begin{Bmatrix}A, B, C\end{Bmatrix}$ only, and satisfy these requirements:

  1. The string's length (number of characters) must be exactly 100
  2. No two adjacent strings are the same (formally this means that no two adjacent characters are the same and for all triplets $(a, b, c)$ such that $a \leq b < b + 1 \leq c \leq 100$, $S[a..b] \neq S[b+1..c]$ with $S[x..y]$ taken to be the substring from the $x$th letter to the $y$th letter
  3. The letter 'B' must be used at few times at possible

I have an algorithm in mind, however it has time complexity of $O(3^n . n^3)$, which is too large for the requirement of $n = 100$. Do you have any suggestions or pieces of example code? Thanks for your help!

Improve this question
$\endgroup$
4
  • $\begingroup$ Please credit the source where you encountered this question. See our referencing rules: cs.stackexchange.com/help/referencing. Thank you! $\endgroup$
    – D.W. ♦
    May 11 at 21:34
  • $\begingroup$ 1. What's the longest string you can make without using 'B', while following rules 1+2? 2. What's the longest string you can make, using only one 'B', while following rules 1+2? 3. What's the longest string you can make, using only two 'B's, while following rules 1+2? 4. Can you noticing any possible pattern? Can you think of any way to check that pattern? $\endgroup$
    – D.W. ♦
    May 11 at 21:36
  • $\begingroup$ What are your thoughts? What progress have you made? We are not particularly looking for questions that consist solely of a contest-style task (and possibly a trivial exponential-time algorithm) and a request for us to show you the solution. We're happy to help you understand the concepts but just solving contest-style tasks for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W. ♦
    May 11 at 21:37
  • $\begingroup$ Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. $\endgroup$
    – D.W. ♦
    May 11 at 21:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.