BWKNIGHT - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

In the general case, there are a couple of types of positions on the board : Positions from which a knight attacks two squares on the board, those from which it attacks three squares, and so on. So we just need to count the number of squares from which a knight would attack exactly X squares, and add 2 * N * M * (N * M-X-1) to the answer. We multiply by 2 because the knights are distinct. Cases with n = 1,2 and 3 might have to be handled seperately depending on how you prefer to think of the problem. Finally note that the answer for the larger test cases do not fit in a 64 bit integer, and hence simple big integer operations are needed.

another way to achieve the solution:

consider a n*m grid . { m rows and n columns }

focus on 1st row . for this row there are 2(n-2) fatal positions in second row. for second row we have 2(n-2) fatal positions in 3rd row. this goes on for all rows except the last row

so we have 2*(n-2)(m-1) ways which are fatal . looking closely we found that 1st row also has 2(n-1) fatal positions in 3rd row and second row has 2*(n-1) fatal positions in 5th row . this goes on till the third last row so we have

2*(n-1)*(m-2) which are fatal

total ways = twice of ( 2*(n-2)(m-1) + 2(n-1)*(m-2) ) twice because we have black and white knight .

so we have 4x ( (n-2)(m-1) + (n-1)(m-2) )

this is only when both n and m are greater than or equal to 2 otherwise we can calculate the answer in trivial manner as there is no fatal position.

accepted solution based on this method : http://www.codechef.com/viewsolution/2055005

5 Likes

^ awesome insight, mate.

https://www.codechef.com/viewsolution/8617076 whats wrong with my code.!!

@vishalrox n,m can be upto 100000 so your total=total*(total-1) can be ~ 10^20 which can not be stored in long long int or unsigned long long int. Try to use array to store values.