Codeforces 1869D Candy Party

题目来自 Codeforces Round #896 (Div.2) D-1。link

  This article provides a feasible solution to a certain competitive programming problem.   If you have better solutions, feel free to share with me!

Problem Description

\(n\) 个人，第 \(i\) 个人有 \(a_i\) 个糖果。按照某种顺序，每个人依次进行如下操作：选择某个整数 \(p\) (\(1\leq p\leq n\)) 与非负整数 \(x\)，并将自己的 \(2^x\) 个糖果给第 \(p\) 个人。整个过程遵循以下限制：

• 若轮到第 \(i\) 个人时此人有 \(a_i\) 个糖果，则其选择的 \(x\) 必须满足 \(2^x\leq a_i\)。[*]
• 第 \(i\) 个人选择的 \(p\neq i\) (不能自己给自己糖果)。[*]
• One can receive candies from exactly one person.

是否存在一种 swap candies 的方式，使得最终 \(n\) 个人拥有的糖果数量相同。

Tutorial

首先，若能均分糖果，最后每个人拥有的糖果数量 \(s=(\sum a_i)/n\).

根据给出的限制，不难得出每个人一定会送出一次糖果且收到一次糖果。那么有对于第 \(i\) 个人，一定有 \(s-a_i=2^{y_i}-2^{x_i}\)。而限制 [*] 实际上并不会产生任何影响，详见 tutorial。

令 \(k_i=|s-a_i|\)，问题转化为对于每个 \(k_i\)，判定方程 \(k_i=2^{y_i}-2^{x_i}\) 解的存在性。若存在，找出一组解 \(y_i, x_i\)。将 \(y_i\) 加入集合 \(\{\rm{Received}\}\)，\(x_i\) 加入集合 \(\{\rm{Sent}\}\)；若最后 \(\{\rm{Received}\}=\{\rm{Sent}\}\)，输出 True。

这个结论很 intuitive。简单的证明：一个 swap 关系代表着同一个 \(x\) 同时被加入两个集合。

下面来讨论如何解方程 \(k=2^y-2^x\). 从二进制的角度看，该方程要么有唯一解，要么无解。其中：

• 一个二次幂为 \(\rm{lowbit(k)}\)，其对应的解为 \(\log_2{(\rm{lowbit(k))}}\)。(具体是 \(x\) 还是 \(y\) 取决于 \(s\) 与 \(a_i\) 的大小关系)
• 另一个二次幂为 \(k+{\rm{lowbit(k)}}\)。若这个值并不是二次幂，说明该方程无解。

举例来说，\(6=110_2=2^x-2^y\).

• \(y=\log(\rm{lowbit(110_2)})=\log{(10_2)}=\log(2)=1\).
• \(x=\log(6+\rm{lowbit(110_2)})=\log(6+2)=\log(8)=3\).

因此 \(6=2^3-2^1\)，我们由此得到方程的解 \(x=3, y=1\)。

Code Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 2e5 + 10;

long long a[MAX_N];

inline long long lowbit(long long k) { return k & -k; }

bool solved(long long s, int n) {
    vector<long long> REC, SEN;
    for (int i = 1; i <= n; ++i) {
        long long k = abs(a[i] - s);
        if (k == 0) continue;
        long long powFir = lowbit(k), powSec = k + lowbit(k);
        if (powSec != lowbit(powSec)) {     // powSec is not a power of 2
            return false;
        }
        if (a[i] < s) {     // receive > sent
            REC.push_back(powSec);
            SEN.push_back(powFir);
        } else {            // sent > receive
            REC.push_back(powFir);
            SEN.push_back(powSec);
        }
    }
    sort(REC.begin(), REC.end());
    sort(SEN.begin(), SEN.end());
    for (int i = 0; i < REC.size(); ++i) {
        if (REC[i] != SEN[i])   return false;
    }
    return true;
}

int main() {

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;

        long long sum = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
            sum += a[i];
        }

        if (sum % n != 0) {
            cout << "No" << endl;
            continue;
        }
        long long s = sum / n;
        if (solved(s, n)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

Reference

One_JuRuo's Blog.