USACO 2024 January Contest Silver Division - Cowlendar

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can narrow down the subset of values that \(L\) can take as follows: we are only interested in the distinct values of the elements in the array.

We take the first \(4\) distinct values, if there are not at least \(4\), then any \(L\) is a solution. On the other hand, if we have at least \(4\) distinct values, the only candidate values for \(L\) are values that divide the absolute difference between two elements.

These values will be at most equal to \(4000\), so if we make a function that simply checks whether a value is a valid solution for the given array, we can check any \(L\) that we consider a "candidate". The algorithm will run in approximately quadratic complexity after n.

Source code

The source codes in C++ and Python can be seen below.

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

#define int long long

signed main() {
    int N;
    cin >> N;

    vector<int> M;
    set<int> nums;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        nums.insert(x);
    }

    for (int i : nums) {
        M.push_back(i);
    }
    int max_L = (M[0] / 4LL);

    if ((int)M.size() <= 3LL) {
        cout << ((max_L) * (max_L + 1)) / 2;
        return 0;
    } 
    else {
        set<int> difs;
        difs.insert(M[1] - M[0]);
        difs.insert(M[2] - M[0]);
        difs.insert(M[3] - M[0]);
        difs.insert(M[2] - M[1]);
        difs.insert(M[3] - M[1]);
        difs.insert(M[3] - M[2]);

        set<int> factors;
        for (int x : difs) {
            for (int i = 1; i * i <= x; i++) {
                if (x % i == 0LL) {
                    if (i <= max_L) {
                        factors.insert(i);
                    }
                    if ((x / i) <= max_L) {
                        factors.insert((x / i));
                    }
                }
            }
        }
        int ans = 0;

        for (int i : factors) {
            set<int> seen;
            for (int j : M) {
                seen.insert(j % i);
                if ((int)seen.size() > 3LL) {
                    break;
                }
            }

            if ((int)seen.size() <= 3LL) {
                ans += i;
            }
        }

        cout << ans;
        return 0;
    }
}

n = int(input())
a = set([int(i) for i in input().split()])
a = list(a)
if len(a) < 4:
    x = min(a)//4
    print(x*(x+1)//2)
    quit()
candidates = set()
for i in range(4):
    for j in range(i, 4):
        diff = abs(a[i]-a[j])
        for v in range(1, int(diff**(1/2))+1):
            if diff % v == 0:
                candidates.add(v)
                candidates.add(diff//v)
result = 0
for i in candidates:
    if i <= min(a)//4:
        if len(set([j%i for j in a])) <= 3:
            result += i
print(result)