Posted in GCJ

GCJ Post #2

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…

((งง •̀•̀__•́•́))งง

I have planned to put 5 problems of the GCJ types and discuss post and lot picked one for the next 2 weeks until July 10th.

So the list of problems that were chosen yesterday are:

  1. Rupsa and the Game
  2. Sticks
  3. Entrance Game
  4. One more weird game
  5. Collisions
So the lot picked problem for today is 

One More Wierd Game

*Wow… I sat on this for way too long during my placement training session yesterday *sigh…*

The problem statement :

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?

Input

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.

Output

For each test case, output a single line containing an integer corresponding to the maximal possible score Leha can obtain.

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

Example

Input:
1
2 2

Output:
4

Explanation

Leha can obtain total score 4 in the following way.

  1. 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.
  2. In the second step, he can color upper right cell, it also adds total 0 to the score.
  3. 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.
  4. 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.

Leha can’t obtain a score more than 4. Hence 4 is the answer.

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)

So the code I came up with is this… pretty simple, right? 

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
   print(2*m*n-n-m);

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?

UPDATE:

*I kinda am horrible with cameras so deal with it*
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s