A simple Knight's problem

Question

How many ways are there to place a black and a white knight on an N * M chessboard such that they do not attack each other?

A knight can move two squares horizontally and one square vertically, or two squares vertically and one square horizontally.

The knights have to be placed on different squares and the knights attack each other if one can reach the other in one move.

Input:

The first line contains the number of test cases T. Each of the next T lines contains two integers N and M, representing the dimensions of the board.

Output:

Output T lines, one for each test case, each containing the required answer for the corresponding test case.

Sample input:

3
2 2
2 3
4 5

Sample output:

12
26
312

Constraints

    1 <= T <= 10000
    1 <= N,M <= 100000
time limit 1 sec

Source Limit:

50000 Bytes

Winning criteria

Shortest code which runs with specified time limit decides the winner

i ll leave two days time for more users to try from today

Answer 1

GNU Octave, 55 _{56 58 78 87* 93} chars

a=t(:,1);b=t(:,2);-4*max(2*(g=a.*b)-3*(a+b)+4,0)+g.*--g

Octave doesn't take input from STDIN, so you've got to provide the input in the program:

t = [
    1 7;
    2 2;
    2 3;
    4 5;
    5000 6000 
];                % test cases

a=t(:,1);b=t(:,2);-4*max(2*(g=a.*b)-3*(a+b)+4,0)+g.*--g

The logic is as follows:

nchoosek(n*m, 2) gives us the number of combinations of two positions we can have on a N*M board. We then multiply it by two since we have two different knights.

Then we work out how many 3*2 blocks fit in an N*M board. For each 3*2 block there are 4 different positions our knights can be attacking each other. So we multiply it by 4 and subtract it from the value we calculated above.

*thanks to a simplification of the nchoosek I shamelessly stole from Matt.

Edit

I've just tested this on my laptop to make sure it meets the time requirements.

It will compute 500,000 10,000,000 test cases in an average of 0.918787 0.231201 seconds

Answer 2

Python 105 119 112 104

for a,b in[map(int,raw_input().split())for i in[1]*input()]:print a*b*(a*b-1)-4*(max(2*a*b-3*(a+b)+4,0))

This uses the same approach as Griffin's solution.

Now appropriately handles boards of size 1xn

Answer 3

Mathematica 55 50 38 41

Second attempt

This is my rendering, in Mathematica, of @Matt's solution. Credit for the underlying reasoning goes to Matt. Griffin helped me understand how Matt's approach works.

It is faster than my first approach approach but still too slow to satisfy the time constraints for boards with 10^5*10^5 cells. The pure function (38 chars) is defined as follows:

 #1 #2 (#1 #2-1)-4 Max[2 #1 #2-3 (#1+#2)+4,0]&

Usage

#1 #2 (#1 #2-1)-4 Max[2 #1 #2-3 (#1+#2)+4,0]& @@@ {{2, 2}, {2, 3}, {4, 5}}

(* out *)
{12, 26, 312}

The symbols, @@@, apply the function to the list. I included them in the character count.

---

First Attempt: 50 chars but really, really slow.

I'm including it because it may be of interest to some readers.

Mathematica doesn't take input from STDIN so I used an input more to its liking. There is no need to input the number of inputs; MMA will simply act on whatever number it is given.

Code

#1*#2*(#1*#2-1)-2 EdgeCount[#1~KnightTourGraph~#2] &

---

Usage (with spaces for readability).

#1*#2*(#1*#2 - 1) - 2 EdgeCount[#1~KnightTourGraph~#2] &; @@@ {{2,2}, {2,3}, {4,5}}

(* out *)
{12, 26, 312}

---

Explanation

Below is a graph of possible knight moves in a 4 by 5 chessboard.

k = KnightTourGraph[i, j, PlotLabel -> Subscript[K, i, j]]

There are 20*19 = 380 ways to arrange the black and white knight on the board. Below is the adjacency matrix:

AdjacencyMatrix[k] // MatrixForm

There are 68 cases in which the knights are in an attacking position. This corresponds tohow many one's there are in the matrix. It also happens to equal two times the number of edges and sum of the degrees of the vertices.

t = 2*EdgeCount[k]
(* out *)
68

Finally, 380-68 = 312.

---

Timing

