Блог пользователя EasonCookie197

Автор EasonCookie197, 18 месяцев назад, По-английски

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 x points.
  • 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 y points.

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.

My initial idea
  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

»
18 месяцев назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

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

»
18 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This much hard university interview...

  • »
    »
    18 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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)

»
18 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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?

  • »
    »
    18 месяцев назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    Are you certain you never place down red pieces? For example:

    x=y=1
    n=2
    22
    22
    

    Isn't the maximum here 8? If you don't place red pieces, then you get at most 4. Correct me if I am wrong.

    • »
      »
      »
      18 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You are correct.

    • »
      »
      »
      18 месяцев назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

»
18 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Spoiler