3632 - Matrix replace

Aky, un elev pasionat de matematică, analiza într-o zi curios o matrice pătratică de dimensiune N. Acesta a observat că această matrice are anumite submatrice, la rândul lor pătratice, ale căror elemente sunt egale. Astfel și-a pus o întrebare: pentru o matrice dată, care este submatricea pătratică de dimensiune maximă a acesteia cu toate elementele egale pe care o pot obține, știind că am voie să schimb valoarea a maxim K elemente din matricea dată cu orice valoare consider și care este numărul minim de elemente ce trebuie schimbate pentru a obține o astfel de submatrice. Acesta ar rezolva problema de unul singur, dar este ocupat chiar acum deci vă cere vouă ajutorul!

Date de intrare

Fișierul de intrare matrix_replace.in conține pe prima linie numerele N și K, reprezentând dimensiunea matricei inițiale, respectiv câte elemente am voie maxim să schimb din aceasta, iar pe următoarele N linii câte N numere naturale reprezentând elementele matricei inițiale.

Date de ieșire

Fișierul de ieșire matrix_replace.out va conține pe prima linie numărele D M, reprezentând dimesiunea maximă a unei submatrice cu proprietatea din enunț, respectiv numărul minim de elemente ale căror valori trebuie schimbate pentru a obține această submatrice.

Restricții și precizări

• 1 ≤ N ≤ 150
• 0 ≤ K ≤ N * N
• elementele matricei vor fi numere naturale mai mici sau egale ca 100
• pentru o matrice dată, o submatrice a acesteia având coordonatele colțului stânga-sus x1 y1 și coordonatele colțului dreapta-jos x2 y2 este formată din toate elementele din matrice având indicele liniei în intervalul [x1, x2] și indicele coloanei în intervalul [y1, y2]. Această submatrice se numește submatrice pătratică dacă are același număr de linii și coloane
• Subtask 1: pentru 20 de puncte N ≤ 20
• Subtask 2: pentru alte 10 de puncte numărul de valori distince din matrice este 2, K = 0 și N ≤ 150
• Subtask 3: pentru alte 20 de puncte pot exista oricâte valori distincte în matrice, N ≤ 100, K ≤ N * N și valoarea maximă din matrice este mai mică sau egală decât 10
• Subtask 4: pentru restul punctelor se păstrează condițiile inițiale: 1 ≤ N ≤ 150, 0 ≤ K ≤ N * N și elementele matricei vor fi numere naturale nenule mai mici sau egale ca 100

Exemplu:

matrix_replace.in

3 5
1 2 3
4 5 6
7 8 9

matrix_replace.out

2 3

Explicație

Putem de exemplu obține o submatrice pătratică de dimenisiune 2 schimbând valorile elementelor de coordonate: 1 2, 2 1, respectiv 2 2 cu 1. Observăm că numărul minim de schimbări de elemente este 3, deci în acest caz K = 5, 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

1. 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>