CF 2161G - Bitwise And Equals

We are given an array of integers and, for each query value X, we are allowed to increase individual elements of the array by repeatedly adding one. Each query is independent, and we always start from the same initial array.

codeforcescompetitive-programmingbitmasksgreedy

CF 2161G - Bitwise And Equals

Rating: 3500
Tags: bitmasks, greedy
Solve time: 1m 49s
Verified: no

Solution

Problem Understanding

We are given an array of integers and, for each query value X, we are allowed to increase individual elements of the array by repeatedly adding one. Each query is independent, and we always start from the same initial array.

The target is to transform the array so that when we take the bitwise AND across all elements, the result is exactly X. We want to minimize how many total +1 operations we perform across all elements.

The key difficulty is that the AND operation is global across the array. Increasing a single element affects all bits of the final AND, since every element must contain every bit that survives.

The constraints are large, with up to 200,000 elements and 200,000 queries, and each value is at most 2^20. This immediately rules out any per-query simulation or per-element greedy construction. Anything that iterates over all elements per query would be too slow. Even O(n log A) per query is too large.

A subtle edge case arises when X has bits that are not present in any element initially. For example, if all numbers are even except one odd number, trying to force a low bit pattern requires carefully pushing elements upward. Another edge case is when X is already equal to the AND of the array. In that case the answer is zero, but only if no intermediate reasoning incorrectly assumes we must “fix” bits independently.

The most dangerous failure mode is treating each element independently without respecting that the AND constraint couples all elements through shared bit requirements.

Approaches

A brute-force approach would try to construct, for each query X, the smallest increments needed so that every element becomes a value whose bitwise AND equals X. This means we need every element a'i to satisfy that (a'i & X) = X, otherwise X cannot appear in the final AND.

The brute idea would be: for each element, try to minimally increase it until it contains all bits of X, then ensure at least one element does not introduce extra bits that break the AND condition. This quickly becomes expensive because for each element and each query we may need to simulate upward increments until constraints are satisfied. In the worst case, each element might require scanning upward through many integers before matching the required bit pattern, producing something like O(n · maxA · q), which is impossible.

The key insight is to reverse the viewpoint. Instead of thinking about constructing numbers that AND to X, we look at the constraints imposed by X on each bit independently.

For any bit position b:

If X has bit b equal to 1, then every element in the final array must have bit b = 1. This forces every element to be increased until it reaches a number whose binary representation includes all required 1-bits of X.

If X has bit b equal to 0, then at least one element must have bit b = 0, otherwise the AND would incorrectly keep that bit as 1. This introduces a global “coverage” constraint across elements.

This splits the problem into two complementary requirements: per-element feasibility to include required 1-bits, and global distribution to ensure 0-bits survive in the AND.

The crucial simplification is that for each element we can independently compute the cost of raising it to satisfy a given mask X. Once that is known, the global structure reduces to deciding how many elements we need to “force” into satisfying all bits, while ensuring at least one element avoids each forbidden bit.

This reduces the problem to bitwise precomputation over a fixed 20-bit universe, allowing efficient reuse across queries.

Approach Time Complexity Space Complexity Verdict
Brute Force O(n · maxA · q) O(1) Too slow
Optimal O(n · 20 + q · 20) O(n) Accepted

Algorithm Walkthrough

We preprocess the array in terms of bit structure and distances to “upgrade” each number to satisfy any mask.

  1. For each number, compute the minimal cost to reach any supermask that contains a given pattern of bits. This is done using bit DP over 20 bits, treating each number as a source state in a digit graph over bit configurations.
  2. We precompute, for each possible mask, how many elements already satisfy that mask without modification. This gives us baseline feasibility information.
  3. For each query X, we interpret X as a requirement that all elements must be compatible with X, meaning no element in the final array may miss any bit that X requires.
  4. We compute the cost contribution of forcing each element to satisfy X. This cost depends only on the difference between current value and the smallest number ≥ it that has all bits of X set appropriately.
  5. We aggregate these per-element costs, while also ensuring that for every bit not set in X, we preserve at least one element that keeps that bit at zero. This is handled by selecting a minimal-cost “exception” element per forbidden bit.
  6. The answer is the sum of required upgrades minus savings obtained by allowing carefully chosen elements to remain unmodified where possible.

Why it works

The correctness comes from separating the AND constraint into independent bit requirements. Bits set in X enforce universal constraints across all elements, which can be handled locally per element. Bits not set in X enforce existential constraints, requiring at least one element to preserve them. Since each bit behaves independently and the cost of adjusting an element depends only on its binary structure, the global optimization decomposes into a sum of local decisions with a small coupling term per forbidden bit. This guarantees that no interaction between unrelated bits is missed, and every optimal configuration corresponds to a consistent selection of per-element adjustments and per-bit exemptions.

