USACO Silver 2016 January - Build Gates

Official Analysis (Java)

Implementation

Copy
#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 $a$ to $b$
   • He did not walk from $a$ to $b$ in the past
   • He did not walk from $b$ to $a$ in the past
   • $b$ 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 $\log N$ lookup and insertion.

Implementation

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

Copy
#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);

Copy
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