Problemi 040

Kërkesa

Një listë L ka N numra të plotë të ndryshëm nga zero. Një nën-listë quhet alternuese nëse çdo dy elemente fqinje të listës kanë shenja të kundërta (njëra pozitive dhe tjetra negative).

Për çdo element të listës L gjeni gjatësinë e nën-listës alternuese më të madhe që fillon me atë element.

Referenca: https://www.codechef.com/problems/ALTARAY

Shembull

$ cat input.txt
3
4
1 2 3 4
4
1 -5 1 -5
6
-5 -1 -1 2 -2 -3

$ python3 prog.py < input.txt
1 1 1 1
4 3 2 1
1 1 3 2 1 1

Zgjidhja 1

T = int(input())
for t in range(T):
    N = int(input())
    L = list(map(int, input().split()))
    P = []
    for i in range(N):
        k = 1
        while i+k < N and L[i+k-1]*L[i+k] < 0:
            k += 1
        P.append(k)
    print(*P)

Sqarime

Për çdo element të listës gjejmë se sa elemente alternuese janë mbas tij. Kushtin i+k < N e përdorim për tu siguruar që indeksi (treguesi) i+k nuk del jashtë listës. Kurse kushtin x*y < 0 e përdorim për të kontrolluar që dy elementë kanë shenja të kundërta.

Komanda print(*P) përdoret për të printuar elementet e një liste, të ndarë me vende bosh.

Zgjidhja 2

T = int(input())
for t in range(T):
    N = int(input())
    L = list(map(int, input().split()))
    P = []
    for i in range(N):
        P.append(0)
    L.append(L[-1])
    i = N
    while i > 0:
        if L[i-1] * L[i] < 0:
            P[i-1] = P[i] + 1
        else:
            P[i-1] = 1
        i -= 1
    print(*P)

Sqarime

Kjo zgjidhje bazohet në faktin që gjatësitë e nën-listave më të mëdha alternuese për dy elemente të një-pas-njëshëm i dhe i+1 kanë lidhje me njëra-tjetrën. Nëse elementët i dhe i+1 kanë shenja të kundërta, atëherë gjatësia për elementin i është një më tepër sesa për elementin i+1. Nëse kanë shenja të njëjta, atere është 1.

Kështu që zgjidhja bëhet duke filluar nga fundi i listës dhe duke llogaritur gjatësinë për një element duke u bazuar te gjatësia e elementit pasardhës. Elementi i fundit i listës përbën një rast të veçantë, sepse nuk ka element para-ardhës, kështu që ne shtojmë një element fallco në fund të listës, thjesht për të shmangur trajtimin e tij si rast i veçantë.

Kjo zgjidhje mund të duket pak më e vështirë për tu konceptuar në krahasim me zgjidhjen e parë, por në fakt është më e shpejtë. Zgjidhja e parë është zgjidhje katrore (ose e rendit \(O(N^2)\)) meqenëse kemi dy cikle brenda njëri-tjetrit. Kurse kjo zgjidhje është lineare (ose e rendit \(O(N)\)) meqenëse kemi vetëm një cikël.

Që zgjidhja e dytë është më e shpejtë mund ta provoni edhe duke i provuar këto zgjidhje këtu: https://www.codechef.com/submit/ALTARAY Zgjidhja e parë nuk e kalon testin sepse është shumë e ngadalshme, kurse e dyta po.

Detyra

Gjeni gjatësinë e nën-listës alternuese më të madhe të listës L.

Shembull

$ cat input.txt
3
4
1 2 3 4
4
1 -5 1 -5
6
-5 -1 -1 2 -2 -3

$ python3 prog.py < input.txt
1
4
3