So what have I planned for today? Since a problem, a day seems too slow for my 2-week goal I have taken things up a notch…
So the list of problems that were chosen yesterday are:
Leha is playing a very interesting game. The game will be played on a rectangular grid consisting of N rows and M columns. Initially, all the cells of the grid are uncolored.
Leha’s initial score is zero. At each turn, he chooses some cell that is yet not colored, and colors that cell. The score obtained in this step will be a number of neighboring colored cells of the cell that Leha colored in this step. Two cells are neighbors of each other if they share a side between them. The game will end when all the cells are colored. Finally, the total score obtained at the end of the game will sum of score obtained in each turn.
Leha wants to know what maximum score he can get? Can you please help him in finding this out?
The first line contains a single integer T denoting the number of test cases. T test cases follow.
Each of the following T lines contains two space-separated integers N, M denoting the dimensions of the grid.
Constraints //For now, I don’t think the constraints bother me as much as the understanding of the question
1 = T = 100
1 = N, M = 1 000
Leha can obtain total score 4 in the following way.
- In the first step, he colors the bottom left cell, all the neighboring cells of this cell are uncolored. So, it adds 0 to the total score.
- In the second step, he can color upper right cell, it also adds total 0 to the score.
- In the third step, he can color top left cell. There are two neighboring cells of this cell, both of which are colored. So, this adds 2 to the score.
- In the last step, he can choose the remaining down the right cell. There are two neighboring cells of this cell, both of which are colored. So, this also adds2 to the score.
There is a n×m dimensional grid. Initially, the cells of the grid are uncoloured. You will colour all the cells of the grid one by one colouring a single cell each time. The score obtained for colouring a cell will be equal to the number of already coloured neighbouring cells of the cell that you are going to colour. Note that two cells are considered to be neighbours of each other, if they share a side with each other.
When I was trying to code this, I ended up playing the game like multiple games and I stumbled upon a pattern to win the game with the maximum possible score.
Fill up alternate boxes in the grid. Then start filling the interior ones. They would have boxes of score 4 in the middle ((m-1)*(n-1) alternate boxes) , boxes with score 3 along the edges and 2 boxes of score 2 if the values of m*n return an even number? (We were doing number systems yesterday so I ended up thinking with respect to the divisibility rules…)
But there were too many holes in this way, and I wasn’t willing to move on … and that was where I got stuck?!?
Apparently after a small discussion about a project proposed by one of my colleagues, I realized this is like the map colouring problem I had learnt in the previous semester under constraint satisfaction problem… Well after when I came home I searched a little about it online… and I came across this formulae (I am sorry I cheated But I really did try… I’ll put a pic of my note in the bottom if I have time)
T = int(input())
for i in range(T):
n, m = [int(s) for s in input().split(” “)]; # read a list of integers, 2 in this case
Well, I got to learn a little about the constraint satisfaction problems? So I guess I should know more algorithms concerning graphs … I’ll get to it if I have time during the weekends?