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

Zadanie sponsor OI

VPS Starter Arubacloud
0 głosów
150 wizyt
pytanie zadane 28 listopada 2022 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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!

1 odpowiedź

+1 głos
odpowiedź 28 listopada 2022 przez Whistleroosh Maniak (56,900 p.)

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

komentarz 28 listopada 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
ale jaja xD. No faktycznie a ja zrobiłem tą 1 wersję w O(n^2)

Dzięki
komentarz 28 listopada 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@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.

komentarz 28 listopada 2022 przez Whistleroosh Maniak (56,900 p.)
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.
1
komentarz 28 listopada 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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ł.

 
 

 

 

Podobne pytania

0 głosów
1 odpowiedź 116 wizyt
+1 głos
1 odpowiedź 469 wizyt
pytanie zadane 5 grudnia 2022 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
+1 głos
1 odpowiedź 293 wizyt
pytanie zadane 14 listopada 2022 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,453 zapytań

141,262 odpowiedzi

319,086 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...