3999 - The Longest Constant Gene

[serur]

The problem is solvable in linear time, but requires huge memory:

392960

Is it possible to make such memory available for this problem only?
Thanks.

[Carlos]

It is actually possible, but I have to think about hether it's fair to increase the memory limit:

- In one side, the number of MLE is huge. We should look for the fastest algorithm no matter how much memory it uses. Time limit should also be fixed to that fastest algorithm, so if you manage to solve the problem in 1s we should set the time limit back to 10s.

- On the other side, many users already submitted using a non linear approach in order to not use as much as memory. They got penalized in speed. It wouldn't be fair to judge them as TLE now, would it?

What do other users think?

[serur]

My current solution is O(nlogk). But I'll submit to your consideration the strictly linear solution when it's ready.

[Carlos]

You can mail it to me, I can tell you what the execution time is for your linear solution.

[serur]

Ah, Carlos, the memory required for linear algo is immense, so I'd rather say we'd drop it all.
The like suggestion made about "Permutation recovery" (n<=500 to n <= 100000) met with your
quite just disapproval on the grounds that this site is, after all, an "Archive". So thank you very much
for your concern; we'll submit a k-common substring with n_1 + ... n_k <= 100000 in one of our
contests, no doubt