Zadanie ploty 2 etap XV OIJ

Question

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/8l-VO_3t9ztnFSIngG3bYUot/site/?key=statement

Napisałem bruta O(N^2), sprawdzam każda parę krawedzi czy się przecinają, jak tak to wiem że wynik to jedna z tych dwóch. Wywalam dowolną, sprawdzam czy się przecinają jak nie, to znaczy że ta była zła, jak tak to ta druga, dostałem 53 pkt. Nie wiem jak to przyspieszyć. Znalazłem jedynie że chyba trzeba użyć seta tylko nwm jak.

Z góry dziękuję za pomoc i poświęcony czas!

Answer 1

Z tego co rozumiem wystarczy znaleźć jakąkolwiek parę przecinających się krawędzi.

Załóżmy, że mamy krawędź x -> y (x < y). Kiedy przetnie ją pewna krawędź zaczynająca się w którymś z punktów  x+1...y-1?

Comments

gdy jeden wierzchołek tej drugiej krawędzi jest na lewo od tej pierwszej krawędzi, a drugi na prawo?

---

Innej możliwości raczej nie ma. Tylko jak matematycznie zapisać ten warunek?

---

Krawędź k1 przecina k2, gdy k1.min < k2.max oraz k1.max > k2. min?

Gdzie min i max, to mniejszy i większy numer wierzchołków, które są połączone krawedzią

?

---

Oraz wszystkie 4 wierzchołki są parami różne

---

Nie wiem czy to zadziała dla wszystkich przypadków. Ale jeden punkt tego k2 jest już pomiędzy punktami krańców k1. Co w takim razie musi spełnić drugi z tych punktów k2?

---

Może to kiepskie pytanie, bo to oczywiste, ze ten drugi punkt musi być po drugiej stronie k1 czyli k2.min < k1.min or k2.max > k1.max (zakładamy że pierwszy punkt k2 leży po tej stronie k1 na której nie ma punktu 1). Ale jak znaleźć dowolny punkt który to spełnia?

---

może jakoś drzewo przedziałowe?

---

Bo jak mamy pary krawędzi posortowane po początkach od najmniejszych, to te o większym początku to te od idx-ów [i+1,n-1], gdzie N to liczba krawędzi, to samo dla końców, chyba nie można nawet liniowo tego zrobić?

---

Pewnie tak, choć tu nie trzeba nic updatować, więc nawet niekoniecznie drzewo. Czy liniowo da się zrobić to nie wiem

---

a to, nie działa tak, że skoro k2.min > k1.min oraz k2.max > k1.max, robimy po tym drzewo przedziałowe i mamy O(N lg N) ?

---

a nie pomieszało mi się całkowicie

---

chyba rozumiem, jak mamy krawędź 1->5, to z wszystkich punktów [2,4] sprwadzamy, czy jest taki k2.min < k1.min or k2.max > k1.max, i to mamy na drzewie przedziałowym.

---

Tak, ale tak jak wspomniałem to może być dowolna struktura która odpowiada na zapytanie min/max na przedziale

---

Tak teoretycznie, oczywiście wiem że to całkowicie bez sensu itp, ale jakby się uprzeć to chyba nawet Mo można zrobić.

---

Można, pytanie czy przejdzie czasowo

---

napisałem taki prosty kod z drzewem przedziałowym, dostaję WA, wiesz może gdzie jest błąd?

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Krawedz
{
    int minn;
    int maxx;
};

int n = 0, a = 0, b = 0, base = 0, rozmiar_drzewa = 0, q = 0;
vector<Krawedz> krawedzie;
vector<Krawedz> krawedzie_in;
vector<int> drzewo_przedzialowe_min;
vector<int> drzewo_przedzialowe_max;

inline int query_max (int l, int p)
{
    l--,p--;
    l = l + base - 1, p = p + base + 1;
    int res = -1e9;
    while (l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res = max(res, drzewo_przedzialowe_max[l+1]);
        if (p % 2 == 1)
            res = max(res, drzewo_przedzialowe_max[p-1]);
        l /= 2;
        p /= 2;
    }
    return res;
}

