USACO Silver 2016 January - Build Gates
Authors: Maggie Liu, Aadit Ambadkar
Warning!
The official solution stores the farm in a boolean array with the origin at , but this is not sufficient. Since each fence segment is doubled, the maximum distance in each direction could be units, causing an input such as s to go out of bounds. To not go out of bounds, an array of size should be used: unit for the origin position, units in each direction from the origin and 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:
- 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.
- 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 to
- He did not walk from to in the past
- He did not walk from to in the past
- 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 lookup and insertion.
Implementation
Time Complexity:
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!