PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Author: Sachin Yadav
Tester: Vraj Patel
Editorialist: Nishikant Parmar
DIFFICULTY:
SIMPLE
PREREQUISITES:
Basic Mathematics
PROBLEM:
There is a rectangular piece of land, surrounded by fences.
The land can be thought of as a 2d grid which extends N units vertically and M units horizontally. It is divided into N horizontal rows, which are numbered from 1 to N, as you move from top to bottom and into M vertical columns numbered from 1 to M, from left to right.
There are X rivers flowing in a horizontal direction, each flowing in a different row and covering the entire row. Similarly, there are Y rivers flowing in a vertical direction, each flowing in a different column and covering the entire column.
The people want to build houses of dimensions S \times S on the remaining land.
What is the maximum number of houses of the given dimensions that could be built on the remaining land, such that no part of any house is in a river and no two houses overlap?
QUICK EXPLANATION:
We find the expression for the total number of squares by adding the number of squares that can be placed in each rectangle formed due to the rivers. For each rectangle with length a and width b, number of houses possible is (a/S)*(b/S). We just sum it over all rectangles in the grid.
EXPLANATION:
Throughout the editorial, x//y denotes \lfloor \frac{x}{y} \rfloor.
Let us think of a sub-problem, where we are given a rectangle of height a and width b, then how many squares of side s, we can place on the rectangle?
Since, the maximum number of squares that can fit on a side of length a are a//s, similarly b//s for the other side.
So, maximum number of squares = (a//s)*(b//s)
In the original problem we have to answer the total number of squares that can be placed on the grid. Hence, it would be the sum of squares that can be placed on individual rectangles formed due to partition by the rivers.
Now, let us consider the following grid -
Here, the number of squares that can be placed in the first row of rectangles (i.e. on the rectangles 1,2 and 3) are -
(a_{1}//s)\times (b_{1}//s)+(a_{1}//s)\times (b_{2}//s) + (a_{1}//s)\times (b_{3}//s)
Thus, on the i^{th} row of rectangles the number of squares that can be placed are -
(a_{i}//s)\times (b_{1}//s)+(a_{i}//s)\times (b_{2}//s) + (a_{i}//s)\times (b_{3}//s)
which is equal to -
(a_{i}//s)\times \sum_{i=1}^3 (b_{i}//s)
So, the total number of squares that can be placed in all rows -
(a_{1}//s)\times \sum_{i=1}^3 (bi//s) + (a_{2}//s)\times \sum_{i=1}^3 (bi//s) + (a_{3}//s)\times \sum_{i=1}^3 (bi//s)
which is equal to -
[\sum_{i=1}^3(ai//s)]\times [\sum_{i=1}^3 (bi//s)]
If m be the number of segments created by rivers along y-axis and n segments along x-axis, then this expression can be generalized for any grid.
Thus, the maximum number of squares is :
[\sum_{i=1}^n(ai//s)]\times [\sum_{i=1}^m (bi//s)]
TIME COMPLEXITY
O(M+N)
SOLUTIONS:
Setter's Solution
#include<iostream>
using namespace std;
int main()
{
int T; cin>>T;
while(T--)
{
int N, M, X, Y, s;
cin>>N>>M>>X>>Y>>s;
int prev_x=0, sum_x=0, prev_y=0, sum_y=0;
for(int i=0; i<X; i++)
{
int x; cin>>x;
sum_x+=(x-prev_x-1)/s;
prev_x=x;
}
sum_x+=(N-prev_x)/s;
for(int i=0; i<Y; i++)
{
int y; cin>>y;
sum_y+=(y-prev_y-1)/s;
prev_y=y;
}
sum_y+=(M-prev_y)/s;
cout<<sum_x*sum_y<<"\n";
}
return 0;
}
Tester's Solution
for _ in range(int(input())):
N, M = [int(i) for i in input().split()]
X,Y,s = [int(i) for i in input().split()]
X_l = [int(i)-1 for i in input().split()] if X>0 else []
Y_l = [int(i)-1 for i in input().split()] if Y>0 else []
X_l = [-1] + X_l + [N]
Y_l = [-1] + Y_l + [M]
diff_x = sum([(i-j-1)//s for i,j in zip(X_l[1:],X_l)])
diff_y = sum([(i-j-1)//s for i,j in zip(Y_l[1:],Y_l)])
print(diff_x*diff_y)
Editorialist's Solution
T=int(input())
for k in range(T):
N, M = map(int,input().split())
X, Y, s = map(int,input().split())
if(X>0):
X_rivers = list(map(int,input().split()))
if(Y>0):
Y_rivers = list(map(int,input().split()))
#sum of bis
X_prev = 0
B_sum = 0
for i in range(X):
B_sum+=(X_rivers[i]-X_prev-1)//s
X_prev = X_rivers[i]
B_sum+=(N-X_prev)//s
#sum of ais
Y_prev = 0
A_sum = 0
for j in range(Y):
A_sum+=((Y_rivers[j]-Y_prev-1)//s)
Y_prev = Y_rivers[j]
A_sum+=(M-Y_prev)//s
print(A_sum*B_sum)
