evandrix's blog

Marathon24 contest quals: DNA [deleted]
By evandrix, 11 years ago, In English

  • Vote: I like it
  • -18
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

as i mentioned before on the main blog comment, the given test data is special, and i'm not sure if there's algorithm with less than O(N^2) complexity on the worst case

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

There is an algorithm with linear complexity :). If you managed to pass all tests with O(n^2) complexity it was rather undesirable :P. There are two tricky observations in this task, which can be easily proven:

  1. If we want to maximize only the ratio, not the length, we can consider substrings with only one bad letter.

  2. If length is also taken into cosideration, we should additionally check if there exists a substring of form 0000110000 (k zeros, 2 ones and k zeros), where k is the best ratio. Given that observations we can easily come up with a linear algorithm.

P.S. At the beginning the ratio of T's and C's to the A's and G's was near 1. Later, in order to make inputs better compress, this ratio were highly lowered. P.S.2 I've come up with an idea for this problem (others were monsoon's), hope you enjoyed it :).

→ Reply