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();
}