• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problem z zadaniem Nawiasy OIG

Aruba Cloud PRO i VPS, Openstack, VMWare, MS Hyper-V
0 głosów
121 wizyt
pytanie zadane 24 lutego 2022 w Algorytmy przez samek Nowicjusz (180 p.)
Cześć.

Robię zadanie z 3 etapu OIG Nawiasy - LINK: https://szkopul.edu.pl/problemset/problem/t_f7jgsXWN9MO7z6BvjvaIr7/site/?key=statement

Bardzo długo głowiłem się nad poprawą algorytmu. Czasowo się zgadza, czasami dostaję złe odpowiedzi przez co niepełna ilość pkt.

Mój kod:

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n = 0;
    long long licznik = 0;
    long long licznik_lewo = 0;
    string ciag;
    stack<char>nawiasy;

    cin >> n >> ciag;

    for (int i = 0; i < n; i++)
    {
        if (ciag[i] == '(')
        {
            nawiasy.push('(');
        }
        else
        {
            if (!nawiasy.empty())
            {
                licznik++;

                nawiasy.pop();
                if (nawiasy.empty())
                {
                    licznik += licznik_lewo;
                    licznik_lewo++;
                }
            }
            else
            {
                licznik_lewo = 0;
            }
        }
        //cout << "I: " << licznik_lewo << endl;
        //cout << "Licznik: " << licznik << endl;
    }

    printf("%d",licznik);
    return 0;
}
 

Ma ktoś jakiś pomysł gdzie zrobiłem błąd?

Z góry dziękuję za odpowiedzi.
komentarz 24 lutego 2022 przez Whistleroosh Nałogowiec (47,000 p.)

Zobacz co Twój program wypisuje dla testu:

6
(()())
komentarz 24 lutego 2022 przez samek Nowicjusz (180 p.)

@samek, Dla testu:

6

(()())

Wynik to: 3.

To chyba dobrze? 1 fragment to: (), 2 fragment to: (), 3 fragment to: (()())

komentarz 24 lutego 2022 przez Whistleroosh Nałogowiec (47,000 p.)
Jeżeli dobrze rozumiem treść zadania to powinno tez być ()()
komentarz 24 lutego 2022 przez samek Nowicjusz (180 p.)
aaa no tak faktycznie tego nie uwzględniłem.
komentarz 24 lutego 2022 przez Wiciorny Ekspert (251,530 p.)

@samek, popraw pytanie, sformatuj kod do odpowiednich bloczków 

1 odpowiedź

0 głosów
odpowiedź 10 marca przez pasjonat_algorytmiki Stary wyjadacz (12,760 p.)
edycja 10 marca przez pasjonat_algorytmiki

Przypomniałem sobie ostatnio o tym zadaniu, więc opiszę jak je zrobiłem. Obiektywnie nie jest jakieś kosmiczne, ale łatwe też nie jest. Na tamten czas nie do zrobienia przezemnie. (Wgl jeszcze widze, że z pierwszego konta na forum zadałem to pytanie) Bruta w O(N^2), można stosunkowo łatwo napisać. Zaczynasz od każdego idx-u i idziesz sobie forem, i sprawdzasz czy podane nawiasowanie jest dobre. Robimy to klasycznym sposobem. Mamy zmienną np. int bilans. na początek bilans = 0. i jeśli spotykamy nawias otwierajacy, to bilans++, jak zamykajacy to bilans-- i żeby nawiasowanie było poprawne, to nigdy bilans nie może byc mniejszy od 0, jak jest w pewnym momencie, to nie idziemy dalej, bo oznacza, to że nawiasowanie jest niepoprawne. I jeśli nigdy nie był bilans mniejszy od zera, i w pewnym momencie bilans = 0, to wyn++. O(N^2), z tego co pamiętam to przechodzi na 49pkt. Teraz pomyślmy na trochę lepszym rozwiązaniem, ale jeszcze nie wzorcowym. Można analogicznym sposobem jak poprzedni w O(N^2), zrobić to w O(N * lg N * lg N), naliczając sobie vector stat, gdzie stat[i] = aktualny bilans, przy założeniu, że liczymy bilans od idx-u 0, i normalnie robimy jak otwierający, to bilans++, zamykający to bilans--, tylko jak w pewnym momencie bilans będzie mniejszy od 0, to nie kończymy, tylko konktynujemy dalej. I od każdego momentu, zamiast iść naiwnie pętlą for, to naliczymy sobie drzewo przedziałowe punkt - przedział min-ów, i wyszukiwaniem binarnym będziemy robić query, sprawdzając, czy min na sprawdzanym przedziale + stat[i-1], było mniejsze / większe od 0 i w zależności przesuwamy początek / koniec -> O(N * lg * lg N), bo od N elementów puszczamy wyszukiwanie binarne, a w wyszukiwaniu binarnym robimy jedno query na drzewie przedziałowym, co ma O(lg N). Nie wiem na ile to wchodzi, ale napewno nie na 100, bo liniówka na styk, ledwoco wchodzi. Można ten pomysł trochę przyśpieszyć do O(N lg N), usuwając loga z drzewa przedziałowego. Można wywalić drzewo przedziałowe, i mina na przedziale odpowiadać np. za pomocą struktury sparse table. Na początku robimy preprocesing nawet starczy w O(N lg N)(nie trzeba preprocesingu w O(N), bo i tak nie pogorszy złożonności, bo jest wyszukiwanie binarne, np ja nie umiem napisać sparse table przy procesingu O(N), ale coś czytałem, że się da, ale nie wiem jak. Jak ktoś wie, to fajnie jak by opisał. Ale jak ktoś umie to oczywiście lepiej zaklepać w O(N)), a w wyszukiwaniu binarnym sprwadzamy w O(1) mina na przedziale -> O(N lg N), to najprawdopodobniej też nie wejdzie na 100, bo liniówka ledwo co weszła. 

