Salut la toata lumea.
Am o rezolvare in O(N^2) pe care cred ca o pot si demonstra prin inductie, cu toate acestea iau 0 puncte. Imi puteti spune va rog daca afirmatia mea e corecta? Recursivitatea este asa:
- Daca pe pozitia A[ i ][ j ] este 0 si pe A[ i-1 ][ j ] == 0 si A[ i ][ j-1 ] == 0 ( adica si sus si la stanga sa fie 0 ) recursivitatea este A[ i ][ j ] = A[ i-1 ][ j ] + A[ i ][ j-1 ] + 1 - A[ i-1 ][ j-1 ]
- Daca A[ i-1 ][ j ] ( cea de deasupra ) e 1 atunci A[ i ][ j ] va lua doar numarul de 0-uri de la stanga
- Daca A[ i ][ j-1 ] (cea de la dreapta ) e 1 atunci A[ i ][ j ] va lua doar numarul de 0-uri de deasupra
Este corecta aceasta rezolvare?
Eu am testat aceasta rezolvare pe mai multe teste, chiar am si verificat cu o solutie brute force, si toate imi dau corect.
De ex pentru testul :
18
010101010101010111
111000101011010111
111000101011010101
111000101011111010
001010110101010101
111000101011010100
111000101011010100
111000101011111000
001010110101010100
111000101011010100
111000101011010100
111000101011111000
001010111110001000
101101011110001000
101101011110001000
101111100010101100
000000000000000000
000000000000000000
Da 1250 ?
Va rog frumos sa ma ajutati.
Multumesc!