Dominater round after so long

korbo lorbo jeetbo re

Contest starts in ~30min.

hope to have some fun with the problems .

is the problem blocktree , perfect subset sum ?

i am sorry for the weak samples on Matching Arrays.

I expected the problem to be much easier than it ended up being. The correct decision was indeed a stronger sample.

In the problem SUMBYOR , the test cases are weak as the number of distinct possible numbers are close to 32000. But i have seen accepted codes with time complexity as big as O(32000^2). The code given below is accepted.

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

#define int long long

const int MAX_N = 200000;

int getBitMask(int num) {
    int mask = 0;
    for (int i = 0; i<30; i++) {
        if (num & (1LL << i)) {
            mask |= (1 << i);
        }
    }
    return mask;
}

void solve() {
    int n; cin >> n;
    map<int, int> freq;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        int mask = getBitMask(a[i]);
        freq[mask]++;
    }
    vector<pair<int, int>> masks(freq.begin(), freq.end());

    int sum=0, pref=0, ct=0;
    for (int i = 0; i < masks.size(); i++) {
        int mski = masks[i].first;
        int cti = masks[i].second;
        sum += (cti*(cti-1)/2)*2;
        for(int j = i + 1; j < masks.size(); j++) {
            int maskj = masks[j].first;
            int ctj = masks[j].second;
            if ((mski & maskj) == 0) {
                sum += cti * ctj * 1;
            } else {
                sum += cti * ctj * 2;
            }
        }
    }
    cout<<sum<<endl;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

Great contest, bricked Sum By Or but good set of problems.

Why constraints of $$$blocks \ on \ tree$$$ is less? For checker? But still checker can be done in $$$O(n)$$$