Zadanie sponsor OI

Question

Czesc,

Natknąłem się na zadanie sponsor z I OI - https://szkopul.edu.pl/problemset/problem/E3eS485F0Qmr6RLduybh_e5b/site/?key=statement

Zrobiłem prostego dynamika na 60pkt:

#include <iostream>
#include <vector>

using namespace std;

int n = 0, max_wyn = 0;
double wczytana_liczba = 0;
vector<double> liczby;
vector<int> dp;

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

    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        dp.push_back(-1);
        liczby.push_back(wczytana_liczba);
    }

    dp[0] = 1;

    for (int i = 1; i < n; ++i)
    {
        int max_dp = 0;
        for (int j = i-1; j >= 0; --j)
        {
            if (liczby[j] > liczby[i])
            {
                max_dp = max(max_dp,dp[j]);
            }
        }
        dp[i] = max_dp+1;
    }

    for (int i = 0; i < n; ++i)
    {
        max_wyn = max(max_wyn,dp[i]);
    }

    printf("%d00",max_wyn);

    return 0;
}

Podejrzewam,że pewnie trzeba jakoś zoptymalizować te szukanie maxa z wszystkich dp, których liczby są > niż liczby[i]. Wydaje mi się tak, bo robiłem kiedyś podobne zadanie - stabilny ciąg z finału XVI OIJ, tylko tam było NWD i brało się maxa z wszystkich liczb, których NWD > 1. I tam musialem naliczyć mapa z dzielnikami.

Tu jest ciężej, bo liczby[i] i ta szukana nie mają żadnych cech specjalnych. Ma ktoś pomysł jak to zoptymalizować?

Bardzo dziękuję za pomoc i poświęcony czas!

Answer 1

To chyba jest po prostu longest decreasing subsequence, czyli odwrotność tego algorytmu

Comments

ale jaja xD. No faktycznie a ja zrobiłem tą 1 wersję w O(n^2)

Dzięki

---

@Whistleroosh, 

Wlasnie w książeczce OI opisywali O(n log n), tylko to książka z przed 30 lat i tam pisał jakieś niezmienniki moura czy jakieś inne dziwne rzeczy.

---

Hoare. Po prostu opisali dowód poprawności algorytmu, ale tego raczej nie trzeba znać na OI. Są ogólnie 2 metody rozwiązania tego zadania, jedna na jakieś drzewa przedziałowe i jedna na bin searcha. Na tej stronie co podesłałem chyba są obydwa rozwiązania.

---

Dobra przeszło na 100pkt z ponad 6 krotnym zapasem O(n log n) z drzewami przedziałowymi.

Opiszę teraz krótko szczegóły, bo implementacja nie jest taka oczywista jak ktoś by się kiedyś męczył:

vectory:

- liczby przechowuje liczby z wejścia

- do sorta vector struktur zeby naliczyc vectory jaki idx, ile_na_lewo_te_same. 

- ile na lewo te_same - bylby nie potrzebny gdy by szukajac dla i - tego elementu interesowaly nas >= a jak wieksze to nie mozemy brac rownych i bez niego byloby >=. Mozna zastapic mapem, ale wtedy czas pewnie spuchnie o połowę, ale też będzie O(n log n). Przechowuje ile jest elementow na lewo o tej samej wartosci w vectorze posortowanym (do sorta)

- jaki_idx - jaki indeks w vectorze posortowanym ma liczby[i]

Ogólnie do drzew przedziałowych musi być posortowany vector, bo jak nie to nie mamy jak brać maxa na przedziale. A tak to wiemy, że wszystkie elementy na lewo są >=.

- drzewo_przedzialowe - jest to drzewo przedzialowe, ktore trzyma max dp na szukanym przedziale.

Wszystko te pomocnicze struktury napełniamy w czasie liniowym. sortujemy w O(n log n). A potem funkcje update i querry to znane funkcję z implementacji drzewa przedziałowego.

 

kod: https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/OI/sponsor_dynamik_drzewo_przedzialowe_100pkt.cpp

Jeszcze raz dzięki!, jak przeczytałem tam o drzewach przedziałowych to odrazu skojarzyłem z tym pomysłem, a tak to bym się męczył i nie wiem czy bym wymyślił.