UVa 11538

From Algorithmist
Jump to navigation Jump to search

11538 - Chess Queen[edit]

Summary[edit]

Simple math, summations, chess board. Count the number of how many ways two queens can be in attacking position in (M x N) board.

Explanation[edit]

If ROW = 1, then the two queens can be placed in {COLUMN * (COLUMN - 1)} ways. So, if the queen can attack only horizontally, then the number of ways is {ROW * COLUMN * (COLUMN - 1)}. Similarly, if the queen can attack only vertically, then the number of ways is {COLUMN * ROW * (ROW - 1)}. Now, if we don't consider the diagonal attacks, the number of ways is {ROW * COLUMN * (COLUMN - 1) + COLUMN * ROW * (ROW - 1)}. Number of cells in a diagonal path will increase by time, after some time it will decrease. For example, MINIMUM := MIN(ROW, COLUMN), MAXIMUM := MAX(ROW, COLUMN) Then number of cells in a diagonal path will increase from 1 to MINIMUM, will remain same from (MINIMUM + 1) to MAXIMUM, then will decrease, same as increase. Calculate the number of ways for increasing diagonal cells, then add the number of ways for diagonally cells which remain same, then similarly calculate for the decreasing cells. Then multiply the sum by 2, as there are two diagonals. Finally, the result will have the sum of numbers of ways for horizontal, vertical & two diagonal sums.

Optimizations[edit]

Here, while calculating the number of ways in increasing diagonal cells, we may code a loop, but that's time consuming and may cross time limit. That's why, we can use the concept of series summation instead of loop. Here, number of ways is {n * (n - 1)}, where there's n cells in a line diagonally. Then assume a series of n terms where every term is n*(n-1). n = {1, 2, 3, . . . . . }


So, summation of the series will have a sum where n can be from 1 to (MINIMUM - 1), that is there are n terms in the series. The sum of first n terms of the series is {n*(n+1)*(2*n+1)/6 - n*(n+1)/2 = n*(n+1)*(n-1)/3}, here n = MINIMUM - 1.

Because, if we consider x = MINIMUM, in case of N being equal to M, the diagonal cells of (M x M) board will be added twice and will cause wrong output.

Notes[edit]

  • To be careful in calculating sum of the numbers of ways with simple math.
  • A 64-bit integer type is needed.
  • Input is terminated by a line containing two zeroes. These two zeroes need not be processed.

Input[edit]

2 2
100 223
2300 1000
0 0

Output[edit]

12
10907100
11514134000

Solutions[edit]