Skip to content

[CodeChef] Starters 73 — Minimum OR Path: decide the bits from the top, test each with a reachability scan

Published 5 October 2026

Problem: CodeChef — Minimum OR Path (Starters 73, same round as Find an Integer, difficulty 2502).

You’re given an array \(A\) of \(N\) non-negative integers. From index \(i\) you can move to any \(j\) with \(i \le j \le \min(i + A_i, N)\). The cost of a path from \(1\) to \(N\) is the bitwise OR of every value it visits, including both endpoints. Find the minimum cost, or \(-1\) if \(N\) can’t be reached.

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

Think in bits

Minimizing an OR isn’t like minimizing a sum. One high bit outweighs all the lower bits put together: \(2^b > 2^b - 1 = 2^0 + \dots + 2^{b-1}\). So the best path is the one that avoids the highest bit it can, then the next highest bit given that choice, and so on. That suggests deciding the bits one at a time, from bit \(20\) down to bit \(0\). \(5 \cdot 10^5 < 2^{19}\), so 21 bits is more than enough.

Keep allowed, the bits I’ve already had to accept. At bit \(b\), ask whether a path exists using only values inside the mask

\[\texttt{allowed} \;\cup\; \{0, 1, \dots, b - 1\},\]

which excludes bit \(b\) and every higher bit I’ve already managed to avoid. Lower bits are still undecided, so they’re all allowed for now.

  • If a path exists, bit \(b\) can be avoided. Leave it out of allowed.
  • If not, every path that respects the higher decisions uses bit \(b\), so add it to allowed.

An index is usable under a mask when a[i] & mask == a[i], meaning its value has no bit outside the mask. That includes indices \(1\) and \(N\), which every path visits. If either endpoint has bit \(b\), the test fails on its own and the bit is forced.

The check: one forward scan

Given a mask, can I get from \(1\) to \(N\) stepping only on usable indices? From \(i\) I can land on any index in \([i, i + A_i]\), so the set of positions I can land on is always a prefix. One number describes it: reach, the farthest position any usable, reachable index can jump to.

Scan left to right. If \(i >\) reach, nothing can land on \(i\) and \(N\) is unreachable. Otherwise \(i\) is reachable, and if it’s usable it extends reach to \(\max(\texttt{reach}, i + A_i)\). An unusable index can still be landed on in this scan, but it can’t be jumped from, which is the same as never stepping on it. The scan is \(O(N)\), so the whole algorithm is \(O(21 \cdot N)\).

My first plan scanned backwards from \(N\) and kept the leftmost index that can reach the end. That works too, but the forward version is shorter.

Where I went wrong

OR-ing what’s left. My first idea kept a list of indices that survived each bit’s filter, and at the end OR-ed all their values together. That overcounts. The surviving indices are everything that could be on a valid path, not the indices of a single path, so the OR can pick up bits from indices that no single path needs together.

The answer is allowed itself. Each bit in it was forced: no path avoids it given the bits above. And the last test that passed (or a final check(a, allowed)) proves some path uses only bits in allowed. A path whose cost is inside allowed and contains every forced bit costs exactly allowed.

Two bugs in the first draft. The endpoint check compared a[1] where it should have used a[0]. And allowed was never updated when a test failed, so every later test ran with too small a mask.

The \(-1\) case. If \(N\) is unreachable, every test fails and allowed ends up as all 21 bits. That mask fits every value, so the final check(a, allowed) fails only when \(N\) really is out of reach. Then print \(-1\).

The pattern: bitwise_greedy_reachability

This shape keeps coming back:

  1. The objective is an OR (or an AND, or an XOR basis value) to minimize or maximize.
  2. Go from the highest bit down, keeping the bits already decided.
  3. For each bit, build a mask that bans it on top of the earlier decisions, and ask “is the structure still feasible using only elements inside the mask?”
  4. Feasibility is a cheap linear check: reachability in an array or a graph, connectivity with DSU, or a greedy partition count.

The answer is whatever the greedy couldn’t remove. Total cost is \((\text{bits}) \times (\text{check})\).

Code

Checked against a brute force over (index, OR so far) states on 30,000 random arrays with \(N \le 8\). On the samples it prints \(1\), \(3\) and \(-1\).

# mask: has allowed bits
def check(a, mask):

    if (a[0] & mask) != a[0]:
        return False
    if (a[-1] & mask) != a[-1]:
        return False

    reach = 1+a[0]
    n = len(a)
    for i in range(1, n):
        if i+1 > reach:
            return False

        if (a[i] & mask) == a[i]:
            reach = max(reach, i+1+a[i])

    return True


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

    allowed = 0
    for bit in range(20, -1, -1):
        if check(a, allowed + (1<<bit)-1):
            continue
        else:
            allowed += 1<<bit

    if check(a, allowed):
        print(allowed)
    else:
        print(-1)


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

reach uses 1-indexed positions: index i is position i+1, so position i+1 can jump to i+1+a[i]. allowed + (1<<bit)-1 is the mask from above. Bits in allowed are all above bit, so the + acts as an OR.