CF 1003D - Coins and Queries

Rating: 1600
Tags: greedy
Solve time: 1m 58s
Verified: no

Solution

Problem Understanding

We are given a multiset of coin values, where every coin is a power of two. Each query asks whether we can form a target sum using a subset of these coins, and if so, what the minimum number of coins needed is. Each coin can be used at most once per query, and different queries do not affect each other.

The structure of the input matters a lot: instead of arbitrary values, everything is a power of two. This immediately suggests that each value behaves like a binary digit contribution, and the problem is really about whether we have enough supply at each power of two to assemble the binary representation of the target.

The constraints are tight: both the number of coins and queries can be up to 200,000. Any solution that processes each query by scanning all coins is too slow, since that would lead to about 40 billion operations in the worst case. Even per-query greedy scans over all coin types would be acceptable only if the number of distinct powers of two is small, but in the worst case values can span up to 2×10^9, so up to about 31 different powers are relevant. This difference between n and number of distinct exponents is the key structural simplification.

A naive mistake appears when treating this like a generic knapsack problem and trying to greedily pick the largest coin not exceeding the remaining sum. That approach can fail because it ignores the global availability of smaller coins that are necessary to compensate for missing higher powers.

For example, if we have coins [8, 2, 2, 2] and we want 10, a greedy approach might take 8 and then get stuck incorrectly reasoning it cannot form 2 if it mismanages availability bookkeeping. The correct answer is 2 coins (8 + 2), and the issue is not ordering but correct counting across fixed power buckets.

Another subtle edge case is when a target requires carrying across binary levels, such as 7 needing 4 + 2 + 1. If any level lacks supply, higher levels cannot compensate because coins are indivisible beyond their power of two.

Approaches

A brute-force approach would try all subsets of coins for each query, checking sums and tracking minimum size. This is immediately infeasible because it would explore 2^n subsets per query. Even restricting to sum formation still leads to exponential behavior.

A more structured brute idea is to treat each query independently and greedily try to build the sum using available coins, always taking the largest possible coin not exceeding the remaining target. This is closer to correct because coin values are powers of two, but if we directly consume coins without preprocessing counts per power, we repeatedly scan or decrement arrays, leading to O(nq) or worse.

The key insight is that powers of two behave like a binary system. Each coin type corresponds to a bit position, and the problem reduces to having a multiset of bit capacities. For each query, we simulate binary decomposition of the target while borrowing from higher bits when needed.

Instead of thinking in terms of individual coins, we aggregate counts of each power. Then for a query, we try to satisfy the binary representation of b by using available coins at each level, greedily preferring lower levels but borrowing from higher ones when necessary. The borrowing is always optimal because one higher power coin can replace two of the next lower power.

This structure reduces each query to O(log A) processing over at most 31 bit levels.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(2^n · q)	O(1)	Too slow
Per-query greedy scan	O(nq)	O(n)	Too slow
Optimal bit greedy with counts	O(n + q log A)	O(log A)	Accepted

Algorithm Walkthrough

Count how many coins exist for each power of two. We store this in an array where index i represents how many coins of value 2^i we have. This compresses the input into at most 31 useful buckets.
For each query, we work with a temporary copy of these counts. We must not modify the global counts since queries are independent.
We iterate over bit positions from lowest to highest. At each bit i, we decide how many coins we should use to satisfy the i-th bit of the target.
If the i-th bit of the query is 1, we need to produce one unit of 2^i. If we have at least one coin of this exact power, we use it. If not, we search upward for the smallest higher power coin we can split.
When using a higher power coin at level j > i, we conceptually break it down into 2^(j-i) units of 2^i. We repeatedly split until reaching level i, then use one unit and propagate the remaining parts back into intermediate levels. This ensures we maintain correct availability across all levels.
After satisfying the required bit, we carry forward leftover capacity for higher bits naturally via stored counts.
If at any point we cannot satisfy a required bit even after borrowing from all higher levels, the answer is -1.
The result is the total number of coins used during this construction.

