USACO 2023 January Contest Silver Division - Moo Route

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

You go and make them all the same value then in order to progress you make all the next ones one when you are left with increasing values you just go and make them all one value in order from right to left.

We will use a two pointers approach to process these value.

Source code

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

#include <iostream>
using namespace std;
int v[200005];
int main() {
    int n, sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[2 * i - 1];
        sum += v[2 * i - 1];
    }
    int st = -1, dr = 2 * n + 1, cnt = 0, i = 0;
    char dir = 'R';
    while (cnt < sum) {
        if (dir == 'R') {
            if (v[i + 1] == 1) {
                if (st + 1 == i) {
                    v[i + 1]--;
                    cout << "R";
                    st = i + 1;
                    i += 2;
                } 
                else {
                    dir = 'L';
                    cnt--;
                }
            } 
            else if (v[i + 1] == 0) {
                dir = 'L';
                cnt--;
            } 
            else {
                v[i + 1]--;
                cout << "R";
                i += 2;
            }
        } 
        else {
            if (v[i - 1] == 1) {
                if (dr - 1 == i) {
                    v[i - 1]--;
                    cout << "L";
                    dr = i - 1;
                    i -= 2;
                } 
                else {
                    dir = 'R';
                    cnt--;
                }
            } 
            else 
                if (v[i - 1] == 0) {
                    dir = 'R';
                    cnt--;
                } 
                else {
                    v[i - 1]--;
                    cout << "L";
                    i -= 2;
                }
        }
        cnt++;
    }
    return 0;
}