Problem D: Array Product Operations

Approach

Given the constraint that |M| ≤ 10⁹, any integer within this range can be decomposed into a product of at most 20 distinct factors. This observation is crucial for solving the problem efficiently.

The strategy involves counting distinct elements in the array. If the number of distinct values exceeds 20, the product will inevitably exceed the valid range (unless zero is introduced by setting one element to zero). Otherwise, we enumerate possible offset values for addition/subtraction operations and record all valid M values that can be formed.

Implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    map<int, int> freq;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        freq[val]++;
    }
    
    vector<pair<int, int>> elements(freq.begin(), freq.end());
    set<int> validM{0};
    const int OFFSET = 4e4, LIMIT = 1e9;
    
    if (elements.size() <= 20) {
        for (auto& [base, _] : elements) {
            for (int delta = base - OFFSET; delta <= base + OFFSET; ++delta) {
                long long product = 1;
                for (auto& [num, count] : elements) {
                    int transformed = num - delta;
                    for (int k = 0; k < count && abs(product) <= LIMIT; ++k) {
                        product *= transformed;
                    }
                    if (abs(product) > LIMIT) break;
                }
                if (abs(product) <= LIMIT) {
                    validM.insert(product);
                }
            }
        }
    }
    
    while (q--) {
        int m;
        cin >> m;
        cout << (validM.count(m) ? "Yes" : "No") << '\n';
    }
    return 0;
}

Problem H: Bit-Constrained Knapsack

Approach

For each bit position where m has a value of 1, we analyze constraints on item weights. Let position i be a bit where m has 1. For any item weight w_j to not exceed m when summed, the i-th bit of w_j must be 0, higher bits must form a subset of m's higher bits, and lower bits are unconstrained.

A key observation emerges: w_j must be a bit-subset of m. This allows us to cover all valid cases and compute the maximum total value efficiently.

Implementation

#include <bits/stdc++.h>
using namespace std;

const int BITS = 30;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n, m;
        cin >> n >> m;
        
        bitset<BITS> mask(m);
        vector<int> values(n);
        vector<bitset<BITS>> weights(n);
        
        long long baseSum = 0;
        for (int i = 0; i < n; ++i) {
            int w;
            cin >> values[i] >> w;
            weights[i] = bitset<BITS>(w);
            
            bool isValid = true;
            for (int b = 0; b < BITS; ++b) {
                if (!mask[b] && weights[i][b]) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) baseSum += values[i];
        }
        
        long long result = baseSum;
        
        for (int b = 0; b < BITS; ++b) {
            if (!mask[b]) continue;
            
            long long currentSum = 0;
            for (int i = 0; i < n; ++i) {
                if (weights[i][b]) continue;
                
                bool compatible = true;
                for (int higher = b + 1; higher < BITS; ++higher) {
                    if (weights[i][higher] && !mask[higher]) {
                        compatible = false;
                        break;
                    }
                }
                if (compatible) currentSum += values[i];
            }
            result = max(result, currentSum);
        }
        
        cout << result << '\n';
    }
    return 0;
}

Problem I: Bertrand Paradox Detection

Approach

The bit-noob generation method produces uniformly distributed coordinates. By analyzing the statistical distribution of input coordinates, we can distinguish between generation methods.

The reference solution examines coordinates where both x and y have absolute values within 70. Theoretically, such coordinates should appear with probability (141×141)/(199×199). By comparing the actual frequency against this expected value with an appropriate threshold, we can determine the generation method.

Implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    int innerCount = 0;
    for (int i = 0; i < n; ++i) {
        int x, y, r;
        cin >> x >> y >> r;
        if (abs(x) <= 70 && abs(y) <= 70) {
            innerCount++;
        }
    }
    
    double expected = 141.0 * 141.0 / (199 * 199) * 1e5;
    
    if (abs(expected - innerCount) > 2000) {
        cout << "buaa-noob\n";
    } else {
        cout << "bit-noob\n";
    }
    return 0;
}

Problem J: Two-Worker Task Scheduling

Approach

Binary search on the maximum allowable distance. For each candidate distance mid, we verify whether both workers can complete all tasks while staying within distance mid of each other.

The verification function maintains a set of valid positions for the idle worker after each task. When transitioning from task i (at position a_i) to task i+1 (at position a_i+1):

• No worker swap: The idle worker stays put. We remove positions from the set that exceed distance mid from a_i+1.
• Worker swap: If |a_i - a_i+1| ≤ mid, the previous worker becomes idle, so we insert a_i into the valid set.

Initial condition requires |x - y| ≤ mid, and the set must remain non-empty throughout.

Implementation

#include <bits/stdc++.h>
using namespace std;

int n, startX, startY;
int tasks[100005];

bool canComplete(int maxDist) {
    if (abs(startX - startY) > maxDist) return false;
    
    set<int> validPositions;
    if (abs(startY - tasks[0]) <= maxDist) validPositions.insert(startY);
    if (abs(startX - tasks[0]) <= maxDist) validPositions.insert(startX);
    
    if (validPositions.empty()) return false;
    
    for (int i = 0; i < n - 1; ++i) {
        bool canSwap = (abs(tasks[i] - tasks[i+1]) <= maxDist);
        
        while (!validPositions.empty() && *validPositions.begin() < tasks[i+1] - maxDist) {
            validPositions.erase(validPositions.begin());
        }
        while (!validPositions.empty() && *validPositions.rbegin() > tasks[i+1] + maxDist) {
            validPositions.erase(prev(validPositions.end()));
        }
        
        if (canSwap) validPositions.insert(tasks[i]);
        if (validPositions.empty()) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> startX >> startY;
    for (int i = 0; i < n; ++i) cin >> tasks[i];
    
    int lo = 0, hi = 1e9, answer;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (canComplete(mid)) {
            answer = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << answer << '\n';
    return 0;
}