Teraz rozwiązanie wzorcowe, O(N), je znalazłem jakiś czas temu w jakimś pliku static scholaris w necie(nwm co to) czy jakoś tak, ale jak te teraz szukałem tej strony z omówieniem, to nie mogłem na nią wejść). Na początek kilka formalności, limity są tak wyśrubowane, że bez tego mi nie przeszło na 100pkt.

1 - Jeśli korzystamy z cout-ów, cinów, to na początku programu, pierwsza linijka w main-ie warto napisać:

ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

Ogólnie ja zawsze piszę te linijki i przyśpieszają. Tylko jak to się pisze, to należy pisać cout i cin, zamiast scanf i printf, bo podobno mozna sobie zrobić krzywdę (nie wiem dlaczego, ale tak kiedyś usłyszałem).

No i ogólnie też wydaje mi się, że pisanie w cou-cie endl jest wolne, lepiej pisać "\n" w stringu, ale najszybsze wydaje mi się, żę jest '\n' w charze. Ja tak staram się pisać. Znam zadania, gdzie endl nie wchodzi na 100pkt, tylko np na 97 czy coś takiego. No a bez tych ios_basow itp to już dużoooooo zadań nie przechodzi na 100pkt. Z tymi iosbasami itp warto wiedzieć, że one wypiszą dopiero po zakończeniu programu, więc na potrzeby debugowania czasem warto je zarymować, tylko potem słabo jest jak się zapomni je odrymować.

2 - Nie polecam w tym zadaniu czytać znak po znaku, forem, tylko lepiej wczytać całego stringa i się po nim iterować. Mi dokładnie to samo rozwiązanie z czytaniem chara po charze nie przeszło, tylko dopiero z wczytaniem całego stringa raz.

No i rozwiązanie wzorcowe, jest podobne co to w O(N^2), tylko trochę przyśpieszymy je na stosie. Nie będziemy za każdym razem naliczać od nowa bilansu, tylko skorzystamy z tego, że znamy dla poprzednich. Wkleję kod z krótkim opisem, bo nie jest baaaardzo trudny, ale banalny też nie jest:

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int n = 0, bilans = 0;
long long wyn = 0;
string ciag;
stack<int> S;
stack<int> S_ile_wystapien;

