USACO 2020 December Contest, Bronze Problem 3. Stuck in a Rut

USACO 2020 December Contest, Bronze Problem 3. Stuck in a Rut

Farmer John has recently expanded the size of his farm, so from the perspective of his cows it is effectively now infinite in size! The cows think of the grazing area of the farm as an infinite 2D grid of square "cells", each filled with delicious grass (think of each cell as a square in an infinite chessboard). Each of Farmer John's NN cows (1≤N≤501≤N≤50) starts out in a different cell; some start facing north, and some start facing east.

Every hour, every cow either

 

• Stops if the grass in her current cell was already eaten by another cow.
• Eats all the grass in her current cell and moves one cell forward according to the direction she faces.

Over time, each cow therefore leaves a barren "rut" of empty cells behind her.

If two cows move onto the same grassy cell in the same move, they share the cell and continue moving in their respective directions in the next hour.

Please determine the amount of grass eaten by each cow. Some cows never stop, and therefore eat an infinite amount of grass.

 

To be as clear as possible regarding directions and coordinates, if a cow is in cell (x,y)(x,y) and moves north, she ends up in cell (x,y+1)(x,y+1). If she instead had moved east, she would end up in cell (x+1,y)(x+1,y).

 

 

SAMPLE INPUT:

6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 2
N 8 1

SAMPLE OUTPUT:

5
3
Infinity
Infinity
2
5

 

 

Problem credits: Brian Dean

USACO 2020 December Contest, Bronze Problem 3. Stuck in a Rut 题解(雷竞技raybet安卓版下载 提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Brian Dean)

At a high level, this problem is approachable in several straightforward ways. Perhaps the most natural approach is to directly simulate the moovements of the cows. For the earlier testcases (numbers 2-5), all coordinates are at most 100, so one can simulate the movement of each cow on a 2D array, marking squares visited by cows as ruts, and making a note of whenever a cow hits a rut. However, this approach won't work for the larger cases, since we don't have enough memory to store the 2D representation of the farm explicitly as a 2D array when coordinates are large.

To simulate larger cases, we could keep track of the position and direction of each cow, along with when (and if) the cow has already stopped. With a bit of math, we can determine the next time an "interesting event" happens -- namely, that some cow ii hits a rut carved out by some other cow jj. We move all the cows forward to this point in time, mark cow ii as stopped, and then continue, looking for the next "interesting event", and so on. Each step requires looking at all pairs of cows to find the next intersection with a rut, and so takes O(N2)O(N2) time. The simulation involves at most NN total steps, since each step ends with at least one cow stopping. Hence, the total running time of a direct simulation is O(N3)O(N3). It's important that we "fast forward" from one interesting event to the next, instead of stepping forward by 1 time step at a time, since otherwise the solution might take too long, with coordinates being as large as they are. My C++ code for this approach is as follows; I've tried to add comments to make it reasonably readable:

 

#include <iostream>
using namespace std;

int Infinity = 1000000001;

struct Cow {
  int time_stopped; // time at which stopped
  int x, y;         // current location
  char dir;         // N or E
};

int N;
Cow C[50];

// At what time would cow i hit the rut carved out by cow j and stop?  (Infinity if no such event)
// (and this is only considering these two cows for the moment)
int when_hits(int i, int j, int current_time)
{
  Cow I = C[i], J = C[j];
  if (I.dir == J.dir) return Infinity; // never hits if moving same direction (or same cow)
  if (I.dir == 'E') { // assume without loss of generality that I is moving north, and J east
    swap (I.x, I.y); swap (J.x, J.y); 
  }
  if (J.y <= I.y) return Infinity; // J isn't north of I?
  if (J.time_stopped == Infinity) {
    if (I.x < J.x - current_time || I.x >= J.x + J.y - I.y) return Infinity; // No insersection, J still mooving
  } else {
    if (I.x > J.x || I.x < J.x - J.time_stopped) return Infinity; // No intersection; j stopped already
  } 
  return current_time + J.y - I.y;
}

// Returns the next time after current_time at which a cow hits a rut and stops  (or Infinity if no such event)
// Also move cows forward until that time and update which cows are stopped
int advance_to_next_event(int current_time)
{
  // T[i] is the next time something happens to cow i; minT is the earliest of these
  int T[50], minT = Infinity;
 
  for (int i=0; i<N; i++) {
    T[i] = Infinity;
    if (C[i].time_stopped == Infinity) { // For all cows still mooving....
      for (int j=0; j<N; j++) {            // What does it hit next?
        int t = when_hits(i, j, current_time);
        if (t < T[i]) T[i] = t; 
      }
      if (T[i] < minT) minT = T[i]; 
    }
  }
  
  if (minT == Infinity) return Infinity;

  // Advance cows, stopping those that hit a rut
  for (int i=0; i<N; i++) {
    if (C[i].time_stopped == Infinity)
      if (C[i].dir == 'N') C[i].y += (minT - current_time);
      else                 C[i].x += (minT - current_time);
    if (T[i] == minT) C[i].time_stopped = minT;
  }

  return minT;
}

