Zadanie księgowy OIG

Question

Mam problem z takim zdaniem: https://szkopul.edu.pl/problemset/problem/2crG-_mquBH3-t56F8OpCNlg/site/?key=statement

Poza brutem w O(N^2) nie wiem jak to ugryść lepiej, ale mam spostrzerzenie, że jak naliczymy sobie sumy prefiksowe od początku i obracamy jakiś fragment w przedziale [l,p], to sumy prefiksowe odwrócą się tylko na tym przedziale, a np. w punktach p+1,p+2,p+3.... oraz l-1, l-2, l-3.... pozostaną takie same. Trochę oczywiste spostrzrzenie, ale myślę, że może się przydać.

Z góry dziękuję za pomoc i poświęcony czas!

Answer 1

Mam pewne przemyślenia do tego zadania. Skoro wiemy, że jeśli obracamy [l, p] to nie zmienia to sum na [0, l-1] i [p+1, n] to sugeruje to żeby policzyć sumy prefiksowe, zobaczyć gdzie stają się ujemne i teraz l to najmniejszy indeks w którym sumy stają się ujemne, a p największy. Musimy obrócić co najmniej [l, p] ale być może więcej. Policzmy sumy sufiksowe dla [l, p] (lub prefiksowe dla [p, l]) musimy zagwarantować że żadna suma na tym przedziale + sum([0, l-1]) nie będzie ujemna. Możemy jedynie zmniejszać l lub zwiększać p. Najbardziej opłaca nam się oczywiście zmniejszać l, bo szukamy rozwiązania o najmniejszym l, więc zróbmy to. Zmniejszmy l o 1 i policzmy sume sufiksową na [l-1, p]. Teraz jeśli po dodaniu sum([0, l-2]) mamy coś ujemnego musimy dodać pewien fragment [p+1, p+k] żeby to naprawić. Więc szukamy najmniejszego k, że po dodaniu sum([p+1, p+k]) dostajmy nieujemne sumy na przedziale [l-1, p]. Wydaje mi się, że to k możemy znaleźć bin searchem. Oczywiście powtarzamy to wszytko dla co raz to mniejszych l.

Jeśli pomysł jest poprawny to dostajemy rozwiązanie w O(nlogn)

Comments

a wsm, jak to działa, to nie starczy z każdego idx-u i puścić takiego binary searcha po k? Wydaje mi się, że to nie zepsuje. Mylę się?

---

A ok ok, cofam, no tak to zepsuje.

---

Tylko jak się binary searchować? Bo ja jedynie myślałem żeby naliczyć sumy prefiksowe od tyłu takie tak jakby sufixowe, i z sparse table odpowiadać w O(1) na mina na przedziale, tylko zwykły binary search po minach od tyłu starczy?

---

Trzeba znaleźć najmniejsze k, że sum([p+1, p+k]) >= x dla pewnego x. p jest stałe. Więc wystarczy zrobić mały preprocessing. Liczysz kolejne sumy prefiksowe sum([p+1, p+1]), sum([p+1, p+2]), ... z czego jeśli ta suma jest mniejsza od którejkolwiek poprzedniej to nie ma sensu jej dodawać. Wystarczy pamiętać tylko te k_1 < k_2 < ..., dla których sum([p+1,p+k_1]), sum([p+1,p+k_2]), ... będzie monotonicznie rosnące

---

Przeszło na 100pkt. Kod:

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

struct Element
{
    ll val;
    int idx;
};

int n = 0, idx_lewo = 1e9, idx_prawo = -1e9, min_lewo = -1, min_prawo = -1;
ll min_val = 1e18, sum = 0;
vector<int> liczby;
vector<ll> sumy_prefiksowe;
vector<ll> sumy_sufixowe;
vector<Element> elementy;

int main()
{
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    cin >> n;

    liczby.assign(n,-1);
    sumy_prefiksowe.assign(n,-1);
    sumy_sufixowe.assign(n,-1);

    for (int i = 0; i < n; ++i)
        cin >> liczby[i];

    sumy_prefiksowe[0] = liczby[0];
    for (int i = 1; i < n; ++i)
        sumy_prefiksowe[i] = sumy_prefiksowe[i-1] + liczby[i];

    sumy_sufixowe[n-1] = liczby[n-1];
    for (int i = n-2; i >= 0; --i)
        sumy_sufixowe[i] = sumy_sufixowe[i+1] + liczby[i];

    for (int i = 0; i < n; ++i)
    {
        if (sumy_prefiksowe[i] < 0)
        {
            idx_lewo = min(idx_lewo, i);
            idx_prawo = max(idx_prawo,i);
        }
    }

    if (idx_lewo == 1e9)
    {
        cout << "1 1" << '\n';
        return 0;
    }

    for (int i = idx_prawo+1; i < n; ++i)
    {
        sum += liczby[i];
        if (elementy.empty())
            elementy.push_back({sum,i});
        else if (sum > elementy[elementy.size()-1].val)
            elementy.push_back({sum,i});
    }

    for (int i = idx_lewo+1; i <= idx_prawo; ++i)
         min_val = min(min_val,sumy_sufixowe[i]);

    for (int i = idx_lewo; i >= 0; --i)
    {
        min_val = min(min_val, sumy_sufixowe[i]);
        ll szukana = 0;
        if (idx_prawo == n-1)
            szukana = min_val;
        else
            szukana = min_val - sumy_sufixowe[idx_prawo+1];
        if (i != 0)
            szukana += sumy_prefiksowe[i-1];
        if (szukana >= 0)
        {
            min_lewo = i, min_prawo = idx_prawo;
            continue;
        }
        szukana *= -1;
        int poczatek = -1, koniec = elementy.size(), srodek = 0;
        while(koniec - poczatek > 1)
        {
            srodek = (poczatek + koniec) / 2;
            if (elementy[srodek].val >= szukana)
                koniec = srodek;
            else
                poczatek = srodek;
        }
        if (koniec != elementy.size())
        {
            min_lewo = i, min_prawo = elementy[koniec].idx;
        }
    }

    if (min_lewo == -1)
        cout << "NIE" << '\n';
    else
        cout << min_lewo+1 << ' ' << min_prawo+1 << '\n';

    return 0;
}

Zastanawia mnie tylko jedna rzecz, czy tego nie da się przyśpieszyć do O(N) usuwając tego binary searcha, i trzymać poprostu max_val jaką można uzyskać i dzięki temu będziemy wiedzieli w O(1), czy się da ułożyć z początkiem G, a potem raz liniowo sobie dla najmniejszego G pasującego odtworzymy wynik w O(N).

Dzięki!

---

Tak, to dobra obserwacja. Można to zrobić liniowo