ISHVALA - Editorial

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 -
image1

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)
 
8 Likes

what are those
6 5
2 0 1
1 4
in sample input?

how here (a1//s)(b1//s)+ (a1//s)(b2//s) * (a1//s)(b3//s)
(a1//s)
(b1//s)+ (a1//s)(b2//s) + (a1//s)(b3//s)
the above format is it correct ?

Pls review my code solution
what is wrong with it? the sample test cases give the right answer

on line 40 and 41 you are pushing upper bound of x in y( y.push_back(N); ) and upper bound of y in x( x.push_back(M):wink:
it should be:
x.push_back(N);
y.push_back(M);

Solution 30231347 for problem “PRACTICE/ISHVALA” - WHY IS THIS WRONG ANSWER. BELOW IS THE CODE

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

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);

	int T = sc.nextInt();

	while (T-- > 0) {
		int rows = sc.nextInt();
		int columns = sc.nextInt();
		int rows_lg = sc.nextInt();
		int columns_lg = sc.nextInt();
		int s = sc.nextInt();
		int current = 1;
		int river;
		int count1 = 0, count2 = 0;

		for (int i = 0; i < rows_lg; i++) {
			river = sc.nextInt();
			if (current + s - 1 < river) {
				count1 += (river - current) / (current + s - 1);
				current = current + s;
			}
		}

		if (current + s - 1 < rows) {
			count1 += (rows - current) / (current + s - 1);
		}

		current = 1;
		for (int i = 0; i < columns_lg; i++) {
			river = sc.nextInt();
			if (current + s - 1 < river) {
				count2 += (river - current) / (current + s - 1);
				current = current + s;
			}
		}

		if (current + s - 1 < columns) {
			count2 += (columns - current) / (current + s - 1);
		}

		System.out.println(count1 * count2);
		count1 = 0;
		count2 = 0;
	}
}

}

can anyone review my code pls sample testcases come correct
https://www.codechef.com/viewsolution/34881887

In my submission I’m getting runtime error even though the code is pretty much the same as that in the editorial.
https://www.codechef.com/viewsolution/35714133
Any help is appreciated.

my code is showing an error.
can anyone suggest to me how to fix it??
here’s my code for this problem
#include <bits/stdc++.h>
using namespace std;
#define l long long

int main()
{
l t; cin>>t;
while(t–){
l n,m,x,y,s;
cin>>n>>m>>x>>y>>s;
l p_x=0,s_x=0,p_y=0,s_y=0;
for(l i=1;i<=x;i++){
l val_x;
cin>>val_x;
s_x+=(val_x-p_x-1)/s;
p_x=val_x;
}
s_x+=(n-p_x)/s;
for(l j=1;j<=y;j++){
l val_y;
cin>>val_y;
s_y=(val_y-p_y-1)/s;
p_y=val_y;
}
s_y+=(m-p_y)/s;
cout<<s_x*s_y<<"\n";
}

return 0;
}

Can somebody help me with my code , finding the error

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t ;
    cin>>t;
    while (t--){
        int x,y,s,n,m;
        cin>>n>>m;
        cin>>x>>y>>s;
        int hor_riv[x] , ver_riv[y];
        int sumx = 0 , sumy = 0, rx = 0 , ry=0;
        for(int i=0 ; i<x ; i++){
            cin>>hor_riv[i];
            sumx += (hor_riv[i] - rx -1)/s;
            rx = hor_riv[i];
        }
        sumx+= (n-rx)/s;
        for(int i=0 ; i<y ; i++){
            cin>>ver_riv[i];
            sumy += (ver_riv[i] - ry -1)/s;
            ry = ver_riv[i];
        }
        sumy+= (m-ry)/s;
        int ans = sumx*sumy ;
        cout<<ans<<endl;

    }

}

Code gave AC.

Why do you think it is wrong ? I see no coding or logic errors.

my mistake !!