Gözəl şəbəkə!#12209

Gözəl şəbəkə! (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Hər bir gridin və sütunun cəmini $O (n^{2})$ \mathcal{O}(n^2)-də hesablayın və onları $map$ ilə xəritələyin, sonra hər diaqonal üçün bütün alt-massiv cəmlərini yoxlayın və onların artıq $map$ -da hesablanıb-hesablanmadığını yoxlayın, bu, prefiks cəmi ilə və ya sadəcə cəmləri yeniləməklə və hesablayarkən onları saxlamaqla edilə bilər.

def solve():
    n=int(input())
    a = [[0]*n for _ in range(n)]
    mp={}
    for i in range(n):
        a[i]=list(map(int,input().split()))
    for i in range(n):
        sum,sum2=0,0
        for j in range(n):
            sum+=a[i][j]
            sum2+=a[j][i]
        mp[sum]=1
        mp[sum2]=1
    d1,d2=[],[]
    sd1,sd2=0,0
    for i in range(n):
        sd1+=a[i][i]
        sd2+=a[i][n-i-1]
        d1+=[sd1]
        d2+=[sd2]
    for i in range(n):
        for j in range(i,n):
            try:
                if(mp[d1[j]-d1[i]+a[i][i]]):
                    print("BƏYƏNİR")
                    return
            except:
                pass
            try:
                if(mp[d2[j]-d2[i]+a[i][n-i-1]]):
                    print("BƏYƏNİR")
                    return
            except:
                pass
    print("YOX")
for _ in range(int(input())):
    solve()

Komplekslik $O (n^{2})$ \mathcal{O}(n^2)