11059. Prefiks równoważący sufiks [MWP4_1E]

Zadanie:
https://pl.spoj.com/problems/MWP4_1E

Skrócony opis problemu:

Dla danego ciągu liczb o długości $n$, znajdź najmniejszy indeks, dla którego suma liczb za nim jest równa sumie liczb od początku do niego włącznie. Jeśli taki indeks nie istnieje - wypisz 0.

Na przykład dla $n=5$ i ciągu 4,2,3,2,1 wynik to 2 (liczymy indeksy od 1), bo dla drugiej liczby mamy: 4+2=3+2+1.

Rozwiązanie naiwne:

Zaczynając od początku ciągu możemy sumować wszystkie liczby do tej, którą bierzemy pod uwagę włącznie oraz od niej do końca i porównywać obie sumy. Jeśli będą równe, to wypisujemy indeks liczby, którą w danym momencie rozpatrujemy. Dzięki temu, że zaczynamy od początku mamy pewność, że będziemy mieli najmniejszy możliwy indeks.

Złożoność: $O(n^2)$.

Rozwiązanie sprytne:

Możemy zauważyć, że jak policzymy te 2 sumy i przesuniemy indeks na następny, i będziemy znów chcieli policzyć te sumy, to większość składników z sumach będzie taka sama. Zmieni się tylko to, że rozpatrywana przez nas liczba pójdzie nie do drugiej sumy, tylko do pierwszej - tej od początku ciągu. Możemy zatem na początku policzyć sumę wszystkich wyrazów ciągu i zapisać ją do zmiennej $suma2$, i ustawić $suma=0$. $suma2$ będzie opisywać sumę sufiksu (czyli prawej części ciągu), a $suma$ prefiksu (czyli lewej części ciągu). Gdy bierzemy pierwszy element to odejmujemy jego wartość od $suma2$ i dodajemy do $suma$, a następnie porównujemy obie sumy.

Złożoność: $O(n)$.

Ostateczny algorytm:

int main()
{
    int n, tab[n]; // dane
    int i, suma = 0, suma2 = 0;

    get(n);
    for(i = 0; i < n; ++i)
    {
        get(tab[i]);
        suma2 += tab[i];
    }
    for(i = 0; i < n-1; ++i)
    {
        s += tab[i]; s2 -= tab[i];
        if(s == s2)break;
    }
    if(i == n-1)print(0); // jeśli doszliśmy do końca i nie udało nam się znaleźć rozwiązania
    else print(i+1); // bo liczymy od 0, a powinniśmy od 1
}