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

Zadanie Binarne Loty Letni Obóz Treningowy OIJ 2021, przed EJOI

Object Storage Arubacloud
0 głosów
509 wizyt
pytanie zadane 12 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Mam problem z takim zadaniem: https://sio2.mimuw.edu.pl/c/oij15-wiekuisty-oboz/p/bin/

Nie wiem jak je zrobić, w dobrej złożonności. Pierwszy ograniczenie na 30pkt, wydaje mi się, że można zrobić Dijkstrą z krawędziami 0-1 na deque, że mamy graf każdy punkt, będzie ich W*H, a krawędzie to pójścia w górę za wagę jeden, i w dól na wagę zero.

To co zauważyłem, to że różnych możliwych wzniosów z danego punktu nie będzie więcej niż logartym, ale nie wiem jak sobie poradzić też z tym, że ten wznos można uruchomić w polu o niekoniecznie współrzędnych całkowitych.

Z góry dziękuję za pomoc i poświęcony czas!
komentarz 15 marca 2023 przez Whistleroosh Maniak (56,980 p.)
Zależy gdzie jest punkt (0, 0). Jesli w lewym donym wierzchołku to pewnie trzeba trzymać y+x.
komentarz 15 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
a jeszcze jedno pytanie, mam już mina na przedziale z y-x, tak jak robiliśmy. I jak będąc w punkcie(x,h) w dowolnym co mogę być w BFS-ie, policzyć kiedy będzie przecięcie z tym stalaktytem min z y-x? Bo chyba to mam źle.
komentarz 15 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 15 marca 2023 przez pasjonat_algorytmiki
Bo ja napisałem coś takiego:

int wsp = h - spr.wierzcholek

roznica = abs(min_z_y-x_w_drzewie_przedzialowym - wsp);

dlugosc_skoku = roznica / 2 - 1;

zmienna wsp, to y-x w aktualnym punkcie w BFS-a spr.wierzcholek, to współrzędne aktualnego punktu w BFS-ie a dlugosc_skoku to ile możemy skoczyć, a h to wysokość. tylko nwm czy to jest dobre, pewnie złe, tylko nwm dlaczego.
komentarz 15 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
trochę mi się pomieszało, już sobie z tym poradziłem.
1
komentarz 15 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
UWAGA UWAGA!

Po prawie 4 dniach męczarni, ogłaszam wszem i wobec, że przeszło na 100pkt!!!!!!!!!!

1 odpowiedź

+1 głos
odpowiedź 15 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Podsumowanie tego wątku i zadania.

To zadanie jest naprawdę super, dawno się nie cieszyłem tak po zrobieniu jakiegoś zadania. Jeszcze raz dzięki Whistleroosh za pomoc, rozwiązanie zadania i dyskusję! Ponad 60 komentarzy, 4 dni spędzone, to zadanie jest naprawdę bardzo trudne.

Krótki opis co i jak, ale i tak warto przeczytać całą dyskusję!

Spostrzerzenia dzięki którym zrobiliśmy to zadanie:

- Istnieje optymalna droga, w której wznosimy się tylko na współrzędnych całkowitych

