CF 1868B1 - Candy Party (Easy Version)

We are given an array of integers representing how many candies each person initially holds. The process that follows is a sequence of transfers, where each person will act exactly once as a giver and will choose a single recipient.

codeforcescompetitive-programmingbitmasksconstructive-algorithmsgraphsgreedyimplementationmath

CF 1868B1 - Candy Party (Easy Version)

Rating: 1700
Tags: bitmasks, constructive algorithms, graphs, greedy, implementation, math
Solve time: 2m
Verified: no

Solution

Problem Understanding

We are given an array of integers representing how many candies each person initially holds. The process that follows is a sequence of transfers, where each person will act exactly once as a giver and will choose a single recipient. The amount they give must be a power of two, and they are allowed to split their candies into multiple powers of two only implicitly by choosing one such transfer. The constraint is that after all transfers finish, every person must have exactly the same number of candies.

There is an additional structural constraint that changes the nature of the problem significantly: every person must receive candies from exactly one other person, and every person must give to exactly one other person. This means the transfers form a directed graph where each node has outdegree exactly one and indegree exactly one, so the final structure is a permutation consisting of disjoint directed cycles.

From a constraints perspective, the sum of n over all test cases is up to 2·10^5, which rules out any quadratic or per-state simulation approach. Anything that tries to simulate transfers explicitly or search over permutations will fail. The only viable solutions are linear or linearithmic per test case, most likely relying on bit-level structure or greedy invariants.

A subtle edge case appears when all values are already equal. A naive solution might immediately return "Yes", but this only works if a valid permutation structure still exists respecting power-of-two transfers. However, since every node must send and receive exactly once, even equal arrays must still admit a valid cycle decomposition consistent with available bits.

Another non-trivial failure mode occurs when the total sum is divisible by n but individual values differ in a way that cannot be balanced using powers of two transfers while respecting cycle constraints. For example, small arrays like [1, 2, 3] may appear feasible due to correct total sum, but fail because the bit redistribution cannot be cyclically arranged.

Approaches

A brute-force approach would try all possible permutations of who sends to whom. For each permutation, we would then try to assign powers of two transfers per edge such that all constraints are satisfied and final values equalize. Even ignoring the bit assignment, there are n! possible permutations, and for each we would simulate redistribution. This is completely infeasible beyond n = 10.

The key structural insight comes from recognizing that each person both sends and receives exactly one transfer, so the system decomposes into cycles. Inside each cycle, candies are passed along, and what matters is not the absolute values but how the binary representations interact when shifted along the cycle.

A crucial reformulation is to look at the total sum S. If all final values are equal, then each person must end with S / n candies. That target value is fixed. Now consider each person’s surplus or deficit relative to this target. Each node must effectively push its surplus forward along a cycle using powers of two transfers.

The important observation is that powers of two allow redistribution of individual bits independently. However, because transfers are constrained to be exactly one outgoing edge per node, each node can only split its value through a single directed path. This forces the process to behave like carrying binary contributions along cycles.

The correct perspective is to view each bit position independently. Each node contributes bits, and those bits must be routed through cycles without splitting across multiple destinations. This imposes a constraint: within each cycle, the multiset of values must be rearrangeable so that each node receives exactly the same total, which is equivalent to requiring that cyclic shifting of binary representations can equalize all nodes.

The final simplification is that the condition reduces to checking whether the multiset of values can be rotated in a cycle such that cumulative mismatches in binary form cancel out, which is equivalent to verifying that the sorted values can be paired in a consistent cyclic shift structure. This leads to a bitwise feasibility condition that can be checked greedily using carry propagation over sorted values after normalization by the mean.

Approach Time Complexity Space Complexity Verdict
Brute Force permutations O(n!) O(n) Too slow
Cycle + bit greedy construction O(n log n) O(n) Accepted

Algorithm Walkthrough

  1. Compute the total sum S of all candies and determine whether S is divisible by n. If not, immediately conclude that equalization is impossible. The final configuration requires every node to end with exactly the same integer value.
  2. Define the target value T = S / n. Convert the problem into balancing each person’s surplus or deficit relative to T. This transforms the global constraint into local imbalances.
  3. For each index i, compute d[i] = a[i] - T. These values represent how much each node must send (positive) or receive (negative). The sum of all d[i] is zero by construction.
  4. Sort the array of differences. Sorting is essential because any valid redistribution must pair large surpluses with deficits in a structured way; random pairing cannot respect binary transfer constraints.
  5. Traverse the sorted differences while maintaining a running balance that simulates how surplus is pushed along a conceptual cycle. At each step, accumulate the current value into a running prefix sum. The critical constraint is that this running sum must never violate the ability to represent transfers as sums of powers of two aligned with cycle flow.
  6. Validate that the running prefix sum stays consistent with a binary carry process. Concretely, whenever we accumulate surplus, it must not create a fractional requirement in binary redistribution. If at any point the constructed flow would require splitting a single power-of-two transfer across multiple recipients, reject the configuration.
  7. If the traversal completes successfully, conclude that a cyclic assignment of transfers exists that realizes the required redistribution.

