Table of Contents

ExplanationImplementation

Explanation

For each room the mentor can be in, we binary search on the maximum distance between the mentor and the farthest student since a larger distance always works if a smaller one does. We binary search over the possible distances from 00 to the maximum grid dimension, or max⁡(n,m)\max(n, m).

Notice that if we're currently checking a distance dd at a starting position (r,c)(r, c), then the students can be anywhere from (r−d,c−d)(r - d, c - d) to (r+d,c+d)(r + d, c + d), excluding the out-of-bounds rooms.

We can use prefix sums to efficiently compute the capacity of the subgrids described above. This allows us to quickly check if a given area can accommodate all students and the mentor.

Implementation

Time Complexity: O(NM)\mathcal{O}(NM)

Warning: Remember the Mentor!

When implementing, be sure to take into account that the room we check has nonempty capacity and that there's enough space for the mentor himself!

C++

#include <algorithm>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::max;
using std::min;
using std::vector;

Java

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


public class TripTastic {
	/** @return the sum of the room capacity from (sr, sc) to (er, ec) inclusive */
	static long rectSum(long[][] rPref, int sr, int er, int sc, int ec) {
		return rPref[er + 1][ec + 1] - rPref[sr][ec + 1] - rPref[er + 1][sc] +
		    rPref[sr][sc];
	}

Python

for _ in range(int(input())):
	row_num, col_num, kid_num = [int(i) for i in input().split()]


	# 2D prefix sum array of the rooms
	r_pref = [[0 for _ in range(col_num + 1)] for _ in range(row_num + 1)]
	for r in range(1, row_num + 1):
		row = [int(i) for i in input().split()]
		for c in range(1, col_num + 1):
			r_pref[r][c] = row[c - 1]
			r_pref[r][c] += r_pref[r - 1][c] + r_pref[r][c - 1] - r_pref[r - 1][c - 1]

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!

Join Forum