- Istnieje droga, w której wszystkie wzniosy(być może poza ostatnim(jak przekracza szerokość mapy) dotykają cały czas ziemi, np:

Teraz rozwiązania:

Pierwsze ograniczenie, można zrobić wspomnianą na początku Dijkstrą 0-1, gdzie puszczamy Dijkstrę od pola startowego i wznios w górę ma koszt 1, a w dół koszt 0, O(H*W*lg(H*W)*koszt_sprawdzenia_o_ile_mozna_isc_w_gore), nawet przy koszcie sprawdzenia o ile można pójść w górę O(N), przechodzi na 30pkt, pewnie to ograniecznie(pewnie bo nie pokazuje wyników sprawdzania)

Drugie ograniczenie można zrobić wspomnianym dynamikiem, korzystamy z drugiego spostrzerzenia i robimy dp, jest opisane. wchodzi na 40pkt.

A rozwiązania na 100pkt, to tosamo co drugie rozwiązania, tylko trzeba zamiast dp zrobić BFS-a od pola startowego, i przyśpieszyć liczenie o ile można pójść baaaaaaaardzo fajnym pomysłem Whistleroosh z trójkątem równoramiennym i drzewem przedziałowym przedział-punkt. Kod dający 100pkt:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Element_kolejki
{
    int wierzcholek;
    int wartosc;
};

int h = 0, w = 0, n = 0, y_i = 0, x_i = 0, y = 0, x = 0, base = (1 << 24), rozmiar_drzewa = (1 << 25), x1 = 0, x2 = 0;
vector<bool> czy_bylismy;
vector<int> drzewo_przedzialowe;
queue<Element_kolejki> Q;

inline void update(int l, int p, int val)
{
    l = l + base - 1, p = p + base + 1;
    while (l / 2 != p / 2)
    {
        if (l % 2 == 0)
            drzewo_przedzialowe[l+1] = max(drzewo_przedzialowe[l+1], val);
        if (p % 2 == 1)
            drzewo_przedzialowe[p-1] = max(drzewo_przedzialowe[p-1], val);
        l /= 2;
        p /= 2;
    }
}

inline int querry(int v)
{
    int res = -1e9;
    v += base;
    while (v > 0)
    {
        res = max(res,drzewo_przedzialowe[v]);
        v /= 2;
    }
    return res;
}

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

    cin >> n >> w >> h;
    czy_bylismy.assign(w+1,false);
    drzewo_przedzialowe.assign(rozmiar_drzewa,-1e9);
    for (int i = 0; i < n; ++i)
    {
        cin >> x_i >> y_i;
        ++y_i; // Konwertujemy wspolrzedna y na tak jak chcemy miec
        y_i = h - y_i; // // Konwertujemy wspolrzedna y na tak jak chcemy miec
        x1 = x_i - y_i - h; // Poczatek przedzialu ktorego i-ty stalaktyt dotyka
        x2 = x_i - (h - y_i); // Koniec przedzialu ktorego i-ty stalaktyt dotyka
        if (x2 < 0)
            continue;
        x1 = max(0,x1);
        x2 = max(x1,x2);
        update(x1,x2,y_i-x_i);
    }

    Q.push({0,0});
    czy_bylismy[0] = true;
    while(!Q.empty())
    {
        Element_kolejki spr = Q.front();
        Q.pop();
        int dlugosc_skoku = querry(spr.wierzcholek), licznik = 1;
        if (dlugosc_skoku == -1e9)
            dlugosc_skoku = h;
        else
        {
            int wsp = h - dlugosc_skoku, roznica = wsp - spr.wierzcholek;
            if (roznica % 2 == 0)
                dlugosc_skoku = roznica / 2 - 1;
            else
                dlugosc_skoku = roznica / 2;
        }

        while(licznik <= dlugosc_skoku)
        {
            if (spr.wierzcholek + licznik * 2 >= w)
            {
                cout << spr.wartosc + 1 << '\n';
                return 0;
            }
            else if (czy_bylismy[spr.wierzcholek + licznik * 2] == false)
            {
                czy_bylismy[spr.wierzcholek + licznik * 2] = true;
                Q.push({spr.wierzcholek + licznik * 2, spr.wartosc + 1});
            }
            licznik *= 2;
        }
    }

    cout << "NIE" << '\n';

    return 0;
}

Jeszcze raz dziękuję Whistleroosh!!!

komentarz 15 marca 2023 przez Whistleroosh Maniak (56,980 p.)
Całkiem trudne jak na OIJ, ale przyjemność ze znalezienia wzorcówki jest niesamowita.
komentarz 15 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
To nie jest zwykły OIJ, tylko chyba obóz dla kadry polski przed EJOI-em. Ale tak przyjamnośc po zrobieniu jest niesamowita. Wgl myślisz, że jest jeszcze jakieś inne rozwiązanie? Bo te limity są takie, że wydaje mi się, że niema. Wydaje mi się, że h<=10^7, żeby dp nie przeszło, ale nie h <= 10^9, żeby dało się drzewo przedziałowe napisać.
komentarz 15 marca 2023 przez Whistleroosh Maniak (56,980 p.)
Nawet gdyby to było OI to takie zadanie to raczej jako najtrudniejsze na II etapie, albo z III etapu. Te poprzednie z EJOI które pokazywaleś były duzo prostsze do wymyslenia (może trudniejsze do zaimplementowania)
komentarz 15 marca 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
No tak, z tego obozu, to chyba najtrudniejsze które widziałem. Ale ogólnie fajne te zadanka.

Podobne pytania

0 głosów
1 odpowiedź 407 wizyt
0 głosów
1 odpowiedź 111 wizyt
0 głosów
1 odpowiedź 367 wizyt

92,695 zapytań

141,606 odpowiedzi

320,106 komentarzy

62,052 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

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!

...