int main()
{
    /*
    Zadanie nawiasy z finalu V OIG-a. O(n).
    Jak chcemy sprawdzic czy dane wyrazenie nawiasowe jest poprawne, to mozemy to zrobic zmienna bilans i jesli nawias[i] = '(', to bilans++,
    nawias[i] = ')' to bilans--, gdzie nawias to wyrazenie nawiasowe. I teraz zeby wyrazenie bylo poprawne, to musza byc spelnione 2 warunki:
    1 - zmienna bilans na koniec musi byc rowna 0.
    2 - zmienna bilans nigdy nie moze byc mniejsza od 0.
    Na tej podstawie mozna konstruowac rozwiazanie w czasie O(n^2) szukajac nawiasu od kazdego elementu wyrazenia 2 petlami for.
    My musimy to zrobic szybciej bo n <= 2*10^6. Stos zalatwia nam sprawe.
    Zauwazmy, ze nasze rozwiazanie sie amortyzuje do O(n), bo kazdy element maksymalnie raz dodamy i usuniemy z stosu.

    Stos S przechowuje wartosci zmiennej bilans, a i-ty element stosu S_ile_wystapien mowi ile jest wystapien i-tego elementu stosu S.
    Dzieki stosowi S_ile_wystapien mozemy przy aktualizowaniu wyniku wiedziec ile mamy dodac, bo sam stos S nie daje nam takiej informacji.
    Mozna alternatywnie zamiast stosu S_ile_wystapien zrobic tylko jeden stos (strukture: wartosc, ile wystapien).

    Mozna zamiast 2 stosu zrobic mapa, jednak wtedy O(n log n), co jest zawolne. Wchodzi na okolo 70%
    Mozna tez zamiast S_ile_wystapien miec tablice o rozmiarze 2*n+1, gdzie trzymamy wartosci. Nie przejmujac sie ujemnymi wartosciami zmiennej bilans,
    bo mozna to obejsc stosujac konwencje ze element o bilansie 0 jest na pozycji 10^6, bilans 5 na pozycji 10^6 + 5 itd, bilans = -5 na pozycji 10^6 - 5 itd.
    W obu rozwiazaniach (z stosem i tablica) otrzymujemy rozwiazanie w zlozonnosci O(n).
     */
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> ciag;
    S.push(0);
    S_ile_wystapien.push(1);
    for (int i = 0; i < n; ++i)
    {
        if(ciag[i] == '(')
            bilans++;
        else
            bilans--;

        while(!S.empty())
        {
            if (S.top() > bilans)
            {
                S.pop();
                S_ile_wystapien.pop();
            }
            else
                break;
        }
        if (!S.empty())
        {
            if (S.top() == bilans)
                wyn += S_ile_wystapien.top();
            if (S.top() == bilans)
            {
                S_ile_wystapien.top()++;
            }
            else
            {
                S.push(bilans);
                S_ile_wystapien.push(1);
            }
        }
        else
        {
            S.push(bilans);
            S_ile_wystapien.push(1);
        }
    }

    printf("%lld",wyn);

    return 0;
}

Ten pomysł w O(N), jest trochę podobny, do tego w O(N^2), jeszcze bardziej podobny, do tych w O(N * lgN * lg N), i O(N * lg N), tylko tu trochę sprytniej i szybciej do tego podeszliśmy.

No i to wsm tyle, powodzonka osobą męczącym się z tym zadaniem, jest bardzo fajne.

Trochę podobne pomysły wchodziły w zadaniach:

- Plakatowanie z OI

- Działka z OI (jest wątek na forum)

- Pranie z finału OIG-a (jest wątek na forum)

I coś podobnego do tego bilansu z zadaniach:

- Różnica z 2 etapu OI

- Płytkie nawiasowania z 1 etapu XXX OI

No i to rozwiązanie z drzewem przedziałowym i to z sparse table wydaje mi się, że nawet jak nie przejdzie na 100pkt, to i tak warto napisać.

Edit: jeszcze dopowiedziałbym trochę więcej o tych rozwiązaniach z sparse table i drzewie przedziałowym. Znajdziemy ostatni taki fragment, gdzie nie spadło poniżej zera, a ile jest tam wyników zrealizujemy dwoma wyszukiwaniami binarnymi pierwszego >= i, i ostaniego <= gdzie nie spadło niżej zera. I odejmiemy ile jest wystąpień pomiędzy i w zależności od implementacji dodamy / nie dodamy jeden. I to całe dodamy do wyniku.

A podobne pomysły do tych drzew przedziałowych / sparse table, pojawiły się np zadaniu:

- Bar sałatkowy z 1 etapu OI

Podobne pytania

0 głosów
1 odpowiedź 45 wizyt
pytanie zadane 2 dni temu w Algorytmy przez pasjonat_algorytmiki Stary wyjadacz (12,760 p.)
0 głosów
0 odpowiedzi 39 wizyt
pytanie zadane 9 marca w Algorytmy przez pasjonat_algorytmiki Stary wyjadacz (12,760 p.)
0 głosów
1 odpowiedź 51 wizyt

90,852 zapytań

139,522 odpowiedzi

313,708 komentarzy

60,336 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...