PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Brute Force
PROBLEM:
You want to place a rook on a chessboard so that the sum of the values written on the squares it attacks is maximal.
EXPLANATION:
The naive solution is to try placing a rook on every square and find the score for each possibility by looping through all the squares it attacks. This solution works in O(n^{3}) time because there are O(n^2) squares to try and for each square we take O(n) time to find the score.
We can improve the solution by noting that there is no need to iterate through all squares that can be attacked by the rook. Let r_{i} and c_{i} denote the sum of values on the squares in the i-th row and i-th column respectively. Then, the score obtained when the rook is on (i, j) is just r_{i} + c_{j} - a_{i, j}.
Thus, with O(n^2) precomputation, the answer can be found in O(n^2) time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.