2429 - matrice9

Fie A o matrice dreptunghiulară de numere întregi cu N linii numerotate de la 1 la N şi M coloane numerotate de la 1 la M. În matricea A oricare două elemente consecutive de pe aceeaşi linie sunt distincte.

Se defineşte un şir valid de numere întregi ca fiind fie un şir crescător, fie un şir descrescător, fie un şir crescător concatenat cu un şir descrescător, fie un şir descrescător concatenat cu unul crescător. Exemple de şiruri valide sunt: 1 2 3 7, 8 5 2 1, 3 5 6 2, 4 1 5 6.

Se defineşte o submatrice a lui A de coordonate (l1, c1, l2, c2) ca fiind matricea formată din toate elementele A(i,j), cu l1 ≤ i ≤ l2 şi c1 ≤ j ≤ c2.

O submatrice a lui A este validă dacă liniile sale sunt şiruri valide.

Atenţie! O submatrice validă poate avea pe o linie un şir crescător de numere, pe a doua un şir descrescător, pe a treia un şir crescător concatenat cu unul descrescător etc. Deci, liniile unei submatrice valide nu trebuie să fie neapărat şiruri de acelaşi tip.

Aria unei submatrice este egală cu numărul de elemente din care este formată submatricea.

Cerința

Se cere să se găsească o submatrice validă a lui A de arie maximă.

Date de intrare

Fișierul de intrare matrice9IN.txt conține pe prima linie numerele N şi M, separate prin spaţiu. Pe fiecare dintre următoarele N linii se află câte M numere întregi separate prin câte un spaţiu, reprezentând elementele matricei A.

Date de ieșire

Fișierul de ieșire matrice9OUT.txt va conţine o singură linie pe care vor fi scrise coordonatele l1, c1, l2, c2 (în această ordine şi separate prin câte un spaţiu) ale unei submatrice valide de arie maximă. În cazul în care există mai multe soluţii cu arie maximă, se va afişa oricare dintre ele.

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• 70% din teste vor avea N, M ≤ 600
• Elementele matricei A sunt numere întregi din intervalul [-30000, 30000].

Exemplul 1:

matrice9IN.txt

2 6
1 2 5 7 9 10
3 4 3 5 1 10

matrice9OUT.txt

1 1 2 3

Explicație

Aria maximă este 6. O altă soluţie de arie maximă ar putea fi 1 1 1 6 sau 1 2 2 4 sau 1 3 2 5 sau 1 4 2 6.

Exemplul 2:

matrice9IN.txt

1001 1001
1 2 5 7 9 10
3 4 3 5 1 10

matrice9OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> N_MAX = 1024 SEQ_UNKNOWN = 0 SEQ_INCREASING = 1 SEQ_DECREASING = 2

N, M = 0, 0 A = [[0] * N_MAX for _ in range(N_MAX)]

Inaltime = [0] * N_MAX Tip = [SEQ_UNKNOWN] * N_MAX Inceput = [0] * N_MAX Contor = 0 Stiva = [0] * N_MAX Top = [0] * N_MAX

CelMaiBun, CelMaiBun1l, CelMaiBun1c, CelMaiBun2l, CelMaiBun2c = 0, 0, 0, 0, 0

def verifica_restrictiile():

   if not (1 <= N <= 1000 and 1 <= M <= 1000):
       with open("matrice9OUT.txt", "w") as fisier:
           fisier.write("Datele nu corespund restrictiilor impuse\n")
       return False
   return True

def rezolva():

   global N, M, A, Inaltime, Tip, Inceput, Contor, Stiva, Top, CelMaiBun, CelMaiBun1l, CelMaiBun1c, CelMaiBun2l, CelMaiBun2c

   for j in range(M):
       for i in range(N + 1):
           if i == N:
               Inaltime[i] = 0
           elif j == 0:
               Inaltime[i] = 1
           elif Tip[i] == SEQ_UNKNOWN:
               Tip[i] = SEQ_INCREASING if A[i][j] > A[i][j - 1] else SEQ_DECREASING
               Inaltime[i] += 1
           elif Tip[i] == SEQ_INCREASING:
               if A[i][j] < A[i][j - 1]:
                   Inaltime[i] = j - Inceput[i] + 1
                   Inceput[i] = j - 1
                   Tip[i] = SEQ_DECREASING
               else:
                   Inaltime[i] += 1
           elif Tip[i] == SEQ_DECREASING:
               if A[i][j] > A[i][j - 1]:
                   Inaltime[i] = j - Inceput[i] + 1
                   Inceput[i] = j - 1
                   Tip[i] = SEQ_INCREASING
               else:
                   Inaltime[i] += 1

           varf = i
           while Contor > 0 and Inaltime[i] <= Stiva[Contor - 1]:
               varf = Top[Contor - 1]
               if Stiva[Contor - 1] * (i - varf) > CelMaiBun:
                   CelMaiBun = Stiva[Contor - 1] * (i - varf)
                   CelMaiBun1l, CelMaiBun2l = varf, i - 1
                   CelMaiBun1c, CelMaiBun2c = j - Stiva[Contor - 1] + 1, j
               Contor -= 1

           if Inaltime[i] > 0:
               Stiva[Contor] = Inaltime[i]
               Top[Contor] = varf
               Contor += 1

   return CelMaiBun1l + 1, CelMaiBun1c + 1, CelMaiBun2l + 1, CelMaiBun2c + 1

def citeste_rezolva():

   global N, M, A
   with open("matrice9IN.txt", "r") as fisier:
       N, M = map(int, fisier.readline().split())
       if not verifica_restrictiile():
           return
       for i in range(N):
           A[i] = list(map(int, fisier.readline().split()))

   rezultat = rezolva()

   with open("matrice9OUT.txt", "w") as fisier:
       fisier.write(f"{rezultat[0]} {rezultat[1]} {rezultat[2]} {rezultat[3]}\n")

if __name__ == "__main__":

   citeste_rezolva()

</syntaxhighlight>