Minimum Operations to Form Letter Y

Moderate

0/80

0 upvote

Problem statement

You are given a 0-indexed n x n grid, where n is always an odd number. Each cell in the grid contains a value of 0, 1, or 2.

A "Letter Y" shape is defined on this grid by three sets of cells:

1) The main diagonal from the top-left (0,0) to the grid's center.
2) The anti-diagonal from the top-right (0, n-1) to the grid's center.
3) The vertical line from the grid's center down to the bottom edge.

The grid is considered to have a "Letter Y" written on it if it meets three conditions:

1) All cells belonging to the Y shape have the same value.
2) All cells not belonging to the Y shape have the same value.
3) The value of the Y cells is different from the value of the non-Y cells.

In one operation, you can change the value of any single cell to 0, 1, or 2. Your task is to find the minimum number of operations required to make the grid satisfy the "Letter Y" conditions.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer n, the size of the grid.

The next n lines each contain n space-separated integers, representing a row of the grid.

Output Format:

Your function should return a single integer representing the minimum number of operations.

Note:

The solution involves iterating through all possible valid final configurations. A valid configuration is defined by a pair of values (y_val, non_y_val) where y_val != non_y_val.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

Y-cells: (0,0), (1,1), (2,1), (0,2). Wait, that's not right. (0,0),(1,1) from main diag. (0,2),(1,1) from anti-diag. (1,1),(2,1) from vertical.
Correct Y-cells: (0,0), (1,1), (2,1), (0,2). Still not quite right. It's (0,0),(0,2),(1,1),(2,1).
Final Y-cells: (0,0), (1,1), (0,2) for the 'V' part, and (2,1) for the stem. (1,1) is the center. So Y-cells are (0,0), (0,2), (1,1), (2,1). The original values are 1, 2, 1, 1.
Let's try to make Y-cells 1 and non-Y cells 0.
  Y-cells to change: (0,2) from 2 to 1 (1 op).
  Non-Y cells: (0,1),(1,0),(1,2),(2,0),(2,2). Values are 2, 1, 0, 0, 0. We want them to be 0.
  Non-Y cells to change: (0,1) from 2 to 0 (1 op), (1,0) from 1 to 0 (1 op).
  Total ops = 1 + 1 + 1 = 3. This is a possible answer. The minimum can be shown to be 3.

Expected Time Complexity:

The expected time complexity is O(N^2).

Constraints:

3 <= n <= 49
n is odd.
0 <= grid[i][j] <= 2

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Minimum Operations to Form Letter Y

Console