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

Question

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!

Comments

Zależy gdzie jest punkt (0, 0). Jesli w lewym donym wierzchołku to pewnie trzeba trzymać y+x.

---

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.

---

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.

---

trochę mi się pomieszało, już sobie z tym poradziłem.

---

UWAGA UWAGA!

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

Answer 1

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!!!

Comments

Całkiem trudne jak na OIJ, ale przyjemność ze znalezienia wzorcówki jest niesamowita.

---

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

---

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)

---

No tak, z tego obozu, to chyba najtrudniejsze które widziałem. Ale ogólnie fajne te zadanka.