USACO 2022 December Contest Silver Division - Circular Barn

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

This is a casework problem where the solution depends on primality and parity.

If the number is prime, turns is just \(1\), If number is even, turns is divided by \(2\) as by Goldbach's conjecture if FJ doesnt decrease by 2 Nhoj will automatically win.

If number is odd, realize that player wants to get opponent to \(0\) mod \(4\) as fast as possible, as from there whatever opponents moves, they can bring back the number to \(0\) mod \(4\), and eventually get to \(0\) through this proceess. So if odd, turns is number of turns to largest prime \(p\) so \(p-a_i=0\) (mod 4) i.e. \(p=a_i\) (mod 4)

Source code

The source code in C++ can be seen below.

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll long long

using namespace std;

const int NMAX = 5 * 1e6;
vector<bool> sieve(NMAX + 1, true);
vector<vector<int>> primemax(4, vector<int>(NMAX + 1));

void gen() {
    for (int i = 2; i * i <= NMAX; ++i) {
        if (sieve[i])
            for (int j = 2 * i; j <= NMAX; j += i) sieve[j] = false;
    }

    // biggest primes modulo 4
    for (int i = 1; i < NMAX; ++i) {
        for (int j = 0; j < 4; ++j) primemax[j][i] = primemax[j][i - 1];
        if (sieve[i]) primemax[i % 4][i] = i;
    }
}

int t;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    gen();
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        vector<ll> a(n);
        for (auto& it : a) cin >> it;

        ll farmerLose = LLONG_MAX, farmerWin = LLONG_MAX;

        for (int i = 0; i < n; ++i) {
            if (sieve[a[i]]) {  // prime = instant win
                farmerWin = 1;
                break;
            }

            if (a[i] % 4 == 0) {  // nhoj wins for 4k
                farmerLose = min(farmerLose, a[i] / 4 * n + i);
                continue;
            }

            if (a[i] % 2 == 0) {  // john wins for 4k+2
                farmerWin = min(farmerWin, a[i] / 4 * n + i);
                continue;
            }

            // odd, john chooses the greatest prime
            farmerWin = min(farmerWin, 1LL * (a[i] - primemax[a[i] % 4][a[i]]) / 4 * n + i);
        }

        cout << ((farmerWin <= farmerLose) ? "Farmer John\n" : "Farmer Nhoj\n");
    }
    return 0;
}