Editing 3632 - Matrix replace (section)

= Exemplu: =
<code>matrix_replace.in</code>
 3 5
 1 2 3
 4 5 6
 7 8 9
<code>matrix_replace.out</code>
 2 3

=== Explicație ===
Putem de exemplu obține o submatrice pătratică de dimenisiune <code>2</code> schimbând valorile elementelor de coordonate: <code>1 2</code>, <code>2 1</code>, respectiv <code>2 2</code> cu <code>1</code>. Observăm că numărul minim de schimbări de elemente este <code>3</code>, deci în acest caz <code>K = 5</code>, numărul de schimbări maxime pe care le putem efectua, nu este atins.

<syntaxhighlight lang="python" line="1">
def preprocess_matrix(matrix, N):
    # Compute the prefix sum matrix
    prefix_sum = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(N):
            prefix_sum[i + 1][j + 1] = matrix[i][j] + prefix_sum[i + 1][j] + prefix_sum[i][j + 1] - prefix_sum[i][j]
    return prefix_sum

def num_changes_to_uniform(matrix, prefix_sum, N, size, top, left):
    # Calculate the number of changes to make the submatrix uniform
    total_elements = size * size
    sum_elements = (prefix_sum[top + size][left + size] - prefix_sum[top + size][left]
                    - prefix_sum[top][left + size] + prefix_sum[top][left])
    # The most frequent element will be the target, so calculate changes needed
    # Assume the target value is 1
    changes_if_target_1 = total_elements - sum_elements
    # Assume the target value is 0
    changes_if_target_0 = sum_elements
    return min(changes_if_target_1, changes_if_target_0)

def find_max_square_submatrix(matrix, N, K):
    prefix_sum = preprocess_matrix(matrix, N)
    
    max_size = 0
    min_changes = float('inf')
    
    for size in range(1, N + 1):
        for i in range(N - size + 1):
            for j in range(N - size + 1):
                changes = num_changes_to_uniform(matrix, prefix_sum, N, size, i, j)
                if changes <= K:
                    if size > max_size:
                        max_size = size
                        min_changes = changes
                    elif size == max_size:
                        min_changes = min(min_changes, changes)
                        
    return max_size, min_changes

# Exemplu de utilizare
N = 4
K = 3
matrix = [
    [1, 0, 0, 1],
    [0, 1, 0, 0],
    [1, 1, 1, 0],
    [1, 0, 1, 1]
]

max_size, min_changes = find_max_square_submatrix(matrix, N, K)
print(f"Dimensiunea maximă: {max_size}")
print(f"Numărul minim de schimbări: {min_changes}")
</syntaxhighlight>