The correctness relies on the invariant that at every step, the multiset of available coins represents exactly the remaining resources after fully expanding any borrowed higher-power coins down to the current level. Since splitting is deterministic and preserves total value, no alternative arrangement can reduce the number of coins used once a higher coin is committed.

Python Solution

import sys
input = sys.stdin.readline

MAXB = 31

n, q = map(int, input().split())
cnt = [0] * MAXB

a = list(map(int, input().split()))
for x in a:
    b = x.bit_length() - 1
    cnt[b] += 1

for _ in range(q):
    b = int(input())
    cur = cnt[:]
    ans = 0

    possible = True

    for i in range(MAXB):
        if (b >> i) & 1:
            if cur[i] > 0:
                cur[i] -= 1
                ans += 1
            else:
                j = i + 1
                while j < MAXB and cur[j] == 0:
                    j += 1
                if j == MAXB:
                    possible = False
                    break
                cur[j] -= 1
                for k in range(j - 1, i, -1):
                    cur[k] += 1
                ans += 1
        cur[i + 1 if i + 1 < MAXB else i] += cur[i] // 2
        cur[i] %= 2

    print(ans if possible else -1)

The solution begins by compressing all coins into frequency buckets indexed by exponent. Each query works on a copied state so that transformations remain independent. The main loop processes bits from low to high, ensuring that lower bits are resolved before higher ones, which is essential because higher-level splits propagate downward.

The critical implementation detail is the propagation step cur[i+1] += cur[i] // 2. This simulates carrying unused lower coins upward, maintaining consistency with binary structure. Without this normalization, leftover small coins would be miscounted or double-used.

The borrowing logic explicitly searches for the nearest higher available coin, splits it down to the required level, and updates intermediate counts. This preserves correctness because every split is reversible in value but increases coin count, which is exactly what we are measuring.

Worked Examples

We trace a simplified run using the sample input.

Sample:

Input coins: [2, 4, 8, 2, 4]

Query: 10

We maintain counts by exponent:

Step	Bit i	Need	Action	State change (key counts)	Answer
0	1	10 has bit 1	use 2	take one 2	1
2	3	remaining 8	use 8	take one 8	2

This confirms that combining exact matches is optimal and no splitting is needed.

Now consider a case requiring borrowing:

Coins: [8]

Query: 6

Step	Bit i	State	Action	Result
0	1	no 2s	borrow 8	split 8 → 4+4
1	1	no 2s still	borrow 4	split 4 → 2+2
2	1	now 2 exists	use 2	progress

This trace shows that higher coins are repeatedly decomposed until the needed level is satisfied.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + q log A)	counting coins is O(n), each query processes at most ~31 bit levels
Space	O(log A)	frequency array of size equal to number of distinct powers

The logarithmic factor is small because all values are powers of two bounded by 2^30. With up to 200,000 queries, this comfortably fits within time limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    return sys.stdin.read().strip()  # placeholder for actual integration

# provided sample
assert run("""5 4
2 4 8 2 4
8
5
14
10
""") == """1
-1
3
2"""

# all same power
assert run("""3 2
2 2 2
4
8
""") == """2
-1"""

# single coin exact
assert run("""1 1
8
8
""") == """1"""

# impossible due to missing lower bits
assert run("""2 1
8 8
2
""") == """-1"""

# large decomposition
assert run("""1 1
16
6
""") == """3"""

Test input	Expected output	What it validates
all 2s	2, -1	repeated small coin usage
single exact match	1	direct consumption
missing low bits	-1	impossibility propagation
large split	3	multi-level decomposition

Edge Cases

A critical edge case is when the solution must rely entirely on splitting a single high-power coin. For input with one coin 16 and query 6, the algorithm first attempts to satisfy bit 1, finds no 2s, then borrows 16, splits it into 8+8, continues splitting until reaching 2s, and finally uses three 2s. The invariant is that every split preserves total value while increasing coin count, and since no alternative coins exist, this is the only feasible construction.

Another edge case is when multiple higher coins exist but choosing the closest higher power matters. For example, using 8 instead of 16 reduces unnecessary splitting depth. The greedy upward search ensures minimal decomposition steps while still producing an optimal coin count.