Problemi 058

Kërkesa

Në një listë me numra natyrorë përkufizojmë funksionin prefixSum(i) si shumën e numrave të listës nga fillimi e deri në pozicionin i, dhe funksionin suffixSum(i) si shumën e numrave të listës nga pozicioni i e deri në fund.

Gjeni indeksin më të vogël i për të cilën shuma prefixSum(i) + suffixSum(i) ka vlerën më të vogël.

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

Shembull

$ cat input.txt
2
3
1 2 3
4
2 1 3 1

$ python3 prog.py < input.txt
1
2

Po të llogarisim shumat, duket që i-ja që jep vlerën më të vogël është 1:

prefixSum(1) + suffixSum(1) = 1 + 6 = 7
prefixSum(2) + suffixSum(2) = 3 + 5 = 8
prefixSum(3) + suffixSum(3) = 6 + 3 = 9

Vlera më e vogël e shumës është 8, dhe vlera më e vogël e i-së që jep shumën më të vogël është 2:

prefixSum(1) + suffixSum(1) = 2 + 7 = 9
prefixSum(2) + suffixSum(2) = 3 + 5 = 8
prefixSum(3) + suffixSum(3) = 6 + 4 = 10
prefixSum(4) + suffixSum(4) = 7 + 1 = 8

Zgjidhja 1

def prefixSum(L, i):
    s = 0
    j = 0
    while j <= i:
        s += L[j]
        j += 1
    return s

def suffixSum(L, i):
    s = 0
    j = i
    while j < len(L):
        s += L[j]
        j += 1
    return s

import math

T = int(input())
for t in range(T):
    n = int(input())
    L = [int(i) for i in input().split()]

    # gjej vlerën më të vogël të shumës
    s_min = math.inf
    for i in range(n):
        s = prefixSum(L, i) + suffixSum(L, i)
        if s < s_min:
            s_min = s

    # gjej i-në më të vogël që jep vlerën më të vogël të shumës
    for i in range(n):
        s = prefixSum(L, i) + suffixSum(L, i)
        if s == s_min:
            print(i+1)
            break

Sqarime

Zgjidhja është me dy hapa, në fillim gjejmë vlerën më të vogël të shumës, pastaj gjejmë i-në më të vogël që jep shumën më të vogël.

Kjo zgjidhje e ka kohën \(O(N^2)\) (pse?). Për vlera të vogla të N-së (p.sh. deri në 100) kjo është zgjidhje e pranueshme, por për vlera të mëdha është shumë e ngadaltë. Këtë mund ta verifikojmë edhe këtu: https://www.codechef.com/submit/CHEFSUM, ku kjo zgjidhje merr vetëm 20 pikë (nga 100 të mundshme). Kjo për shkak sepse kalon vetëm nëntestin me vlera të vogla të N-së, por jo atë me vlera të mëdha.

Zgjidhja 2

```python def prefixSum(L, i): s = 0 j = 0 while j <= i: s += L[j] j += 1 return s

def suffixSum(L, i): s = 0 j = i while j < len(L): s += L[j] j += 1 return s

import math

T = int(input()) for t in range(T): n = int(input()) L = [int(i) for i in input().split()] s_min = math.inf i_min = n i = n-1 while i >= 0: s = prefixSum(L, i) + suffixSum(L, i) if s <= s_min: s_min = s i_min = i i -= 1 print(i_min + 1) ```

Sqarime

Kjo zgjidhje ka një përmirësim në lidhje me zgjidhjen e parë, sepse vlera më e vogël e shumës dhe vlera më e vogël e i-së gjenden njëkohësisht, me të njëjtin cikël. Pra në vend të dy cikleve tani kemi vetëm një. Kjo e shkurton përgjysëm kohën e punës së programit, por gjithsesi është krejtësisht e pafuqishme për të mposhtur rritjen kuadratike të \(O(N^2)\). Këtë e tregon edhe testimi, ku përsëri kjo zgjidhje arrin të kalojë vetëm testin e vogël.

Zgjidhja 3

import math

T = int(input())
for t in range(T):
    n = int(input())
    L = [int(i) for i in input().split()]
    l_min = math.inf
    i_min = n
    i = n-1
    while i >= 0:
        if L[i] <= l_min:
            l_min = L[i]
            i_min = i
        i -= 1
    print(i_min + 1)

Sqarime

Kjo zgjidhje është e ndryshme nga dy të parat. Po ta mendojmë me kujdes, vëmë re se prefixSum(L, i) + suffixSum(L, i) == sum(L) + L[i]. Kjo do të thotë se vlera më të vogël e shumës merret për të njëjtën i që ka numri më i vogël i listës. Kështu që nuk është nevoja ta llogarisim fare shumën por gjejmë direkt numrin më të vogël të listës.

Për të gjetur vlerën më të vogël të i-së, përsëri e bëjmë kontrollin duke filluar nga fundi.

Koha e kësaj zgjidhje është \(O(N)\), sepse kemi vetëm një cikël. Ky është një përmirësim i ndjeshëm në krahasim me zgjidhjet e mësipërme, dhe kjo zgjidhje i kalon edhe testet e mëdha.

Zgjidhja 4

for _ in range(int(input())):
    input()
    L = [int(i) for i in input().split()]
    print(L.index(min(L)) + 1)

Sqarime

E njëjta zgjidhje si më sipër, por më e përmbledhur, duke përdorur funksionet e gatshme min() dhe index().

Detyra

Ceni kishte një kuti me N numra në të: \(A_1, A_2, ... , A_n\). Gjithashtu kishte vendosur edhe numrin N në krye, për të ditur sa numra janë. Pra kutia kishte gjithsej N+1 numra. Por nga gëzimi i olimpiadës IOI ai filloi të kërcente me kutinë në xhep dhe numrat iu ngatërruan, dhe tani nuk e di më se cili nga N+1 numrat është numri N dhe cilët janë numrat e tjerë. Atij i duhet të gjejë më të madhin e numrave të dhënë. A mund ta ndihmoni?

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

Shembull

$ cat input.txt
3
1 2 1
3 1 2 8
1 5 1 4 3 2

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

Në rastin e parë, N=2 dhe numrat janë {1, 1}, kështu që më i madhi është 1.

Në rastin e dytë N=3 dhe numrat janë {1, 2, 8}. Më i madhi është 8.

Në rastin e tretë N=5 dhe numrat janë {1, 1, 4, 3, 2}. Më i madhi është 4.