Official Analysis (Java)

Solution

Explanation

By computing the 2D Prefix Sum for the grid, we can evaluate the usability of a frame in $\mathcal{O}(1)$ time.

Due to the low bounds on $N$, we can iterate through all possible pairs of columns and find the maximum area frame in $O(N)$ with a sliding window.

Implementation

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

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

int main() {
	freopen("fortmoo.in", "r", stdin);
	freopen("fortmoo.out", "w", stdout);

	int n, m;
	cin >> n >> m;

Alternate Solution

Explanation

The approach here is a bit different from the official solution, using an adaption of 2D Kadane's algorithm instead.

Iterate through all possible pairs of columns. For each pair, we'll solve the problem with the restriction that the fort must be aligned along these two columns. For each row between these two columns, we will use prefix sums to check if the area between the two columns and in the row is clear.

We keep a running variable $r_{start}$ which keeps track of the earliest row we can start the fort at and iterate through all possible row endings ($r_{end}$ in the code). Note that if a swampy area resides in one of the columns themselves, no fort can go through that row, so we must check for that and update $r_{start}$ accordingly.

Implementation

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

Copy
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

const char BAD = 'X';

Copy
import java.io.*;
import java.util.*;

public class FortMoo {
	private static final char BAD = 'X';
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("fortmoo.in"));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int rowNum = Integer.parseInt(initial.nextToken());
		int colNum = Integer.parseInt(initial.nextToken());