Skip to content

[CodeChef] Starters 72 — Good Sequence: exactly one more one, not at least one

Published 6 October 2026

Problem: CodeChef — Good Sequence (Starters 72, difficulty 2451).

You’re given a binary array \(B\) of length \(N\). A sequence \(1 \le x_1 < x_2 < \dots < x_k \le N + 1\) is good if for every pair \(i < j\), the subarray \(B[x_i : x_j - 1]\) has exactly \(j - i\) more ones than zeros. A sequence of length \(1\) is always good. Find the longest good sequence and print one.

Constraints: \(N \le 10^5\), \(\sum N \le 10^6\).

Turn it into prefix sums

Map each \(1\) to \(+1\) and each \(0\) to \(-1\), and let \(P[t]\) be the sum of the first \(t\) values, with \(P[0] = 0\). Think of each \(x\) as a boundary: \(x\) sits just before element \(x\), so it’s prefix position \(x - 1\). Then “\(B[x_i : x_j - 1]\) has \(j - i\) more ones than zeros” is

\[P[x_j - 1] - P[x_i - 1] = j - i.\]

Only consecutive pairs matter

For consecutive elements, \(j - i = 1\), so each step must raise the prefix sum by exactly one. Once every consecutive step does that, every other pair follows by telescoping:

\[P[x_j - 1] - P[x_i - 1] = \sum_{t=i}^{j-1} \bigl(P[x_{t+1} - 1] - P[x_t - 1]\bigr) = j - i.\]

So the \(O(k^2)\) pair conditions collapse to \(k - 1\) conditions: pick increasing boundaries whose prefix sums go \(v, v+1, v+2, \dots\). Find the longest such chain.

The DP

Let dp[b] be the longest good sequence ending at prefix boundary b. Its previous boundary must have prefix sum P[b] - 1, and it might as well be the one with the best dp so far. So keep a map from prefix sum to the best (dp, boundary) seen with that sum, and store a parent pointer to rebuild the sequence. Every boundary can start a sequence on its own, so dp starts at \(1\). That’s \(O(N)\) per test.

Where I went wrong

I read “more ones” as “at least one more”. My first version of the condition was \(P[b] > P[a]\). That only says the segment has some excess of ones. The statement wants the excess to be exactly \(j - i\), and for neighbours \(j - i = 1\). The segment [1, 1] has sum \(2\): it satisfies \(P[b] > P[a]\) but isn’t allowed between neighbours. The wording makes you track two things at once, the distance in the sequence and the ones-minus-zeros count, and I missed that the first one pins the second to exactly \(1\).

I was reasoning about majorities and parities. My draft notes asked whether two good segments glued together are still good, by parity cases (even + even, odd + odd, …), and planned a DP over “suffixes with a majority” with a condition like pre[j] + (j - i) // 2 < pre[i]. None of that is needed once the condition is read as “exactly \(+1\) per step”. The telescoping argument above is the whole story.

I thought the + 1 when printing was wrong. The loop index i is 1-based, but it counts how many elements the prefix contains. It’s not the problem’s \(x\). Boundary \(0\) (nothing read yet) is \(x = 1\), boundary \(1\) is \(x = 2\), and in general boundary \(i\) is \(x = i + 1\). So the boundaries [1, 4, 5, 6] are the answer 2 5 6 7.

Two bugs in the first draft.

  • dp started at \(0\) when there was no predecessor. It should be \(1\): a single index is a good sequence by itself.
  • The best answer was tracked with if dp[i] > best_end, comparing a length with an index. It should be dp[i] > dp[best_end].

I wanted to assert best_end == n. The longest chain can end at any boundary, not only the last one. Forcing it to end at \(N\) would only consider sequences that reach the end of the array.

I thought a lone 0 breaks a length-1 sequence. The -1 only matters on the segment between two chosen boundaries. A sequence with one index has no pairs to check, so it’s good whatever the element under it is. dp[i] = 1 means “start a new sequence here”, not “this element is a valid \(+1\) segment”.

Code

My accepted submission. The docstring is my scratch notes from before the “exactly \(+1\)” reading clicked, so the majority and parity ideas in it are the wrong turn described above.

Also checked against a brute force over every subset of boundaries on 3,000 random arrays with \(N \le 9\). On the first sample it prints 2 3 4 7 instead of the expected 2 5 6 7; both have length \(4\), and any longest sequence is accepted.

# cook your dish here

"""
1 <= x1 < x2 < ... xk <= N+1

if B[x1: x2-1] is good
B[x2: x3-1] is good
B[x3: x4-1] is good
..
B[xk-1: xk - 1] is good

can i say that B[x1: x3-1] is good ?

e + e => yes
o + o => yes
o + e
e + o

let dp(i) = max subseq length from 0..i
transition:
    - choose some suffix such that the suffix has majority
    - dp(i) = max(dp(i-j) + 1) over all j s.t  B[i-j:i] is good

Basically break the array B into as many segments as possible ok, if we keep track of prefix sums then
    at i i want to chooose j's s.t pre[j] + (j-i)//2 < pre[i]
"""

def solve():
    n = int(input())
    arr = list(map(int, input().split()))

    dp = [1]*(n+1)
    best_for_sum = {0: (1, 0)} # (prefix_sum: (dp(i), i))
    parent = [-1]*(n+1)
    prefix = 0
    best_end = 0

    # dp[i] := longest sequence ending at boundary i
    for i,bit in enumerate(arr, 1):
        prefix += 1 if bit == 1 else -1

        # To reach this boundary, the previous prefix sum must be one less
        previous = best_for_sum.get(prefix-1)
        if previous is not None:
            dp[i] = previous[0] + 1
            parent[i] = previous[1]

        # Make this boundary available as a predecessor for later ones
        current = best_for_sum.get(prefix)
        if current is None or dp[i] > current[0]:
            best_for_sum[prefix] = (dp[i], i)

        if dp[i] > dp[best_end]:
            best_end = i

    # Follow parent links to recover the chosen boundaries
    boundaries = []
    boundary = best_end
    while boundary != -1:
        boundaries.append(boundary)
        boundary = parent[boundary]
    boundaries.reverse()

    answer = [boundary+1 for boundary in boundaries]
    # answer = boundaries
    print(len(answer))
    print(*answer)


tc = int(input())
for _ in range(tc):
    solve()