inline int query_min (int l, int p)
{
    l--,p--;
    l = l + base - 1, p = p + base + 1;
    int res = 1e9;
    while (l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res = min(res, drzewo_przedzialowe_min[l+1]);
        if (p % 2 == 1)
            res = min(res, drzewo_przedzialowe_min[p-1]);
        l /= 2;
        p /= 2;
    }
    return res;
}

inline pair<int,int> jakie_przecinaja()
{
    vector<int> A_min, A_max;
    A_min.assign(n+1,1e9);
    A_max.assign(n+1,-1e9);
    for (int i = 0; i < krawedzie.size(); ++i)
        A_min[krawedzie[i].minn] = min(A_min[krawedzie[i].minn], krawedzie[i].maxx);
    for (int i = 0; i < krawedzie.size(); ++i)
        A_max[krawedzie[i].minn] = max(A_max[krawedzie[i].minn], krawedzie[i].maxx);

    base = (1 << int(ceil(log2(n + 5)))), rozmiar_drzewa = base * 2;
    drzewo_przedzialowe_min.assign(rozmiar_drzewa,1e9);
    drzewo_przedzialowe_max.assign(rozmiar_drzewa,-1e9);

    for (int i = 1; i <= n; ++i)
        drzewo_przedzialowe_min[i+base-1] = A_min[i];
    for (int i = base-1; i >= 1; --i)
        drzewo_przedzialowe_min[i] = min(drzewo_przedzialowe_min[i*2], drzewo_przedzialowe_min[i*2+1]);

    for (int i = 1; i <= n; ++i)
        drzewo_przedzialowe_max[i+base-1] = A_max[i];
    for (int i = base-1; i >= 1; --i)
        drzewo_przedzialowe_max[i] = max(drzewo_przedzialowe_max[i*2], drzewo_przedzialowe_max[i*2+1]);

    for (int i = 0; i < krawedzie.size(); ++i)
    {
        int poczatek = krawedzie[i].minn + 1, koniec = krawedzie[i].maxx - 1, minn = query_min(poczatek, koniec), maxx = query_max(poczatek, koniec);
        if (maxx > koniec or minn > poczatek)
        {
            for (int j = 0; j < krawedzie.size(); ++j)
            {
                if (krawedzie[j].minn >= poczatek and krawedzie[j].minn <= koniec and (krawedzie[j].maxx > poczatek or krawedzie[j].maxx > koniec))
                    return {i,j};
            }
        }
    }
    return {-1,-1};
}

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

    cin >> q;

    while(q--)
    {
        cin >> n;
        krawedzie.assign(n-2,{});
        for (int i = 0; i < n-2; ++i)
        {
            cin >> a >> b;
            krawedzie[i].minn = min(a,b);
            krawedzie[i].maxx = max(a,b);
        }

        krawedzie_in = krawedzie;

        pair<int,int> przecinajace = jakie_przecinaja();

        vector<Krawedz> dod;
        for (int i = 0; i < n-2; ++i)
            if (i != przecinajace.first)
                dod.push_back(krawedzie[i]);
        krawedzie = dod;

        pair<int,int> przecinajace2 = jakie_przecinaja();

        if (przecinajace2.first == -1)
            cout << krawedzie_in[przecinajace.first].minn << ' ' << krawedzie_in[przecinajace.first].maxx << '\n';
        else
            cout << krawedzie_in[przecinajace.second].minn << ' ' << krawedzie_in[przecinajace.second].maxx << '\n';
    }

    return 0;
}

edit: poprawiłem kilka indeksowań, było bez sensu, ale dalej WA.

---

Pętla w 77 wygląda jakby miała kilka błędów

---

Chyba czegoś nie rozumiem. Napisałem bruta w O(N^2), żeby sprawdzić, czy dobrze rozumiem, i chyba nie... Nie wiem, gdzie ta funkcja ma błąd:

