RaulOtet: Pagină nouă: 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...

2024-07-31T12:45:54Z

Pagină nouă: Aky, un elev pasionat de matematică, analiza într-o zi curios o matrice pătratică de dimensiune <code>N</code>. 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 <code>K</code> elemente...

New page

Aky, un elev pasionat de matematică, analiza într-o zi curios o matrice pătratică de dimensiune <code>N</code>. 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 <code>K</code> 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 <code>matrix_replace.in</code> conține pe prima linie numerele <code>N</code> și <code>K</code>, reprezentând dimensiunea matricei inițiale, respectiv câte elemente am voie maxim să schimb din aceasta, iar pe următoarele <code>N</code> linii câte <code>N</code> numere naturale reprezentând elementele matricei inițiale.

= Date de ieșire =
Fișierul de ieșire <code>matrix_replace.out</code> va conține pe prima linie numărele <code>D M</code>, 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 =

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

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

3632 - Matrix replace - Revision history