It takes just under one second to calculate the answer for all grids up to 15 by 15. Note: 312 is in row 4, column 5.

Answer 4

C++, 232 250 228 192 173 characters

#include<iostream>
int main(){long long n,x,y,i;for(std::cin>>n;n--;)std::cin>>x>>y,i=(x*2-2)*(y-2<0?0:y-2)+(y*2-2)*(x-2<0?0:x-2)<<1,x*=y,std::cout<<x*x-x-i<<"\n";return 0;}

SEE IT RUN

I don't know what hardware ideone uses, but that can run for a 10000x10000 board 10000 times in .2 seconds.

How I simplified the problem:

I started out trying to find ways I could divide the board into known regions, with a certain density of bad positions per square. The simplest case is that if there are no edges within 2 squares of a square, that square has 8 possible failing positions. This turned out to be really complicated near the edges of the board where more than 2 edges can sometimes come into play (if, for example, you have a board that's only 2 wide), so I decided to try to simplify it based on direction, which turned out to be very easy.

First, I considered just one direction. On a chessboard of irrelevant length, how many moves are eliminated by the introduction of one unit of width? I made a table:

Width of board         Number of positions eliminated
1                      0
2                      2
3                      4
4                      6
N                      2N-2

I used my E=2N-2 formula along with the knowledge that for a board of length L, L-2 rows are viable (and thus count towards the exclusion count).

The program, conceptually, makes 4 sweeps, one in each direction (in practice it does 2, and multiplies by 2. It's a shortcut that works because of symmetry). Each sweep represents the moves excluded that tend in the direction of the sweep. The program then sums up each of the sweeps and subtracts from the total number of possible combinations.

Knight placement is random, but two knights cannot occupy the same space. Therefore, the total number of positions you can place a knight is the total numbers of squares the first time, then the number of squares minus one the second time (since there is a square that's taken).

EDIT 1

fixed overflow, fixed forgetting to substract somewhere causing incorrect answers with a dimension of 1. Also swapped out 31's for 63's in bit twiddling since it uses 64 bit data types now

EDIT 2

shortened further (introduced branching D: the non-branching version is 6 characters longer.)

GOLF SCORECARD

• removed unnecessary clause: (~u>>31&(x<<1)-2) became ((x*2)-2) in 2 places, saved 16 characters (234)
• swapped ~u>>63&u for u<0?0:u in 2 places, saving 2 characters (232)
• swapped x-2<0?0:x-2 for u<0?0:u and removed definition of u u=x-2, in 2 places, saving 4 characters (228, shorter than original solution)
• removed function f and moved functionality into main, saved 28 characters (200)
• removed using namespace std; and used std::cout, std::cin, and "\n", saved 5 characters (195)
• changed std::cin>>n;for(;n>0;--n) to for(std::cin>>n;n;--n), saved 3 characters (192)
• removed typedef long long L; since its only used in one place now, saved 12 characters (180)
• removed 4 parens from statements like ((x*2)-2), saved 4 characters (176)
• removed brackets from loop by using commas instead of semicolons, compressed loop condition from std::cin>>n;n;--n to std::cin>>n;n--;, saved 3 characters (173)

Answer 5

Go

package main
import "fmt"
func main() {
    var N int
    fmt.Scanln(&N)
    for ; N > 0; N-- {
        var m, n int64
        fmt.Scanln(&m, &n)
        grid := m*n
        total := grid*(grid-1)
        if m > 2 && n > 1 {
            total -= (m - 2)*(n - 1) * 4
        }
        if n > 2 && m > 1 {
            total -= (n - 2)*(m - 1) * 4
        }
        fmt.Println(total)
    }
}

Explanation

• grid is number of grid
• total is initialized as all the possible ways the knights could be placed. Since they have to be different grids, grid * (grid - 1)
• Now we exclude the number of ways they may attack each other
  • Their position could be two squares difference horizontally and one square vertically. The number of ways is (m - 2)*(n - 1) when m > 2 && n > 1. The left can be higher of lower then the right, so *2. White and black are exchangable, so *2 again.
  • Similar to the situation for two squares vertically and one square hotizontally

Timing

• 4 int64 multiplication and 7 int64 plus/minus operation, should be done in 1 second.