Szablon Bajtogrodu OI

Question

Mam problem z takim zadaniem z 2 etapu OI-a: https://szkopul.edu.pl/problemset/problem/y-mTVYClxMJcgMhUnHaUqPPq/site/?key=statement

Zrobiłem kod na 50pkt w O(N^3) a mianowicie: ide DFS-em od każdego wierzchołka i dla każdego szablonu mam statystyki jakie krawędzie odwiedziliśmy i sprawdzam jaki się zgadza. Tylko kompletnie nie wiem co dalej, jak to przyśpieszyć.

Kod:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <set>

using namespace std;

int n = 0, a = 0, b = 0;
char wczytany_znak;
vector<vector<pair<int,char>>> krawedzie;
unordered_map<string,set<pair<int,int>>> stat;
vector<bool> czy_bylismy;
vector<string> wyn;

void DFS(int v, string napis, vector<int> wierzcholki)
{
    czy_bylismy[v] = true;
    wierzcholki.push_back(v);
    if (!napis.empty())
    {
        if (auto it = stat.find(napis) == stat.end())
            stat.insert({napis,{}});
        for (int i = 1; i < wierzcholki.size(); ++i)
        {
            stat[napis].insert({wierzcholki[i],wierzcholki[i-1]});
            stat[napis].insert({wierzcholki[i-1],wierzcholki[i]});
        }
    }
    for (int i = 0; i < krawedzie[v].size(); ++i)
    {
        if (czy_bylismy[krawedzie[v][i].first] == false)
        {
            string spr = napis;
            spr.push_back(krawedzie[v][i].second);
            DFS(krawedzie[v][i].first, spr, wierzcholki);
        }
    }
}

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

    cin >> n;
    krawedzie.assign(n+1,{});
    czy_bylismy.assign(n+1,false);

    for (int i = 0; i < n-1; ++i)
    {
        cin >> a >> b >> wczytany_znak;
        krawedzie[a].push_back({b,wczytany_znak});
        krawedzie[b].push_back({a,wczytany_znak});
    }

    for (int i = 1; i <= n; ++i)
    {
        fill(czy_bylismy.begin(),czy_bylismy.end(),false);
        DFS(i,"",{});
    }

    for (auto it = stat.begin(); it != stat.end(); ++it)
    {
        if (it->second.size() == 2 * (n-1))
            wyn.push_back(it->first);
    }
    sort(wyn.begin(),wyn.end());
    cout << wyn.size() << '\n';
    for (int i = 0; i < wyn.size(); ++i)
        cout << wyn[i] << '\n';

    return 0;
}

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

Comments

Zamiast plain text wybierz C++, to się kod pokoloruje.

---

zrobione

---

Ciekawe zadanie. Mam jedynie pomysł na małe przyspieszenie. Miejscem w którym tracimy najwiecej czasu jest zapisywanie dla kazdego napisu krawędzi które obejmuje. Jak startujemy dfs'a z jakigoś wierzchołka, jesteśmy w v i przechodzimy to u to napis (nazwijmy go s1) od korzenia do v i od korzenia do u (nazwijmy s2) rózni się jedną literką. Dodatkowo krawędzie które obejmuje s2 to te same krawędzie które obejmuje s1 + jedna nowa. Dobrze więc gdyby szybko dało się skopiować te krawędzie obejmowanie przez s1 do s2. Można skorzystać z optymalizacji bitowej i tego że jest maks 1000 wierzhołków. Krawędzie które obejmuje napis nie będziemy pamiętać na mapie setów, ale mapie tablic rozmiaru 16 typu int_64. Jeśli odwiedziliśmy krawędź x to zamieniamy x-ty bit w binarnej reprezentacji tych 16 liczb na 1. (wzieliśmy 16, bo 16*64 = 1024 > 1000). Teraz jak mamy wypełnioną tę tablicę dla napisu s1 i wypełniamy dla s2 to iterujemy się po tych 16 liczbach dla s1 i robimy operacje OR z liczbami z tablicy dla s2. Tym samym zbiliśmy czas kopiowania obejmowanych krawędzi z liniowego od ilości wierzchołków do stałego (o stałej 16)

---

Chodzi mi o to, żeby zaimplementować coś jak bitset i skorzystać z tego, że operacje na typach elementarnych działają błyskawicznie. Tylko nie wiem jak zaimplementowany jest bitset, czy korzysta z int64 czy np. int32 (a lepiej korzystać z 64)

---

I to ma O(N^2 * 16)?

---

Chyba tak. Dotychczas tylko raz spotkałem się z zadaniem w którym taka optymalizacja pomogła, ale to było jakieś zadanie z codeforces

Answer 1

Wróciłem dzisiaj do tego zadania, omówię rozwiązanie, które wchodzi na 100pkt.

Pierwsze spostrzerzenie jest dość oczywiste.

1 - Poprawny szablon musi zaczynać się w jakimś liściu i iść ścieżką do jakiegoś innego wierzchołka. Gdyby tak nie było, to krawędź od liścia do rodzica liścia nie byłaby użyta. Co więcej możemy zacząć z dowolnego liścia i puścić algorytm dfs do znalezienia wszystkich kandydatów na wynik. Trzeba tutaj uważać, żeby nie trzymać w dfs-ie całego napisu, dlatego robimy drzewo trie. Ukorzeniamy je w liściu i napełniamy to drzewo trie idąc dfs-em od liścia. Zauważmy, że będziemy mieć maksymalnie około n kandydatów na wynik.

