USACO 2016 January Contest Bronze Division - Mowing the Field

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can solve this division by division. First, we can figure out how many new people joined the contest to see how many promoted from bronze to silver. Similarly, we can do the same for silver->gold and gold->platinum.

Source codes

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

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

int main()
{
    ifstream cin("mowing.in");
    ofstream cout("mowing.out");

    int n;
    cin >> n;

    map<pair<int, int>, int> mp;
    int t = 1;
    int x = 0, y = 0;
    int ans = 100000;
    mp[{x, y}] = t;
    for(int i = 1; i <= n; i++)
    {
        char c;
        int tt;
        cin >> c >> tt;
        while(tt)
        {
            t++;
            x += (c == 'S') - (c == 'N');
            y += (c == 'E') - (c == 'W');
            if(mp.find({x, y}) != mp.end())
                ans = min(ans, t - mp[{x, y}]);
            mp[{x, y}] = t;
            tt--;
        }
    }
    if(ans == 100000)
        ans = -1;
    cout << ans;
    return 0;
}

with open("mowing.in", "r") as fin:
    n = int(fin.readline().strip())
    mp = {} # dictionary for pairs
    t = 1
    x = 0
    y = 0
    ans = 100000
    mp[(x, y)] = t
    for _ in range(n):
        parts = fin.readline().split()
        c = parts[0]
        tt = int(parts[1])
        while tt:
            t += 1
            x += (1 if c == 'S' else 0) - (1 if c == 'N' else 0)
            y += (1 if c == 'E' else 0) - (1 if c == 'W' else 0)
            if (x, y) in mp:
                ans = min(ans, t - mp[(x, y)])
            mp[(x, y)] = t
            tt -= 1

if ans == 100000:
    ans = -1

with open("mowing.out", "w") as fout:
    fout.write(str(ans))