UWCOI20D - Base Plans - Editorial

D. Base Plans:

Link to Practice
Link to Contest

Author: Soumyaditya Choudhuri (socho)
Tester: Jatin Yadav (jtnydv25)
Editorialist: Soumyaditya Choudhuri (socho)

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

PERMUTATIONS, COUNTING

PROBLEM:

Let’s call a K * K binary grid valid, if it satisfies the following constraints:

  • Each row and each column has exactly one occurrence of 1.

You are given a valid N * N grid. Find the number of square subgrids of any size which are also valid.

Subtask 1 [28 points]: All the occurrences of 1 are on the top-left to bottom-right diagonal.
Subtask 2 [39 points]: N \leq 600
Subtask 3 [33 points]: N \leq 2500

QUICK EXPLANATION:

We represent the grid as a permutation array. We then count the number of subarrays A[i:j] of this array such that the max(A[i:j])-min(A[i:j]) = j-i.

EXPLANATION:

Subtask 1

We note that in this subtask, every tower square is on the top-left to bottom-right diagonal. In this case, we notice that every square which has a top-left to bottom-right diagonal coinciding with the same diagonal of the entire grid, will be a valid subgrid. Each of these squares, say of side length K, will have each of the K squares on its diagonal to make a valid subgrid. The answer for this subtask is therefore the N-th triangular number, or N * (N + 1) / 2.

Subtask 2

In this subtask, we note that N \leq 600. We have two very different solutions for this subtask, and we describe them both below:

Approach 1

We first maintain a 2D range sum data structure known as a “prefix sum”. We precompute it over the 2D array in O(N^2) time. This allows us to answer queries of the form “how many tower squares are in some subgrid of the grid” in O(1) time. We notice that the three constraints to form a valid base plan, can be reduced to, “how many different K*K squares have exactly K towers in them?”.

We see that there are O(N^2) possible top-left corners to a square subgrid. For each of these possible top-left corners, we notice that the bottom-right corners which allow this subgrid to be square must lie on the same diagonal as the top-left corner. As the length of the diagonal is about N, this means that there are N possible bottom-right corners to check for each top-left corner. There are therefore N^3 possible square subgrids of the grid. Each of these can be checked in O(1) time, using our prefix-sum for a total of O(N^3).

Approach 2

This approach builds on more directly to the final solution.

We first notice that the constraint of one cell per row and one cell per column is very useful. This allows us to construct an array representation of our grid A, of size N such that A[i] is the column of the tower square in row i. For example, in the first sample input, the array A = [1, 2] and in the second sample input, the array A = [1, 3, 2, 4].

We realise that in this array, all contiguous subarrays will represent a set of adjacent rows. In these rows, we consider the rightmost column and the leftmost column of a tower square. For this set of adjacent rows to have a valid subgrid, the rightmost column and the leftmost column must be exactly the number of rows in this set.

Since our array represents the positions of the tower square, we notice that the rightmost tower square in some set of rows must be the maximum value in the corresponding subarray. Similarly, the leftmost tower square must be the minimum value in the corresponding subarray. We therefore just need to check for every possible subarray, say A[i] to A[j] has max(A[i], A[i+1]..A[j-1], A[j]) - min(A[i], A[i+1]..A[j-1], A[j]) == j-i.

There are O(N^2) possible subarrays, each of which can be checked in O(N) time to find the maximum and the minimum, for a total of O(N^3).

Subtask 3

The final solution to this task builds on directly from Approach 2 in Subtask 2. Instead of checking for every subarray in O(n) time, it is possible to check the range maximum / minimum in O(log(n)) time using a range-min query data structure, for example, a segment tree.

An alternative (and significantly nicer!) solution for this subtask is to fix the left endpoint of the subarrays you are considering, and advance the right endpoint to update the maximum and minimum variables, and then maintain the check. This solution scores a perfect score for this task.

SOLUTIONS:

Setter's Solution
#include "bits/stdc++.h"
using namespace std;

void solve() {
	
	int n;
	cin >> n;
	
	vector<long long> cds;
	for (int i=0; i<n; i++) {
		string s;
		cin >> s;
		for (int j=0; j<n; j++) {
			if (s[j] == '1') cds.push_back(j);
		}
	}
	
	long long answer = 0;
	
	for (int i=0; i<n; i++) {
		long long mn = INT_MAX;
		long long mx = INT_MIN;
		for (int j=i; j<n; j++) {
			mn = min(mn, cds[j]);
			mx = max(mx, cds[j]);
			if (mx - mn + 1 == j - i + 1) {
				answer++;
			}
		}
	}
	
	cout << answer << endl;
	
}

int main() {

	int t;
	cin >> t;
	while (t--) solve();

}
10 Likes

Base test cases are passed but giving RE-NZEC for rest cases on submit.
can anyone tell whats the problem with code…

public static void main(String[] args) throws IOException {
Reader input = new Reader();
PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
int t = input.nextInt();
while (t-- > 0) {
int n = input.nextInt();

		int arr[] = new int[n];
		for (int i = 0; i < n; i++) {
			String a = input.readLine();
			for (int j = 0; j < n; j++) {
			char ch= a.charAt(j);
				if (ch == '1') {
					arr[j] = i;
				}
			}
		}

		int count = n;
		for (int i = 2; i <= n; i++) {
			for (int j = 0; j <= n - i; j++) {
				int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
				for (int k = j; k < j + i; k++) {
					if (arr[k] < min)
						min = arr[k];
					if (arr[k] > max)
						max = arr[k];
				}
				int diff = Math.abs(max - min);
				if (diff == i - 1)
					count++;
			}
		}
		out.println(count);

	}
	out.flush();

}

I am not getting this. Can anyone explain this.

1 Like

Can this problem be solved with recursion??
Can base case be 1x1 matrix and 2x2matrix for, 2x2 we have to check the two boxes on the diagonals is 1 or not ,if it is then return ,…like this recur for every possible matrix i.e3x3 ,4x4,5x5.
3x3 matrix has total four 2x2 matrix… So every four 2x2 matrix must satisfy the condition to include or count it as base plan.
But how to implement it???

Consider a set of contiguous rows, for this set to be a valid grid(a square), the sides of the square should be same. In other words, if the height of the square is represented as length of contiguous rows, the width of the square should be difference between leftmost and rightmost column. Then height = width for a square. Check this condition for all pairs of rows and correspondingly increase the count.

Thanks for the explanation!