ICPC-ZU Round 2 Level 1 Contest 5 25-26

We are given 4 integers representing the side lengths. A valid square has all 4 sides equal, so we just check if all values are the same.

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while(t--){
        long long a, b, c, d;
        cin >> a >> b >> c >> d;
        if(a == b && b == c && c == d)
            cout << "yes\n";
        else
            cout << "no\n";
    }
}

Sort the array. For each query value x, use binary search to find how many elements are <= x. Since the array is sorted, the answer is simply the index of the last element that is <= x.

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<long long> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());

    while(m--){
        long long x;
        cin >> x;
        // upper_bound gives iterator past last element <= x
        cout << (upper_bound(a.begin(), a.end(), x) - a.begin()) << ' ';
    }
}

We want to count pairs (i, j) such that i * j = x, where 1 <= i, j <= n. We iterate over all possible values of i from 1 to n. If x is divisible by i and the quotient x/i is also in range [1, n], then (i, x/i) is a valid pair. Each such i contributes one valid pair.

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, x;
    cin >> n >> x;

    int count = 0;
    for(long long i = 1; i <= n; i++){
        if(x % i == 0 && x / i >= 1 && x / i <= n)
            count++;
    }

    cout << count << "\n";
}

The aliquot sum s(n) is the sum of all proper divisors of n (all divisors except n itself). With T and n up to 10^6, we precompute s(n) for all n using a sieve approach: for each i, add i to s[j] for every multiple j = 2i, 3i, ... This runs in O(N log N). Then each query is answered in O(1).

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    const int MAXN = 1e6 + 1;
    vector<long long> s(MAXN, 0);

    for(int i = 1; i < MAXN; i++)
        for(int j = 2 * i; j < MAXN; j += i)
            s[j] += i;

    int t;
    cin >> t;

    while(t--){
        int n;
        cin >> n;
        if(s[n] > n)      cout << "abundant\n";
        else if(s[n] < n) cout << "deficient\n";
        else              cout << "perfect\n";
    }
}

A number d divides all elements in the array if and only if d divides their GCD. So we compute the GCD of the entire array, then count the number of divisors of that GCD. We count divisors in O(sqrt(GCD)) by iterating up to the square root and checking each factor pair.

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    long long g = 0;
    for(int i = 0; i < n; i++){
        long long a;
        cin >> a;
        g = __gcd(g, a);
    }

    int res = 0;
    for(long long i = 1; i * i <= g; i++){
        if(g % i == 0){
            res++;
            if(i != g / i) res++;
        }
    }

    cout << res << "\n";
}

We want two indices i < j such that gcd(a[i], a[j]) == 1 and i + j is maximized. Since values are bounded by 1000, we only care about the last occurrence of each value. We store the last position of every distinct value, then try all pairs of values (v1, v2) and check if gcd(v1, v2) == 1, tracking the maximum sum of their last positions. The loop runs at most 1000 * 1000 = 10^6 iterations.

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

const int MAX_A = 1001;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

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

        vector<int> last(MAX_A, -1);
        for(int i = 1; i <= n; i++){
            int x;
            cin >> x;
            last[x] = i;
        }

        int ans = -1;
        for(int i = 1; i < MAX_A; i++){
            if(last[i] == -1) continue;
            for(int j = 1; j < MAX_A; j++){
                if(last[j] == -1) continue;
                if(__gcd(i, j) == 1)
                    ans = max(ans, last[i] + last[j]);
            }
        }

        cout << ans << '\n';
    }
}

We count pairs (i, j) with i < j such that l <= a[i] + a[j] <= r. It is easier to count the complement: pairs whose sum is > r, plus pairs whose sum is < l, then subtract from the total number of pairs C(n,2). After sorting, both counts can be done in O(n) using the two-pointer technique.

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--){
        long long n, l, r;
        cin >> n >> l >> r;

        vector<long long> v(n);
        for(int i = 0; i < n; i++) cin >> v[i];
        sort(v.begin(), v.end());

        long long bad = 0;
        long long i = 0, j = n - 1;

        // count pairs with sum > r
        while(i < j){
            if(v[i] + v[j] > r){ bad += j - i; j--; }
            else i++;
        }

        i = 0; j = n - 1;

        // count pairs with sum < l
        while(i < j){
            if(v[i] + v[j] < l){ bad += j - i; i++; }
            else j--;
        }

        cout << (n * (n - 1)) / 2 - bad << '\n';
    }
}