inline pair<int,int> jakie_przecinaja()
{
    for (int i = 0; i < krawedzie.size(); ++i)
    {
        int poczatek = krawedzie[i].minn + 1, koniec = krawedzie[i].maxx - 1;
        for (int j = 0; j < krawedzie.size(); ++j)
        {
            int a = krawedzie[j].minn, b = krawedzie[j].maxx;
            if (a >= poczatek and a <= koniec)
            {
                if (b < poczatek or b > koniec)
                    return {i,j};
            }
            a = krawedzie[j].maxx, b = krawedzie[j].minn;
            if (a >= poczatek and a <= koniec)
            {
                if (b < poczatek or b > koniec)
                    return {i,j};
            }
        }
    }
    return {-1,-1};
}

 

---

ooo już weszło O(N^2) na 53pkt, błąd miałem taki, że dawałem początek + 1, koniec - 1, a potem jak sprawdzałem ten drugi, to sprawdzałem nie względem początek i koniec, tylko początek + 1 i koniec - 1. Kod:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Krawedz
{
    int minn;
    int maxx;
};

int n = 0, a = 0, b = 0, base = 0, rozmiar_drzewa = 0, q = 0;
vector<Krawedz> krawedzie;
vector<Krawedz> krawedzie_in;


inline pair<int,int> jakie_przecinaja()
{
    for (int i = 0; i < krawedzie.size(); ++i)
    {
        int poczatek = krawedzie[i].minn, koniec = krawedzie[i].maxx;
        for (int j = 0; j < krawedzie.size(); ++j)
        {
            int a = krawedzie[j].minn, b = krawedzie[j].maxx;
            if (a > poczatek and a < koniec)
            {
                if (b < poczatek or b > koniec)
                    return {i,j};
            }
            a = krawedzie[j].maxx, b = krawedzie[j].minn;
            if (a > poczatek and a < koniec)
            {
                if (b < poczatek or b > koniec)
                    return {i,j};
            }
        }
    }
    return {-1,-1};
}

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

    cin >> q;

    while(q--)
    {
        cin >> n;
        krawedzie.assign(n-2,{});
        for (int i = 0; i < n-2; ++i)
        {
            cin >> a >> b;
            krawedzie[i].minn = min(a,b);
            krawedzie[i].maxx = max(a,b);
        }

        krawedzie_in = krawedzie;

        pair<int,int> przecinajace = jakie_przecinaja();

        vector<Krawedz> dod;
        for (int i = 0; i < n-2; ++i)
            if (i != przecinajace.first)
                dod.push_back(krawedzie[i]);
        krawedzie = dod;

        pair<int,int> przecinajace2 = jakie_przecinaja();

        if (przecinajace2.first == -1)
            cout << krawedzie_in[przecinajace.first].minn << ' ' << krawedzie_in[przecinajace.first].maxx << '\n';
        else
            cout << krawedzie_in[przecinajace.second].minn << ' ' << krawedzie_in[przecinajace.second].maxx << '\n';
    }

    return 0;
}

To jak już wiem co miałem źle, to wracam do drzewa przedziałowego i próbuję zdebugować.

---

No i weszło 100pkt ;)

Błęd był tylko jeden i to faktycznie w tej pętli. Dałem początek = krawedzie[i].minn + 1 oraz koniec = krawedzie[i].maxx - 1, i sprawdzałem nie względem początek i koniec, tylko początek + 1 i koniec - 1. Wystarczyło to zmienić i weszło 100pkt.

Kod dający 100pkt:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct Krawedz
{
    int minn;
    int maxx;
};

int n = 0, a = 0, b = 0, base = 0, rozmiar_drzewa = 0, q = 0;
vector<Krawedz> krawedzie;
vector<Krawedz> krawedzie_in;
vector<int> drzewo_przedzialowe_min;
vector<int> drzewo_przedzialowe_max;

