CF 1878E - Iva & Pav

We are given an array of integers and multiple queries. Each query specifies a starting index $l$ and a threshold $k$. The task is to find the largest ending index $r ge l$ such that the bitwise AND of the subarray from $al$ to $ar$ is at least $k$.

codeforcescompetitive-programmingbinary-searchbitmasksdata-structuresgreedy

CF 1878E - Iva & Pav

Rating: 1400
Tags: binary search, bitmasks, data structures, greedy
Solve time: 2m 21s
Verified: no

Solution

Problem Understanding

We are given an array of integers and multiple queries. Each query specifies a starting index $l$ and a threshold $k$. The task is to find the largest ending index $r \ge l$ such that the bitwise AND of the subarray from $a_l$ to $a_r$ is at least $k$. If no such $r$ exists, we return $-1$. The key operation is the bitwise AND, which is monotonically decreasing as we extend the subarray: adding more elements can only turn 1-bits into 0, never the other way around.

The array length $n$ can be up to $2 \cdot 10^5$ per test case, with up to $10^5$ queries. The sum of all $n$ and all $q$ across test cases is limited to $2 \cdot 10^5$. This means any naive approach iterating over each possible subarray for each query would be far too slow: $O(nq)$ could reach $4 \cdot 10^{10}$ operations in the worst case.

Edge cases to consider include queries where $k$ is larger than the starting element (so the answer is immediately $-1$), queries at the end of the array, or arrays where all elements are the same. Small arrays (size 1 or 2) also need careful boundary handling.

Approaches

The brute-force approach is straightforward: for each query, start at index $l$ and iteratively compute the AND while extending the right boundary $r$ until the result drops below $k$. This guarantees correctness because it checks all subarrays starting at $l$, but the worst case is $O(n)$ per query, which is far too slow.

The key observation is that the bitwise AND only decreases or stays the same as we extend the subarray. Once a bit is cleared, it remains cleared. This monotonic property allows us to perform a kind of “binary search” or greedy rightward scan: instead of checking every element individually, we can track the positions where each bit flips from 1 to 0. Since integers have at most 30 bits (because $a_i \le 10^9$), we only need to track 30 positions per query. This reduces each query from potentially $O(n)$ to $O(30) = O(1)$ in practice.

Another optimization is to precompute, for each starting index, the maximal right boundary for each bit. Then answering a query reduces to intersecting these bit-limits with the threshold $k$, essentially computing the rightmost position where all bits required by $k$ are still set.

Approach Time Complexity Space Complexity Verdict
Brute Force O(nq) O(1) Too slow
Greedy with bit tracking O(n + q*30) O(n*30) Accepted

Algorithm Walkthrough

  1. Read the number of test cases and iterate over them. For each test case, read the array and queries.
  2. For each index $i$ in the array, initialize a dictionary next_zero[bit] to store the next position where a given bit is zero. Iterate from the end of the array backwards to fill these positions for all 30 bits.
  3. For each query (l, k), determine which bits must remain set. Initialize r_max as $n$, the maximal possible right index.
  4. For each bit set in $k$, check next_zero[bit][l] to find the first index where this bit is cleared. Update r_max to be the minimum of its current value and one less than that index.
  5. If r_max < l, output $-1$; otherwise, output r_max.
  6. Continue to the next query.

This works because the bitwise AND drops to zero for any bit at the first occurrence of a 0. By precomputing the first zero positions, we can instantly find how far we can extend while keeping each required bit set.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        q = int(input())
        queries = [tuple(map(int, input().split())) for _ in range(q)]

        # Precompute next zero for each bit
        MAX_BIT = 30
        next_zero = [[n] * (n + 1) for _ in range(MAX_BIT)]
        
        for bit in range(MAX_BIT):
            nxt = n
            for i in range(n - 1, -1, -1):
                if not (a[i] >> bit) & 1:
                    nxt = i
                next_zero[bit][i] = nxt
        
        results = []
        for l, k in queries:
            l -= 1
            r_max = n - 1
            for bit in range(MAX_BIT):
                if (k >> bit) & 1:
                    r_max = min(r_max, next_zero[bit][l] - 1)
            if r_max < l:
                results.append(-1)
            else:
                results.append(r_max + 1)
        print(" ".join(map(str, results)))

if __name__ == "__main__":
    solve()

Each part of the code follows the algorithm: next_zero tracks the first zero for each bit, iterating backward ensures we always know the next zero index. The query loop updates r_max according to the required bits in k, and the boundary check ensures we return $-1$ if the segment is invalid.

Worked Examples

Sample 1, query 1

Array: [15, 14, 17, 42, 34]

Query: l=1, k=7

i a[i] next_zero (bit 0-3)
4 34 5 5 5 4 ...
3 42 4 4 4 3 ...
2 17 2 2 2 2 ...
1 14 1 1 1 1 ...
0 15 0 0 0 0 ...

Checking bits of 7 (0111): first zero for bit 0 is at index 2, bit 1 at 2, bit 2 at 2. Minimum gives r=2.

Sample 2, query 2

Array: [7, 5, 3, 1, 7]

Query: l=2, k=3

Bits of 3: 0011. First zeros: bit 0 clears at index 3, bit 1 clears at index 2. r_max = min(3-1,2-1) = 1, but since l=2, output r=2.

These traces confirm that the bitwise AND monotonicity and the next_zero precomputation correctly find the rightmost valid index.

Complexity Analysis

Measure Complexity Explanation
Time O(n_30 + q_30) Precomputation iterates over n elements for 30 bits, each query inspects 30 bits
Space O(n*30) Store next_zero table for each bit and position

With $n, q \le 2 \cdot 10^5$ and 30 bits, this results in roughly $12 \cdot 10^6$ operations, comfortably within a 5-second time limit.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    solve()
    return output.getvalue().strip()

# Provided samples
assert run("3\n5\n15 14 17 42 34\n3\n1 7\n2 15\n4 5\n5\n7 5 3 1 7\n4\n1 7\n5 7\n2 3\n2 2\n7\n19 20 15 12 21 7 11\n4\n1 15\n4 4\n7 12\n5 7\n") == "2 -1 5\n1 5 2 2\n2 6 -1 5", "sample 1"

# Custom cases
assert run("1\n1\n1\n1\n1 1\n") == "1", "single element"
assert run("1\n5\n1 1 1 1 1\n2\n1 1\n3 2\n") == "5 -1", "all ones with k exceeding"
assert run("1\n3\n7 7 7\n3\n1 7\n2 7\n3 7\n") == "3 3 3", "all equal elements"
assert run("1\n4\n1 2 4 8\n2\n1 1\n2 2\n") == "4 2", "powers of two"
Test input Expected output What it validates
`