No to mamy n kandydatów i trzeba umieć jakoś sprawdzić, który jest poprawnym szablonem. Zrobimy to w dwóch fazach. Chcemy dla każdego wierzchołka w drzewie trie naliczyć vector par (a,b), które mówią nam, że ciąg na ścieżce od wierzchołka a do wierzchołka b w oryginalnym drzewie z treści zadania ma taką samą wartość jak nasz wierzchołek w drzewie trie na ścieżce od korzenia drzewa trie do niego. Żeby to naliczyć, skorzystamy z tego, że n <= 2000, czyli możemy z każdego wierzchołka w drzewie z treści zadania puścić dfs-a, bo będziemy mieć wtedy o(n^2). Tak wiec robimy puszczamy dfs-a z każdego wierzchołka. Powiedzmy, że puściliśmy go aktualnie od wierzchołka x. W dfs-ie trzymamy aktualny wierzchołek w oryginalnym drzewie, oraz jaki numer ma ścieżka od x do y, (gdzie y, to aktualny wierzchołek w dfs-ie). Idziemy tylko wtedy, gdy dana literka ma krawędź w drzewie trie. Tak więc pozbyliśmy się za pomocą drzewa trie niepotrzebnego kopiowania napisów, wszystko mamy szybciutko.

Mamy policzone dla każdego wierzchołka w drzewie trie jakie ścieżki w oryginalnym drzewie mają taką samą wartość jak ścieżka z korzenia drzewa trie do niego, teraz musimy jakoś sprawdzić, czy da się całkowicie pokryć drzewo tymi ścieżkami. Zrobimy to korzystając z programowanie dynamicznego na drzewie. Dodajemy w wierzchołkach a i b, odejmujemy 2 w wierzchołku lca(a,b), gdzie lca(a,b) to najniższy wspólny przodek wierzchołków a i b. Przetwarzając it-y wierzchołek dp[v] = suma dp dzieci + to co dodaliśmy / usuneliśmy. Zauważmy, że krawędź do rodzica jest pokryta wtedy i tylko wtedy, gdy dp[v] > 0. Jeżeli dla wszystkich wierzchołków nie licząc korzenia dp[v] > 0, to drzewo da się pokryć takim szablonem, w przeciwnym razie nie.

Pozostaje pytania jaką ten algorytm ma złożonność. Kandydatów na wynik mamy około n, każdego przetwarzamy w o(n), czyli przetworzenie kandydatów ma o(n^2). Taką samą złożonność ma znalezienie kandydatów. Pozostaje pytanie co z lca par wierzchołków a i b oraz jak odtworzyć wynik. Limity zadania pozwalają nam na o(n^2* log n), czyli lca można znajdywać klasycznie jump pointerami w o(log n) oraz skoro mamy n kandydatów i każdy ma długość co najwyżej n-1, to możemy wrzucić wszystkie wyniki (w stringach) na seta / na vector i posortować i wypisać w kolejności posortowanej. Takie rozwiązanie ma o(n^2 * lg n) i jak najbardziej wchodzi na 100pkt, za bardzo dużym zapasem. Da sie to usprawnić do o(n^2) korzystając z tego, że nie trzeba liczyć lca za każdym razem oddzielnie w logu, tylko skoro mamy n <= 2000, to możemy dfs-em spreprocesować sobie lca dla każdej pary albo oddzielnie, albo wtedy gdy naliczamy te wszystkie pary (a,b). A jeśli chodzi o wypisywanie wyniku to drzewo trie daje nam porządek alfabetyczny wiec wydaje się, że można poprostu dfs-em w o(n^2) znaleźć wszystkie wyniki, tylko jest jeden problem, że jak pasuje szablon x, to szablon równy x, tylko w odwróconej kolejności też jest szablonem, wiec możemy zbudować już pod koniec drugie drzewo trie, na które dodamy wszystki oryginalne szablony spełniające wynik i wszystkie odwrócone szablony. W ten sposób możemy puścić dfs-a na takim drzewie trie i dostaniemy o(n^2).

Więcej o drzewach trie można zobaczyć np. tutaj:

- https://www.youtube.com/watch?v=MBIe1gBiWwY

- https://www.youtube.com/watch?v=RDRJpl-jUG4

- Było też takie zadanie na oi Midas.

Więcej o lca i jump pointerach:

- zadanie randka oi

- zadanie komiwojażer bajtazar oi

- zadanie odwiedziny oi

- https://www.youtube.com/watch?v=4tzs0brpbWA

- https://www.youtube.com/watch?v=IRMdwFMJ_NI&t=2041s

- https://www.youtube.com/watch?v=ub1E2lSuafc

- https://www.youtube.com/watch?v=x3pf0aiWgnI

 

Jeżeli kogoś interesuje ta sztuczka z dodawaniem 1 w liściach i odejmowaniem 2 w lca, to było takie zadania z ceoia, bardzo polecam: https://oj.uz/problem/view/CEOI17_oneway

Mam nadzieję, że rozwiązanie jest dobrze opisane.