USACO 2023 US Open Contest Bronze Division - Rotate and Shift

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

In short, you want to do a brute force or do some casework which helps you and then you basically try to deduce one of the two approaches where we focus on either each value or think at cyclical shifts.

For a more detailed solution and casework review, I recommend checking this solution out as well.

Source codes

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

#include <iostream>
#include <vector>

using namespace std;

int main() 
{
    int N, K, T;
    cin >> N >> K >> T;

    vector<int> A(K + 1);
    for (int i = 0; i < K; ++i) {
        cin >> A[i];
    }
    A[K] = N; // append the value N to the sequence

    vector<int> ans(N, -1); // initialize the final array with -1

    for (int i = 0; i < K; ++i) 
        for (int j = A[i]; j < A[i + 1]; ++j) 
        {
            int T_prime = T - (j - A[i] + 1);
            int ending_position;
            if (T_prime >= 0) 
            {
                int increase_times = 1 + T_prime / (A[i + 1] - A[i]); // integer division
                ending_position = (j + increase_times * (A[i + 1] - A[i])) % N;
            } 
            else 
            {
                // doesn't move at all
                ending_position = j;
            }

            ans[ending_position] = j;
        }

    for (int i = 0; i < N; ++i) 
    {
        cout << ans[i];
        if (i < N - 1) 
            cout << " ";
    }
    cout << '\n';

    return 0;
}

n, t = map(int, input().split())
cntt = [(0, 0)]
for _ in range(n):
    a, b = map(int, input().split())
    cntt.append((a, b))
ans = 0
rem = 0
printed = 0
for i in range(1, n + 1):
    temp = min(t, cntt[i][0]) - cntt[i - 1][0] - 1
    use = min(rem, temp)
    ans += use
    rem -= use
    if cntt[i][0] > t:
        print(ans)
        printed = 1
        break
    rem += cntt[i][1]
    ans += 1
    rem -= 1
    if cntt[i][0] == t:
        print(ans)
        printed = 1
        break
if printed == 0:
    if cntt[n][0] < t:
        ans += min(rem, t - cntt[n][0])
    print(ans)