int main(void)
{
  cin >> N;
  for (int i=0; i<N; i++) {
    cin >> C[i].dir >> C[i].x >> C[i].y;
    C[i].time_stopped = Infinity;
  }

  // Now just advance from one "event" to another until done...
  int current_time = 0;
  do { current_time = advance_to_next_event(current_time); }
  while (current_time != Infinity);

  for (int i=0; i<N; i++)
    if (C[i].time_stopped == Infinity) cout << "Infinity\n";
    else                               cout << C[i].time_stopped << "\n";
}

There are several variations on this theme. In another approach, one can look at all pairs of cows and generate a list of all O(N2)O(N2) possible "potential intersections" that will ever happen. Some may not happen, if one or more of the cows in a pair have already stopped before reaching the point where their trails would intersect. However, we can again simulate the moovement of the cows, by stepping through these potential intersections in chronological order. At each step, we look at the next prospective intersection (say, where cow ii would nominally hit the rut carved by cow jj). If cow ii is still mooving and cow jj has mooved at least to the point of this intersection, then cow ii is stopped at this point. Each iteration, we scan the list of O(N2)O(N2) intersections to find the next one chronologically, so a straightforward implementation here might take O(N4)O(N4) time. I'm including a couple of implementations along these lines --- here's some C++ code I wrote that uses this approach:

 

#include <iostream>
using namespace std;

const int MAX_N = 50;

int N, x[MAX_N], y[MAX_N], tstop[MAX_N];
char dir[MAX_N];

struct Intersection {
  int i, j, time_i, time_j, active;
};
Intersection I[MAX_N*MAX_N];

void find_all_intersections(void)
{
  int current = 0;
  for (int i=0; i<N; i++)
    for (int j=0; j<N; j++) {

      if (dir[i] == dir[j]) continue; // no intersection if same direction (or same cow)

      // Possibly flip coordinates so that for simpllicity, we can
      // assume without loss of generality that cow i is moving north, and cow j east
      int xi = x[i], yi = y[i], xj = x[j], yj = y[j];
      if (dir[i] == 'E') { swap(xi,yi); swap(xj,yj); } 
      
      if (yi > yj) continue; // cow i already north of cow j?
      if (xi < xj) continue; // cow i already west of cow j?
      if (xi >= xj + yj - yi) continue; // cow i passes before cow j can cut her off

      Intersection Inew = { i, j, yj-yi, xi-xj, 1 };
      I[current] = Inew;
      current++;
    }
}

int main(void)
{
  cin >> N;
  for (int i=0; i<N; i++) cin >> dir[i] >> x[i] >> y[i];

  find_all_intersections();
  
  // Repeatedly find earliest remaining intersection and process it
  while (1) {
    int earliest = -1;
    for (int i=0; i<MAX_N*MAX_N; i++)
      if (I[i].active)
        if (earliest == -1 || I[i].time_i < I[earliest].time_i) earliest = i;
    if (earliest == -1) break;
    Intersection &E = I[earliest];
    if (tstop[E.i] == 0 && (tstop[E.j] == 0 || tstop[E.j] > E.time_j))
      tstop[E.i] = E.time_i;
    E.active = 0;
  }
  
  for (int i=0; i<N; i++)
    if (tstop[i] == 0) cout << "Infinity\n";
    else               cout << tstop[i] << "\n";
}

I've made it a point in my code above not to use sorting, with this being a bronze-level problem, to emphasize that one doesn't need any elaborate algorithms. Sorting can of course also be part of your solution, and it can help with simplifying the task of visiting things in chronological order. Below is some Java code from Danny Mittal, where he finds the time of every "prospective" intersection point, sorts these values of time, and then processes them in order. For each time point of interest, he loops over all pairs of cows to figure out if there is an intersection caused by the pair at the point in time in question:

 

    import java.util.*;
     
    public class StuckInARutBronzeQuartic {
     
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int[] xs = new int[n];
            int[] ys = new int[n];
            char[] dir = new char[n];
            for (int j = 0; j < n; j++) {
                dir[j] = in.next().charAt(0);
                xs[j] = in.nextInt();
                ys[j] = in.nextInt();
            }
            int[] answer = new int[n];
            Arrays.fill(answer, Integer.MAX_VALUE);
            List<Integer> differences = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    differences.add(Math.abs(xs[k] - xs[j]));
                    differences.add(Math.abs(ys[k] - ys[j]));
                }
            }
            Collections.sort(differences);
            for (int d : differences) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        if (dir[j] == 'E' && dir[k] == 'N' && xs[j] < xs[k] && ys[k] < ys[j]) {
                            if (xs[j] + d == xs[k] && ys[k] + Math.min(answer[k], d) > ys[j]) {
                                answer[j] = Math.min(answer[j], d);
                            } else if (ys[k] + d == ys[j] && xs[j] + Math.min(answer[j], d) > xs[k]) {
                                answer[k] = Math.min(answer[k], d);
                            }
                        }
                    }
                }
            }
            for (int j = 0; j < n; j++) {
                System.out.println(answer[j] == Integer.MAX_VALUE ? "Infinity" : answer[j]);
            }
        }
    }

Faster solutions are possible by using essentially the same approach (i.e., finding all interesting time points and simulating these in chronological order) -- these are needed to solve the silver variation of this problem, so please consult the silver solutions for further details.

[/hide]