USACO 2023 December Contest Bronze Division - Farmer John Actually Farms

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

One initial idea is that some kind of sorting makes sense here as we know the order we seek to have long term and now we need to find the smallest day we achieve this, which can be found using some math.

The important thing to see now is that we don't need to check all \(n^2\) pairs, but only pairs with consecutive \(t\) values. Therefore, all we have to do now is to deal with two cases depending on the growth rates and we are done.

Source codes

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

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

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

    int t;
    cin >> t;

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

        vector<pair<int, pair<int, int> > >v(n+1);
        for(int i = 1; i <= n; i++)
            cin >> v[i].second.first;
        for(int i = 1; i <= n; i++)
            cin >> v[i].second.second;
        for(int i = 1; i <= n; i++)
            cin >> v[i].first, v[i].first = n - v[i].first - 1;

        sort(v.begin() + 1, v.begin() + n + 1);

        int mxD = 0;
        int minbadD = (1<<30);
        bool ok = 1;

        for(int i = 2; i <= n; i++)
        {
            if(v[i].second.first <= v[i-1].second.first)
            {
                if(v[i].second.second > v[i-1].second.second)
                {
                    int rp = (v[i-1].second.first - v[i].second.first + v[i].second.second - v[i-1].second.second) / (v[i].second.second - v[i-1].second.second);
                    mxD = max(mxD, rp);
                }
                else
                    ok = 0;
            }
            else
            {
                if(v[i].second.second < v[i-1].second.second)
                {
                    int rp = (v[i].second.first - v[i-1].second.first + v[i-1].second.second - v[i].second.second - 1) / (v[i-1].second.second - v[i].second.second);
                    minbadD = min(minbadD, rp);
                }
            }
        }
        if(mxD >= minbadD || ok == 0)
            cout << -1 << '\n';
        else
            cout << mxD << '\n';
    }

    return 0;
}

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = list(map(int, input().split()))
    for i in range(n):
        c[i] = n - c[i] - 1
    v = [(c[i], a[i], b[i]) for i in range(n)]
    v.sort()
    mxD = 0
    minbadD = 2**30
    ok = True
    for i in range(1, n):
        prev_a = v[i-1][1]
        curr_a = v[i][1]
        prev_b = v[i-1][2]
        curr_b = v[i][2]
        if curr_a <= prev_a:
            if curr_b > prev_b:
                rp = (prev_a - curr_a + curr_b - prev_b) // (curr_b - prev_b)
                mxD = max(mxD, rp)
            else:
                ok = False
        else:
            if curr_b < prev_b:
                rp = (curr_a - prev_a + prev_b - curr_b - 1) // (prev_b - curr_b)
                minbadD = min(minbadD, rp)
    if mxD >= minbadD or not ok:
        print(-1)
    else:
        print(mxD)