GRIDBL - Editoriale

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Soumyadeep Pal
Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni

DIFFICULTY:

968

PREREQUISITES:

Basic Math

PROBLEM:

You have a grid with N rows and M columns. You have two types of dominos - one of dimensions 2 * 2 and the other of dimensions 1 * 1. You want to cover the grid using these two types of dominos in such a way that :

  • Each cell of the grid is covered by exactly one domino.
  • The number of 1 * 1 dominos used is minimized.

Find the minimum number of 1 * 1 dominos you have to use to fill the grid.

EXPLANATION:

The minimum number 1 * 1 dominos can be found by finding the maximum number of 2 * 2 dominos that can be placed in the grid. This is because the total area to be covered is constant (N * M).

We know that in each row we can place at most \lfloor N/2 \rfloor number of 2 * 2 dominos and in each column we can place at most \lfloor M/2 \rfloor number of 2 * 2 dominos. It is clear that we can always fill a sub-grid of size (\lfloor N/2 \rfloor * 2) * (\lfloor M/2 \rfloor * 2) with 2 * 2 dominos and this means that the maximum number of 2 * 2 dominos is \lfloor N/2 \rfloor * \lfloor M/2 \rfloor.

Since the total area to be covered is N * M and the maximum area to be covered by 2 * 2 dominos is 4 * \lfloor N/2 \rfloor * \lfloor M/2 \rfloor. So the minimum number of 1 * 1 dominos (= area to be covered by 1 * 1 dominos) is N * M - 4 * \lfloor N/2 \rfloor * \lfloor M/2 \rfloor.

TIME COMPLEXITY:

O(1) for each test case.

SOLUTION:

Setter's solution 
using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
	    int n, m; 
	    cin >> n >> m;
	    cout << n * m -  4 * (n / 2) * (m / 2) << '\n';
	}
}
Editorialist's Solution 
using namespace std;

int main() {
	int T;
	cin >> T;
	while(T--){
	    int n,m;
	    cin >> n >> m;
	    cout << m*n-(n/2)*(m/2)*4 << endl;
	}
	return 0;
}