Genome Sequencing puzzle discussion

Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements
Example : abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, … etc are subsequences of “abcdefg”

Substring of a string S is another string S that occurs “in” S.
Example : “the best” is a substring of “It was the best of times”.

There is a minor difference :stuck_out_tongue: :slight_smile: What you are referring to is substring but the problem says subsequence.

I actually whent throught this Article : Shortest Common Supersequence and was baffled when my code didn’t pass the testcases.

###PS: Geeks4Geeks is really helpful for Hard Problems and Competitive Programming

You are mathematically right but the problem is about genome. So… you might report a bug.

me too, I have a code with the validation test A + C = AC not working. Anybody known how th debug a validation test, or the imput data for this test.
thanks a lot

I used Java, and given the small number of subsequences, I could pass all tests using a brute force algorithm. i think you are just interpreting the results wrong

In my cases, tests pass.
For validations, the only one that fails is “Almost superimposed”.

I try a case like the one below and it works.
This is what I would assume to be almost superimposed.


Any clues on what to expect for this case ?

I have a problem with one of the validators as well, namely, Example 3, but with the first two words nested. I’ve tried a bunch of combinations from Example 3 and everything seems to be correct. All of the other validators and tests pass smoothly. Any ideas?
(PS. I wish the names of validators would be more specific, since right now all the feedback I get is ‘something’s wrong! good luck trying to figure out what.’

Maybe cause most people fail at the A+C = AC one include it in the test cases so people can debug that one or see what is wrong with it. I’m one of those people who is failing at this one, and only this one, and it’s kinda frustrating to solve something where you can’t see your fault.

I have the same problem with A + C test.

But, if I do (Groovy)

`N = input.nextInt()
subseqs = []
for (i = 0; i < N; ++i) {
subseq =
subseqs << subseq

subseqs = []
subseqs << “C”
subseqs << “A”
(I force A and C as inputs)

This test pass !!!
So the good answer is 2. But I still don’t know what is the input… :confused:

Same problem with A + C =AC.
All other tests pass (IDE+check) and if I simulate “A” and “C” as input, it works (It returns 2).

I only think to 2 reasons to have this results:

  1. They reduce the time limit for A+C=AC test
  2. There is a problem with inputs or the result expected

I had the exact same problem with A+C = AC test and solved it by changing a little thing (I ordered by length the testing of sequences that completly contains another).

So I think it should be as @Drahull said a time limit issue. Try to figure out a worst case for your algorithm with a lot of “A” “C” and “AC”.
Or maybe it has nothing to do with it and it fixed a small issue in my code, but as I tested many case I don’t think so.

Or not (see below), try with this : {A;C;AC} in this order.

Oh, i didn’t think about having a lot of “A” and “C” in inputs. I’ll check this.

N line : each between 1 & 10 char.

Constraint :
0 < N < 6

Worst case : 60 char…
I still don’t have a timeout :confused:

Maybe they should create a similar test on IDE. Like T + G = TG

I found it, my reordering fixed a minor issue in my code after all. Try with these inputs:



It works ! It was it, thanks Bandersnatch !

Thanks a lot !

Hi there.
Like @naruchaaan, I’m stuck with the “Example 3, but with the first two words nested”.

I’ve tried an input like this:


But does not seems to match the validator.
If the validator name could be more expressive (sorry for not being english native), we could find a way out.

I cannot pass MIRROR and MIRROR REVERSE,can anybody offer me some MIRROR cases?thanks a lot!

I have the same problem with “13 Sequences included and disjointed”, I do not know what to do. What are the inputs?