USACO Silver 2016 January - Build Gates

Authors: Maggie Liu, Aadit Ambadkar

Official Analysis (Java)

Warning!

The official solution stores the farm in a 2005×20052005 \times 2005 boolean array with the origin at (1002,1002)(1002, 1002), but this is not sufficient. Since each fence segment is doubled, the maximum distance in each direction could be 20002000 units, causing an input such as 10001000 N\texttt{N}s to go out of bounds. To not go out of bounds, an array of size 4003×40034003 \times 4003 should be used: 11 unit for the origin position, 20002000 units in each direction from the origin and 11 more unit in each direction to ensure that the farm includes area beyond the fence.

Implementation

C++

#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
void ff(int i, int j);
bool fence[4003][4003] = {false};
bool visited[4003][4003] = {false};
int maxx = 2001, minx = 2001, maxy = 2001, miny = 2001;
int main() {

Alternate Faster Solution

It is possible to make the following 2 observations:

  1. For each contiguous closed region, there must be 1 gate. In a minimum state, each region has exactly 1 gate. For example, if there are 2 regions, there must be 2 gates.
  2. Each time FJ comes across a node he has visited along an edge he has not crossed in either direction, he creates exactly 1 new region. In other words, FJ creates exactly 1 new contiguous closed region if all of these conditions are met:
    • FJ walks along an edge from point aa to bb
    • He did not walk from aa to bb in the past
    • He did not walk from bb to aa in the past
    • bb is a point he had already visited

Under these observations, we can use a set of visited edges and visited nodes, and keep track of the number of contiguous closed regions. This solution is about 10 times faster than flood filling due to logN\log N lookup and insertion.

Implementation

Time Complexity: O(NlogN)\mathcal{O}(N\log N)

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("gates.in", "r", stdin);
freopen("gates.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);

Python

with open("gates.in") as read:
n = int(read.readline().strip())
s = read.readline().strip()
visedge = set()
visnode = set()
prev = (0, 0)
visnode.add(prev)
ans = 0

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!