PROBLEM LINK:Author: Pavel Sheftelevich DIFFICULTY:simple PREREQUISITES:basic understanding of graphs, trial or error PROBLEM:There is a $n \times 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. Score obtained for colouring a cell will be equal to 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. QUICK EXPLANATIONThe answer will be equal to $n \cdot(m  1) + m \cdot (n  1)$. EXPLANATION:Let us solve the first subtask before proceeding to the next one. In this subtask, we have $1 \leq n, m \leq 3$. Without loss of generality, we can assume that $n \leq m$, i.e. answer for grid of dimensions $n, m$ where $n \leq m$, will be same as that of a grid of dimensions $m, n$ where $m \leq n$, because both the grids are essentially the same. You can rotate one to obtain the other. So, we are now left to deal with following cases.
So, for solving the small subtask, you can just find these values manually and solve the problem. Here is one sample code.
Probably a better way of implementing this way would be encode these values in a two dimensional array and output them. It will save you a lot of if/else conditions which are prone to missing some cases.
Now, you might have realized that somehow the order of coloring the vertices does not matter. Let us find a formal proof of this condition, and later we will understand how to use this to solve the full subtask. Consider a graph whose vertices correspond to the cells of the grid. There will be an edge between two vertices if their corresponding cells are adjacent. Now, let us understand the colouring process on this graph instead of the grid. So, colouring a cell is equivalent to colouring a vertex of the graph. As score obtained for coloring a cell is equal to number of coloured neighbours of the cell. This means that score obtained will be number of edges between the current cell and its adjacent coloured cells. So, we wonder whether we can transform our problem in terms of counting edges instead? Whenever we color an adjacent cell of some already coloured cell, we will mark the edge between those cells. Also marking an edge will give you a score of 1. So, our total score will number of times the edges were marked. Crucial point to note is that after the end of coloring all cells, all the edges of the graph will be marked. This is simply due to that fact each of the grid cells are coloured. One interesting fact is that the each edge of the graph will be marked only $once$. This is due to the fact that an edge connects two cells. We mark the cell when both the cells are coloured. We are not allowed to colour any cell more than once, which guarantees that we will mark each cell only once. So, in whatever order you colour the cells, the number of edges marked are going to remain the same, so your score is also going to be same. Now we can use this fact to find a solution of the problem. We can just implement this process by iterating over the cells of the matrix in any way which want and maintain which of the cells are coloured and count the corresponding score. Pseudo code follows.
We can even find a closed form formula for the score. Let us find total number of edges in a $n \times m$ dimensional grid. We know that sum of degrees of all the vertices of the graph is twice the number of edges. It is easier to find sum of degrees of vertices in our case. All the vertices in the inner boundary of the grid have a degree of 4. The corner vertices on the boundary will have a degree of 2, remaining vertices on the boundary will have degree of 3. Hence, $\begin{align} sum of degrees &= 4 (n  2) (m  2) + 3 * 2 * (n  2 + m  2) + 2 * 4\\ &= 4 (n  2) (m  2) + 6n + 6m  24 + 8\\ &= 4nm  8n  8m + 16 + 6n + 6m  24 + 8\\ &= 4nm  2n  2m\\ \end{align}$ So total number of edges will = $2 (nm  n  m)$. TIME COMPLEXITYIt will be $\mathcal{O}(1)$ if we just print the answer as $2 nm  n  m$. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 25 Jun '16, 18:34

shouldn't it be a[3][3] = { {0, 1, 2}, {1, 4, 7}, {2, 7, 12} } ??? answered 25 Jun '16, 22:46

The link for the problem point to LCOLLIS not OMWG. Please fix. answered 25 Jun '16, 23:11

As n increases, difference between two successive matrices (increasing m) increases in an Arithmetic Progression. Similarly, when n is fixed and m increases, the maximum score is also an AP. The first terms and common difference can be figured out by trying out a few cases. Here's the pseudocode of the calculation part.
answered 25 Jun '16, 23:56

a[3][3] = { {0, 1, 2}, {1, 4, 7}, {2, 7, 12} } it should be this i guess, why there is 0 for n=2 m=1 and for n=3 m=1? answered 27 Jun '16, 01:04

There is an error in the above statement: =>So total number of edges will = 2(nm−n−m) Rather it should be : =>So total number of edges will = 2nm−n−m answered 26 Jul '16, 22:21

Beautiful proof of an invariant in the editorial ! Keep it up ! answered 24 Jun '17, 08:47

in short: include<iostream>using namespace std; define ll long long intint main() { ll m,n,t,i,j,a,am;cin>>t;while(t) { cin>>n>>m; a=n1; am=a+((m1)(2n1)); cout<<am<<endl;}} answered 26 Jun '16, 01:46