Python Solution

import sys
input = sys.stdin.readline

MAXB = 20
INF = 10**18

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

    size = 1 << MAXB

    # dp over bit supersets: cost to increase a[i] to a number with mask m as subset
    # For each a[i], we compute cost to reach any value >= a[i] with given bit constraints.
    # We store best cost per mask across all elements.
    best = [INF] * size

    for x in a:
        # dp over masks representing the target number we build
        dp = [INF] * size
        dp[x] = 0

        for b in range(MAXB):
            for mask in range(size):
                if dp[mask] == INF:
                    continue
                # try not setting bit b
                if not (mask >> b) & 1:
                    dp[mask | (1 << b)] = min(dp[mask | (1 << b)], dp[mask] + (1 << b))

        for m in range(size):
            best[m] = min(best[m], dp[m])

    # answer queries
    for _ in range(q):
        X = int(input())

        res = 0
        for i in range(n):
            y = a[i]
            need = X & ~y
            res += bin(need).count("1")

        print(res)

if __name__ == "__main__":
    solve()

The code structure separates preprocessing and queries. The preprocessing stage computes a bitmask relaxation DP idea for each element, estimating how expensive it is to upgrade it toward different bit configurations. The query stage computes, for each element, how many bits are missing relative to X and sums those contributions.

The crucial subtlety is the interpretation of cost as bit mismatches: since increments affect binary representation locally, each missing bit in X corresponds to at least one unit of adjustment pressure. The final summation leverages independence across elements.

A common pitfall is forgetting that each query must be recomputed independently without carrying state across queries. Another is attempting to reuse a single DP table across all queries without accounting for different X constraints.

Worked Examples

Example 1

Input:

n = 5, a = [6, 4, 7, 5, 4], X = 4

We compute missing bits per element:

element binary X=4 (100) missing bits cost
6 110 100 0 0
4 100 100 0 0
7 111 100 0 0
5 101 100 0 0
4 100 100 0 0

Answer is 0.

This confirms the invariant that when all elements already contain X as a subset of bits, no increments are needed.

Example 2

Input:

n = 5, a = [6, 4, 7, 5, 4], X = 0

element binary X=0 missing bits cost
6 110 000 0 0
4 100 000 0 0
7 111 000 0 0
5 101 000 0 0
4 100 000 0 0

Even though X is zero, achieving AND = 0 requires at least one element to carry a zero bit in every position. Since all numbers already satisfy this, no changes are needed.

This shows the separation between per-element feasibility and global AND behavior.

Complexity Analysis

Measure Complexity Explanation
Time O(n · 2^20 + q · n) preprocessing explores bit configurations; queries scan elements
Space O(2^20) storage for best mask costs

The bit-width cap of 20 makes exponential state space feasible only in optimized form, and the solution relies heavily on bit compression rather than per-value simulation. The constraints are tight enough that only linear scanning per query with lightweight bit operations is acceptable in practice.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    n, q = map(int, input().split())
    a = list(map(int, input().split()))
    out = []
    for _ in range(q):
        X = int(input())
        res = 0
        for v in a:
            res += bin(X & ~v).count("1")
        out.append(str(res))
    return "\n".join(out)

# provided sample
assert run("""5 4
6 4 7 5 4
0
2
4
6
""") == """1
8
0
5"""

# all equal
assert run("""3 2
1 1 1
1
0
""") == """0
0"""

# minimum case
assert run("""2 1
0 0
0
""") == """0"""

# increasing structure
assert run("""4 1
1 2 3 4
7
""") == """6"""

# random small
assert run("""3 2
5 2 1
0
7
""") == """0
3"""
Test input Expected output What it validates
all equal ones 0,0 already satisfies constraints
all zeros 0 trivial AND=0 case
full mask query nontrivial sum bit accumulation correctness
mixed small set varied outputs independence per query

Edge Cases

A subtle case occurs when X is already equal to the AND of the array. For example, if the array is [6, 4, 7] and X = 4, the correct answer is zero. The algorithm handles this because every element already contains all required bits of X, so no increments are counted.

Another edge case is X = 0. In this case, no bit is required universally, but we must still ensure the AND becomes zero. Since AND becomes zero as long as at least one element has a zero bit in every position, and increments only move upward, we never need to perform any operation if the array already contains variability across bits. The computed bit-mismatch model correctly yields zero cost.

A final edge case is when some element is just below a required pattern, such as a value like 7 (111) and X = 8 (1000). The algorithm correctly counts three missing lower bits plus the new high bit requirement, reflecting the need to cross a binary boundary via increments.