6
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I tidied up the formatting a little on your question, I hope you don't mind. Feel free to roll back the edit if you don't like it. \$\endgroup\$ – Griffin Aug 27 '12 at 11:09
  • \$\begingroup\$ @Griffin i am new here thanks for the edit ,please correct me if i make mistakes in future \$\endgroup\$ – BlueBerry - Vignesh4303 Aug 27 '12 at 12:13
  • \$\begingroup\$ You're going to want to put a winning criteria on your question before it gets down-voted by all the boring people on this site. You need to have a fairly objective way of choosing a winner. e.g. shortest code, fastest running code for a given input or some point system of your choosing. \$\endgroup\$ – Griffin Aug 27 '12 at 12:40
  • 2
    \$\begingroup\$ Do we need to worry about board dimensions <= 0? \$\endgroup\$ – Matt Aug 27 '12 at 12:41
  • 1
    \$\begingroup\$ Question appears to be copied from here without any attribution. \$\endgroup\$ – Paul R Sep 1 '12 at 14:41
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ I can't test yours at the moment, but my solution that was based on yours gives incorrect results for boards of size 1xn, I suspect yours does as well. \$\endgroup\$ – Matt Aug 27 '12 at 12:13
  • \$\begingroup\$ @matt, you are correct, good catch. Also I've just noticed we've come up with the same fix. \$\endgroup\$ – Griffin Aug 27 '12 at 12:25
  • \$\begingroup\$ @Griffin I don't know much of the Octave, but can't you use end instead of endfor? \$\endgroup\$ – defhlt Aug 27 '12 at 23:33
  • \$\begingroup\$ @ArtemIce Yes you're right, when I was learning Octave I just assumed I had to end loops like that, silly me. Though I've just realised I don't even need a loop - huge performance increase. \$\endgroup\$ – Griffin Aug 28 '12 at 0:13
  • \$\begingroup\$ @griffin excellent answer ,i ll keep my question alive for more solutions if it's your's best then i ll accept it !!! \$\endgroup\$ – BlueBerry - Vignesh4303 Aug 28 '12 at 8:16
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ +1 for the a*b*(a*b-1), I forgot the simplify the maths. I might pinch that... \$\endgroup\$ – Griffin Aug 27 '12 at 12:42
  • \$\begingroup\$ (a-2)*(b-1)+(a-1)*(b-2) can be expanded and simplified to 2*a*b-3*(a+b)+4 \$\endgroup\$ – Griffin Aug 28 '12 at 2:18
3
\$\begingroup\$

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]]

graph

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

AdjacencyMatrix[k] // MatrixForm

adjacency

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.

enter image description here

\$\endgroup\$
  • 1
    \$\begingroup\$ Do your timings include time to ouput (which I don't think they should)? Because you need to be able to calculate answers for grids up to 100000x100000. \$\endgroup\$ – Griffin Aug 27 '12 at 16:38
  • \$\begingroup\$ Time to output is not included. (The ; suppresses that.) The routine seems to be relatively slow. \$\endgroup\$ – DavidC Aug 27 '12 at 16:42
  • \$\begingroup\$ Why don't you take the conditionals out? Octave (pretty much MATLAB with some syntactic sugar I prefer) is interpreted too. Maybe using a table is slowing you down? \$\endgroup\$ – Griffin Aug 27 '12 at 19:05
  • \$\begingroup\$ That was my first thought but the timing without the conditionals was just the same. I'll try using an alternative to Table. Thanks. \$\endgroup\$ – DavidC Aug 27 '12 at 19:08
  • \$\begingroup\$ @Griffin. The timing is slightly faster (2x) with Do loops and no conditionals. There must be a better way. \$\endgroup\$ – DavidC Aug 27 '12 at 19:33
1
\$\begingroup\$

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)
\$\endgroup\$
  • 1
    \$\begingroup\$ This gives the wrong result for boards of size 1xn \$\endgroup\$ – Matt Aug 28 '12 at 17:19
  • \$\begingroup\$ @Matt: yeah I forgot to subtract when checking for positivity. fixed now \$\endgroup\$ – Wug Aug 28 '12 at 17:49
  • \$\begingroup\$ Alright, I think we're maximally golfed. \$\endgroup\$ – Wug Aug 28 '12 at 19:18
  • \$\begingroup\$ I don't know too much C++ but can't y-2<0?0:y-2 be changed to max(y-2,0)? \$\endgroup\$ – Griffin Aug 28 '12 at 19:29
  • \$\begingroup\$ @Griffin: I'd need to #include<algorithm> and use std::max. Good suggestion though. I always forget about little things like that that the STL provides for me and roll my own wheel. \$\endgroup\$ – Wug Aug 28 '12 at 19:30
0
\$\begingroup\$

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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.