Sherlock Holmes is bored to death as there aren't any interesting cases to solve. Dr Watson finding it impossible to be around Sherlock goes out to get some fresh air. Just as he lays his feet out of the door, he is thrown right back into his house by the explosion in front of his apartment. The metropolitan police arrive at the scene a few minutes later. They search the place thoroughly for any evidence that could throw some light on the event that unfolded. Unable to get any clues, they call Sherlock for help. After repeated persuasion by Mycroft Holmes and Dr Watson, Sherlock agrees to look at the crime scene.
Sherlock walks into the apartment, the walls are all black and dripping wet as the fire was recently extinguished. With his skills, he observes, deduces and eliminates the impossible. What's left after it is a simple puzzle left by an evil computer genius and the future Arch Nemesis of Sherlock, Jim Moriarty.
Given a binary string (S) which contains '0's and '1's and an integer K,
find the length (L) of the longest contiguous subsequence of (S * K) such that twice the number of zeroes is <= thrice the number of ones (2 * #0s <= 3 * #1s) in that sequence.
S * K is defined as follows: S * 1 = S
S * K = S + S * (K - 1)
Answers
Explanation:
Here's a hint:
Let's first suppose K = 1 and that S looks like (using a dot for 0):
..1...11...11.....111111....111....
e f b a c d
The key is to note that if the longest acceptable sequence contains a 1 it will also contain any adjacent ones. For example, if the longest sequence contains the 1 at a, it will also contain all of the ones between b and c (inclusive).
So you only have to analyze the sequence at the points where the blocks of ones are.
The main question is: if you start at a certain block of ones, can you make it to the next block of ones? For instance, if you start at e you can make it to the block at f but not to b. If you start at b you can make it to the block at d, etc.
Then generalize the analysis for K > 1.
share improve this answer follow
answered Sep 10 '15 at 5:31
ErikR
49.2k66 gold badges6565 silver badges119119 bronze badges
This is a good start, but not enough unfortunately. You can also compress blocks like 1*n 0*k 1*m where 3 * min(m, n) >= 2 * k. Obviously these blocks always go together. Finding the longest sequence by going from one block of ones to the next left to right fails for example on this sequence: 1100100010011 where the solution is the whole sequence. – jakab922 Dec 17 '15 at 0:08
add a comment
0
Brute force obviously won't work since it's O((n * k) ** 2). I will use python style list comprehensions in this answer. You'll need an array t = [3 if el == "1" else - 2 for el in S]. Now if you use the p[i] = t[0] + ... + t[i] array you can see that in the k == 1 case you are basically looking for a pair (i, j), i < j such that p[j] - (p[i - 1] if i != 0 else 0) >= 0 is true and j - i is maximal among these pairs. Now for each i in 0..n-1 you have to find find it's j pair such that the above is maximal. This can be done in O(log n) for a specific i so this gives and O(n log n) solution for the k == 1 case. This can be extended to an O(n log n) solution for the general case(there is a trick to find the largest block that can be covered). Also there is an O(n) solution to this problem but you need to further examine the p sequence for that. I don't suggest to write a solution in a scripting language though. Even the O(n) solution times out in python...