0
$\begingroup$

I'm trying to solve this problem, but without success.

Problem: You're given a binary string where some of the bits are replaced by ?. You're also given several intervals [$l_i$, $r_i$] ($l_i < r_i$). Find a binary string S with ? replaced by 0 or 1, such that in each interval [$l$, $r$], s[$l..r$] includes both 0 and 1.

Example:

Given the string 00?11 and the interval [2, 3], the string 00111 satisfies the requirements, as S[2..3]=01 include both 0 and 1.

However, the string 00?11 and the intervals [2, 3] and [3, 4] cannot be solved, as the ? would have to be both 0 and 1.

The bounds are |S|,Q<=1e5

I tried using greedy, but it's giving wrong answer for this case: 0??0, [1, 3], [2, 3] and [3, 4], as the greedy algorithm would try 0??0 -> 01?0 -> 0100 -> fail, yet there exists a solution (0010).

I tried removing completely overlapping intervals (such as [1, 3] and [2, 3]), but there're other cases I found that fails. What would be a correct solution?

Thanks.

$\endgroup$
2
  • 1
    $\begingroup$ I think you made an error in your greedy example. Since the given string is 0??1, you will have 0??1 -> 01?1 -> 0101 and you have a correct solution. $\endgroup$
    – Jakube
    Commented Aug 19, 2020 at 19:34
  • $\begingroup$ @Jakube Sorry, I've updated my greedy counterexample. $\endgroup$
    – Gareth Ma
    Commented Aug 20, 2020 at 7:31

1 Answer 1

2
$\begingroup$

There are 4 types of intervals:

  1. Intervals containing both $0$ and $1$ (e.g. 00?11?). Such intervals are already satisfied, and we simply ignore them.

  2. Intervals which can't be satisfied: either of length 1 (e.g. 0, ?), or contain only 0's or 1's (e.g. 000, 111). If such an interval exists, report "no solutions".

  3. Intervals which consist only of 0's or only of 1's and have a single ? (e.g. 00?0, 1?). For such intervals, we know what ? must be - so we just set ?, satisfying the interval, and ignore the interval from now on.

  4. Intervals which have more than one ?. We'll talk about them later.

The first phase of the algorithm is to get rid of Types 1, 2, 3. Note that when we satisfy an interval of Type 3, other intervals can change their Type.

while (true) {
    Remove all intervals of Type 1
    Check that there are no intervals of Type 2
    if (there exists an interval of Type 3) {
        Satisfy and remove this interval
    } else {
        break
    }
}

As a result, only intervals of Type 4 remain. Each such interval has two ?. In particular, it covers two consecutive remaining ?'s. Therefore, it suffices to assign to the remaining ?'s values 0, 1, 0, 1, 0, 1, ..., from left to right.


Now, the efficient algorithm for the first phase. We process all intervals in increasing order of their right ends. We maintain a set of intervals $T_4$ (initially empty) of currently encountered Type 4 intervals, sorted by their left ends.

For each new interval, depending on their type, we do the following:

  • Type 1: Ignore it

  • Type 2: Return "no solutions"

  • Type 4: Add an interval into $T_4$.

  • Type 3: Satisfy it. Now we look into the rightmost interval $I$ in $T_4$ (i.e. with the largest left end). If it changed its type, remove it from $T_4$ and process it again (i.e. check its type and apply the corresponding action from this list). Otherwise do nothing: since $I$ didn't change its type, other intervals in $T_4$ also won't change their type.

    Indeed, let $I'$ be another interval from $T_4$. If $I \subseteq I'$, we are fine (if $I$ has two ?, then $I'$, which contains $I$, also has them). Let $i$ be the position of the fixed ?. If $i > right(I')$, then we are fine. Otherwise, we have $i \le right(I') < right(I)$. But note that there are no ? between $right(I')$ and $right(I)$: otherwise, the currently processed interval wouldn't be Type 3, since it has at least two ?'s. Therefore, $I \cap I'$ has at least two ?'s, and therefore, $I'$ too.

While processing Type 3, we find the rightmost interval $I$ in $T_4$ until $T_4$ is empty or $I$ didn't change its type. Simply put, we remove intervals from $S$ while there are intervals which change their type.

$\endgroup$
3
  • $\begingroup$ I have questions about the time complexity of algorithm. (rmb L,R,N,Q<=1e5) I believe the step Check that there are no intervals of Type 2 will be O(n) over all segments if I store the number of zeroes, ones and question marks and update when satisfying type 3 intervals. That makes the whole algorithm will be O(n^2) as the loop can run for O(n) (Maybe n/2?), which gives time limit exceeded... :( $\endgroup$
    – Gareth Ma
    Commented Aug 20, 2020 at 7:48
  • $\begingroup$ @GarethMa, I've explained how to do this efficiently. $\endgroup$
    – user114966
    Commented Aug 20, 2020 at 8:20
  • $\begingroup$ can you explain what do you mean for While processing Type 3, we find the rightmost interval I in T4 until T4 is empty or I didn't change its type.? Also in the instructions for type 3, what do you mean remove it from $S$ (i.e. $T_4$) and "process it again"? Thank you. $\endgroup$
    – Gareth Ma
    Commented Aug 20, 2020 at 11:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.