Algorytm psoms, zadanie: wahanie akcji na giełdzie OI

Question

Mam poważny problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/jzCvm_VOCX4120OGdoLq7RuQ/site/?key=statement

3 godzinę już debuguję, i nie mogę znaleźć błędu. W połowie testów dostaję wrong answer (za duże odpowiedzi wypisuje mój program) i w kilku signal 6 / 11.

Kompletnie nic mi nie przychodzi do głowy co jest źle, bo kod wydaje się byc bardzo krótki / prosty. Poprostu dla każdej akcji biorę największy, gdzie kiedykolwiek była - najmniejszy, gdzie kiedykolwiek była.

Kod, zmienna KTR oznacza numer akcji, którą aktualnie dodajemy, numeruję akcję od 1,2,3,4...:

#include <iostream>
#include <vector>

using namespace std;

int  wyn = 0, KTR = 1;
const int SIZE = 1e6+5;
string ciag;
vector<int> operacje;
int bilans[SIZE] = {0}; // aktualny bilans dla i-tej akcji
int t_max[SIZE] = {0}; // Najwyzsza gora dla i-tej akcji
int t_min[SIZE] = {0}; // Najnizszy dolek dla i-tej akcji
vector<int> wsk; // Wskazniki, ktore akcje sa na danych idx-ach
vector<int> dod; // Jakie beda akcje po zamienieniu w i-tym dniu (to co damy na wsk)

inline void przetwarzaj() // Funkcja ktora ciag wczytany w getlini-ie, tnie na inty i dodaje do vectora operacje.
{
    string spr;
    for (int i = 0; i < ciag.size(); ++i)
    {
        if (ciag[i] == ' ')
        {
            if (!spr.empty())
                operacje.push_back(stoi(spr));
            spr.clear();
        }
        else
            spr += ciag[i];
    }
    if (!spr.empty())
        operacje.push_back(stoi(spr));
}

int main()
{
    // Wynik dla kazdej akcji do max_gora - min_dolek.
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while(getline(cin,ciag))
    {
        operacje.clear();
        przetwarzaj();
        dod.clear();
        while(wsk.size() < operacje.size())
        {
            wsk.push_back(KTR);
            KTR++;
        }
        for (int i = 0; i < operacje.size(); ++i)
        {
            if (operacje[i] != -99)
            {
                bilans[wsk[i]] += operacje[i];
                t_min[wsk[i]] = min(t_min[wsk[i]],bilans[wsk[i]]);
                t_max[wsk[i]] = max(t_max[wsk[i]],bilans[wsk[i]]);
                dod.push_back(wsk[i]);
            }
        }
        wsk = dod;
    }

    for (int i = 0; i < SIZE; ++i)
        wyn = max(wyn, t_max[i] - t_min[i]);

    cout << wyn << '\n';

    return 0;
}

Możliwe, że źle rozumiem treść, bo jest ona moim zdaniem fatalnie napisana, ale jeśli dostejemy -99, to już tej akcji nie używamy, a kolejnych przesuwamy wszystkie o jeden w lewo.

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

Comments

Taki mały hint. Do rozdzielenia stringa po spacjach można skorzystać z stringstream

---

Wgl z inline jest taka ciekawa sprawa, że to tylko hint dla kompilatora żeby nie wywoływać funkcji tylko "wkleić" jej kod. Dzisiejsze kompilatory potrafią same z siebie traktować niektóre funkcje jako inline.

Np. dla Twojego kodu keyword inline nic nie zmienia jeśli kompilujemy z g++ -O2. Dopiero od O3 funkcja jest "wklejana"

Keyword inline ma natomiast inne zastosowanie. Oznaczone nim funkcje można wielokrotnie definiować

---

Myślałem, że inline to poprostu czasami przyśpiesza. A może być taka sytuacja, ze inline zepsuje kod? I funkcja będzie robić coś innego niż bez inline?

---

Raczej nie. W najgorszym wypadku rozmiar kodu wykonywalnego się trochę zwiększy, ale jak rozmiar będzie za duży to sprawdzarka i tak odrzuci