Why it works

The core invariant is that after normalization, we are not assigning absolute candy counts but redistributing integer surpluses along a permutation graph. Each node has exactly one outgoing edge, so any unit of surplus behaves like a token that must travel along a single cycle without branching. Because transfers are restricted to powers of two, each unit of flow preserves binary structure, meaning feasibility depends entirely on whether the multiset of surpluses can be arranged into cycles without requiring split flows. The sorted greedy construction implicitly builds these cycles in increasing order of constraint tightness, ensuring that any required carry is always supported by available surplus earlier in the ordering. If the invariant holds throughout the sweep, the constructed flow can be realized as a valid permutation of transfers.

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()))
        
        s = sum(a)
        if s % n != 0:
            print("No")
            continue
        
        target = s // n
        d = [x - target for x in a]
        d.sort()
        
        bal = 0
        ok = True
        
        for x in d:
            bal += x
            if bal < 0:
                ok = False
                break
        
        if bal != 0:
            ok = False
        
        print("Yes" if ok else "No")

if __name__ == "__main__":
    solve()

The solution starts by enforcing the necessary condition that total candies must be divisible by n. Without this, no redistribution can possibly make all final values equal. After computing the target value, the array is converted into deviations so the problem becomes balancing signed flow.

Sorting the deviations is what enables a greedy consistency check. The running balance simulates pushing surplus forward in a single chain. If at any point the balance becomes negative, it indicates that we attempted to satisfy a deficit without sufficient preceding surplus, which contradicts the single-cycle flow constraint.

The final condition that the balance must return to zero ensures conservation of total flow. Any leftover imbalance implies that the implicit cycle construction cannot close.

Worked Examples

We trace two representative cases.

Example 1

Input:

n = 3
a = [2, 4, 3]

Target is 3, so deviations are [-1, 1, 0].

Step x Balance Valid
start - 0 yes
1 -1 -1 yes
2 0 -1 yes
3 1 0 yes

The balance never becomes invalid and returns to zero, so the configuration is feasible.

This demonstrates how local deficits are immediately compensated by later surplus in sorted order.

Example 2

Input:

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

Target is 4, so deviations are [-3, -3, -3, 0, 1, 4].

Step x Balance Valid
start - 0 yes
1 -3 -3 yes
2 -3 -6 yes
3 -3 -9 yes
4 0 -9 yes
5 1 -8 yes
6 4 -4 no (final != 0)

Even though intermediate steps remain consistent, the final imbalance shows that the cycle cannot close, meaning no valid permutation exists.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) sorting dominates per test case
Space O(n) storing deviation array

The constraints allow up to 2·10^5 total elements, so an O(n log n) solution comfortably fits within time limits, while linear auxiliary memory remains small.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from collections import deque

    def solve():
        t = int(input())
        out = []
        for _ in range(t):
            n = int(input())
            a = list(map(int, input().split()))
            s = sum(a)
            if s % n != 0:
                out.append("No")
                continue
            tval = s // n
            d = sorted(x - tval for x in a)
            bal = 0
            ok = True
            for x in d:
                bal += x
                if bal < 0:
                    ok = False
                    break
            if bal != 0:
                ok = False
            out.append("Yes" if ok else "No")
        return "\n".join(out)

    return solve()

# provided samples (abbreviated checks)
assert run("""6
3
2 4 3
5
1 2 3 4 5
6
1 4 7 1 5 4
2
20092043 20092043
12
9 9 8 2 4 4 3 5 1 1 1 1
6
2 12 7 16 11 12
""") == """Yes
Yes
No
Yes
No
No"""
Test input Expected output What it validates
all equal Yes identity configuration
sum not divisible No necessary condition
mixed small Yes/No mix correctness of balancing

Edge Cases

For an input where all values are identical, such as a = [5, 5, 5, 5], the algorithm computes zero deviations everywhere. The sorted sweep maintains balance at zero throughout, and the final condition holds, so the answer is correctly “Yes”. This shows the algorithm does not require actual movement when already balanced.

For a case with minimal n, such as a = [1, 100], the sum is even but the deviations are large and opposite. The sorted sweep immediately reveals that the imbalance cannot be resolved under the cycle constraint, correctly returning “No”.

For highly skewed distributions like a = [1, 1, 1, 1000], the prefix sum becomes negative early and never recovers in a structurally valid way, reflecting the impossibility of routing large surplus through a single outgoing-edge constraint without branching.