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-josx2 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 puncteN ≤ 20
- Subtask 2: pentru alte
10
de puncte numărul de valori distince din matrice este2
,K = 0
șiN ≤ 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ât10
- 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 ca100
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.
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}")