Answer 1

2 problemy

1) W treści chyba nie było wspomniane, że bedzie maksymalnie 1e6 spółek

2) akcje trzeba na początku kupić, a potem sprzedać. Czyli ten maks który znajdujesz musi być po minimum. Teraz niektóre wyniki masz za duże, bo korzystasz z minimum globalnego które może wystąpić po maksimum globalnym

Comments

Dziękuję bardzo! Problemy wynikały z niezrozumienia treści, ale wydaje mi się, że treść jest słabo napisana(pewnie dlatego, że to 1 edycja OI).

Samo przyśpieszenie było proste.

punkt 2 -> wystarczyło zmienić jedną linijkę, że maxa liczymy tylko z mina wcześniejszego.

punkt 1 -> wystarczyło zrobić małą kompresję, że po każdym obiegu daję im numery 1,2,3,4,5,6,7,8.....

Kod dający 100pkt:

#include <iostream>
#include <vector>

using namespace std;

int  wyn = 0, KTR = 1;
const int SIZE = 1e6+5;
string ciag;
vector<int> operacje;
int bilans[SIZE] = {0}; // aktualny bilans dla i-tej akcji
int t_min[SIZE] = {0}; // Najnizszy dolek dla i-tej akcji
vector<int> wsk; // Wskazniki, ktore akcje sa na danych idx-ach
vector<int> dod; // Jakie beda akcje po zamienieniu w i-tym dniu (to co damy na wsk)

inline void przetwarzaj() // Funkcja ktora ciag wczytany w getlini-ie, tnie na inty i dodaje do vectora operacje.
{
    string spr;
    for (int i = 0; i < ciag.size(); ++i)
    {
        if (ciag[i] == ' ')
        {
            if (!spr.empty())
                operacje.push_back(stoi(spr));
            spr.clear();
        }
        else
            spr += ciag[i];
    }
    if (!spr.empty())
        operacje.push_back(stoi(spr));
}

int main()
{
    // Wynik dla kazdej akcji do max_gora - min_dolek.
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while(getline(cin,ciag))
    {
        operacje.clear();
        przetwarzaj();
        dod.clear();
        while(wsk.size() < operacje.size())
        {
            wsk.push_back(KTR);
            KTR++;
        }
        for (int i = 0; i < operacje.size(); ++i)
        {
            if (operacje[i] == -99)
            {
                bilans[wsk[i]] = 0;
                t_min[wsk[i]] = 0;
            }
            else
            {
                bilans[wsk[i]] += operacje[i];
                t_min[wsk[i]] = min(t_min[wsk[i]],bilans[wsk[i]]);
                wyn = max(wyn, bilans[wsk[i]] - t_min[wsk[i]]);
                dod.push_back(wsk[i]);
            }
        }
        wsk = dod;
        vector<int> miny;
        vector<int> bilanse;
        for (int i = 0; i < wsk.size(); ++i)
        {
            miny.push_back(t_min[wsk[i]]);
            bilanse.push_back(bilans[wsk[i]]);
            bilans[wsk[i]] = 0;
            t_min[wsk[i]] = 0;
        }
        for (int i = 0; i < wsk.size(); ++i)
        {
            wsk[i] = i+1;
            bilans[i+1] = bilanse[i];
            t_min[i+1] = miny[i];
        }
        KTR = wsk.size()+1;
    }

    cout << wyn << '\n';

    return 0;
}

Btw, jak ktoś się natknął na to zadanie, i mu się spodobało, na tematykę górek i dołków, to polecam zrobić zadania:

- płtykie nawiasowania z 1 etapu XXX OI

- rożnica z 2 etapu XVIII OI

- bar sałatkowy z 1 etapu XXI OI (można napisać O(N lg N), z górkami-dołkami + 2 binary searche + drzewo przedziałowe punkt -przedział, ale chyba istnieje wzorcówka liniowa).

- łyżwy z 2 etapu XVI OI

btw. Ta technika jest super! Chyba jedna z moich ulubionych po grafach, sqrt i zadaniach na czystego skilla, bez technik.