inline int query_max (int l, int p)
{
    l--,p--;
    l = l + base - 1, p = p + base + 1;
    int res = -1e9;
    while (l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res = max(res, drzewo_przedzialowe_max[l+1]);
        if (p % 2 == 1)
            res = max(res, drzewo_przedzialowe_max[p-1]);
        l /= 2;
        p /= 2;
    }
    return res;
}

inline int query_min (int l, int p)
{
    l--,p--;
    l = l + base - 1, p = p + base + 1;
    int res = 1e9;
    while (l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res = min(res, drzewo_przedzialowe_min[l+1]);
        if (p % 2 == 1)
            res = min(res, drzewo_przedzialowe_min[p-1]);
        l /= 2;
        p /= 2;
    }
    return res;
}


inline pair<int,int> jakie_przecinaja()
{
    vector<int> A_min, A_max;
    A_min.assign(n+1,1e9);
    A_max.assign(n+1,-1e9);
    for (int i = 0; i < krawedzie.size(); ++i)
        A_min[krawedzie[i].minn] = min(A_min[krawedzie[i].minn], krawedzie[i].maxx);
    for (int i = 0; i < krawedzie.size(); ++i)
        A_max[krawedzie[i].minn] = max(A_max[krawedzie[i].minn], krawedzie[i].maxx);

    base = (1 << int((double)ceil(log2(n + 5)))), rozmiar_drzewa = base * 2;
    drzewo_przedzialowe_min.assign(rozmiar_drzewa,1e9);
    drzewo_przedzialowe_max.assign(rozmiar_drzewa,-1e9);

    for (int i = 1; i <= n; ++i)
        drzewo_przedzialowe_min[i+base-1] = A_min[i];
    for (int i = base-1; i >= 1; --i)
        drzewo_przedzialowe_min[i] = min(drzewo_przedzialowe_min[i*2], drzewo_przedzialowe_min[i*2+1]);

    for (int i = 1; i <= n; ++i)
        drzewo_przedzialowe_max[i+base-1] = A_max[i];
    for (int i = base-1; i >= 1; --i)
        drzewo_przedzialowe_max[i] = max(drzewo_przedzialowe_max[i*2], drzewo_przedzialowe_max[i*2+1]);


    for (int i = 0; i < krawedzie.size(); ++i)
    {
        int minn = query_min(krawedzie[i].minn+1, krawedzie[i].maxx-1), maxx = query_max(krawedzie[i].minn+1, krawedzie[i].maxx-1);
        if (maxx > krawedzie[i].maxx or minn < krawedzie[i].minn)
        {
            for (int j = 0; j < krawedzie.size(); ++j)
            {
                int a = krawedzie[j].minn, b = krawedzie[j].maxx;
                if (a > krawedzie[i].minn and a < krawedzie[i].maxx and (b < krawedzie[i].minn or b > krawedzie[i].maxx))
                    return {i,j};
            }
        }
    }
    return {-1,-1};
}

int main()
{
    // O(N lg N)
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> q;

    while(q--)
    {
        cin >> n;
        krawedzie.assign(n-2,{});
        for (int i = 0; i < n-2; ++i)
        {
            cin >> a >> b;
            krawedzie[i].minn = min(a,b);
            krawedzie[i].maxx = max(a,b);
        }

        krawedzie_in = krawedzie;

        pair<int,int> przecinajace = jakie_przecinaja();

        vector<Krawedz> dod;
        for (int i = 0; i < n-2; ++i)
            if (i != przecinajace.first)
                dod.push_back(krawedzie[i]);
        krawedzie = dod;

        pair<int,int> przecinajace2 = jakie_przecinaja();

        if (przecinajace2.first == -1)
            cout << krawedzie_in[przecinajace.first].minn << ' ' << krawedzie_in[przecinajace.first].maxx << '\n';
        else
            cout << krawedzie_in[przecinajace.second].minn << ' ' << krawedzie_in[przecinajace.second].maxx << '\n';
    }

    return 0;
}

No i O(N lg N), dzięki za pomoc!