I was asked an interesting problem on an university interview. (I won't tell you what university it was.) However, I couldn't come up with an effective solution. I would appreciate if anyone has any thoughts or approaches!
Statement
You are given two integers x y, and a n by n chessboard, each square is given either black, white, or red. (Denoted by 0,1,2) You also have an infinite amount of black, white, and red chess pieces. You are to put exactly one piece on each of the squares. You have to calculate the maximum score possible. The score is calculated as follows:
- For each square, if the color of the square is same as the color of the piece, you get
xpoints. - For each unordered pair of squares that are adjacent (up, down, left, right) if the color of the chess pieces are the same, you get
ypoints.
Constraints
$$$n \le 100$$$ $$$x,y \le 10^9$$$
Sample Input
n=3 x=4 y=2
110
001
100
Sample Output
46
Explanation:
We can put the chess pieces as follows:
110
000
000
This way we have 7 chess pieces that have the same color as the square color, giving us 7x4=28 points. We also have 1 pair of white and 8 pairs of black pieces that are adjacent, giving us 9x2=18 points. Total is 46.
I have an idea for that since these are unordered_pair , we just use (i-1, j) , (i , j-1) so that repetation is not there in calculation dp[i][j][3] Can work??
This much hard university interview...
I think what they intended is that they want to see how the interviewees responded and approached difficult problems on the spot, because it is nearly impossible to solve problems like these in such a short time (less than 10 minutes)
Seems like a (more or less) standard min-cut problem.
First of all, never put red pieces. Then, form a bipartite graph (bipartition on checkerboard coloring). Add edges from source to all white squares of cost $$$x$$$ and from all black squares to sink of cost $$$x$$$. Also add edges from every white square to every black neighbor with cost $$$y$$$. Then, the minimum cut in this weighted digraph should be the solution.
Proof (I hope it’s correct):
If you consider a cut, and put a white piece iff the cell is in the same side of cut as source, then the cost of the cut is exactly what you have to subtract from the best possible cost, with one exception — when a black piece is put on a white square and a white piece to a neighboring black square won’t subtract $$$y$$$; but that will never happen in the best assignment if $$$x>0$$$ — try to think of why.
On a side note, who in their right mind asks min-cut problems on university interviews?
Are you certain you never place down red pieces? For example:
Isn't the maximum here
8? If you don't place red pieces, then you get at most4. Correct me if I am wrong.You are correct.
Sorry, I thought the chessboard would be colored like an actual chessboard. I guess I was just solving a much easier variant of this problem, lol.
I think linear programming can solve this problem. Let Z_{i,j,k} denote if we pick the cell i,j to have color k, and then relax the constraints to 0<=Z<=1 and sum_k(Z_{i,j,k})=1. Then if we have a fractional solution we can increase and decrease some variables to make them integers while at the same time not getting a worse solution.
Assuming that we can use an interior point method, it solves the problem, but i think it is overkill and there probably is a simpler solution using max flow (there is one if we only have black and white cells, just link all black cells to source with capacity x, all white cells to sink with capacity x and all adjacent cells woth capacity y and there is an equivalence between the cut and the solution)