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

Zadanie Skarbonki OI, Silnie Spójne Składowe, Optymalizacja Pamięci

Aruba Cloud - Virtual Private Server VPS
0 głosów
531 wizyt
pytanie zadane 1 lutego 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Mam takie zadanie: https://szkopul.edu.pl/problemset/problem/lm7lS3cC3aTRwlRaCztGRkov/site/?key=statement

Rozwiązanie jest dobre, a mianowicie: traktuję całość jako graf o n wierzchołkach i n krawędziach, a mianowicie, jeśli wiemy, że numer i-ty klucz jest w skarbonce x, to robimy krawędź skierowana i - > x, i taki graf dzielimy na silnie spójne składowe, i wyn to ile wszystkich spójnych składowych - ile_krawedzi w grafie, gdzie każda spójna składowa to wierzchołek. Tylko jest jeden problem, a mianowicie pamięc. Napisałem kod na 72pkt, gdzie dzielę graf na SCC 2 dfs-ami jeden, żeby ustalić kolejnośc post order, potem odwracam krawędzie i w tej kolejności post order odpalam DFS-y i to są silnie spójne składowe. Żeby odwrócić krawędzie muszę zrobić vector vectorów, a limit to 32MB, próbowałem też na multisecie trzymać krawędzie postaci a->b, ale to też zawolne. Nie wiem co zrobić dalej, bo problemem jest też to jak zliczyć ile jest krawędzie w tym grafie silnie spójnych składowych.

Z góry dziękuję za pomoc!
komentarz 1 lutego 2023 przez Whistleroosh Maniak (57,400 p.)
To się da rozwiązać dużo prościej bez SCC. Rozrysuj sobie graf jaki powstanie i zobacz jaki będzie miał kształt

1 odpowiedź

+1 głos
odpowiedź 2 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 2 lutego 2023 przez pasjonat_algorytmiki

 Whistleroosh zrobiłem, to bardzo fajnym pomysłem (pewnie chodziło Ci o to samo), dzięki za hinta, tak to bym pewnie się pomęczył i zaklepał SCC, a tak to poznałem bardzo fajny sposób, opiszę krótko rozwiązanie, jakby ktoś kiedyś się męczył. Mianowicie:

Zastanówmy się co oznacza nasza krawędź i -> j, w grafie. Oznacza, że klucz i jest w skrzynce j, ale co kluczowe jeśli mamy jakąś scieżkę wierzchołków. Np:  

To otwierając skrzynkę w wierzchołku żółtym otworzymy wszystkie wierzchołki na ścieżce, które idą do niego! Nigdy nie opłaca nam się otworzyć w którymś czarnym wierzchołku, skoro mozna otworzyć w żółtym i mieć to samo co w czarnym + dodatkowe. Zauważmy, że całośc polega, na podzieleniu grafu, na pod drzewa, tak, żeby w podrzewie było jak najwięcej wierzchołków. A to robimy już bardzo prosto, idziemy sobie DFS-em i jeśli natkniemy się na inne poddrzewo, to poprostu dołączamy całą ścieżkę sprawdzaną do tego podrzewa, i nic nie dodajemy do wyniku. Natomiast, jeśli natkniemy się na podrzewo aktualne (te co mamy na ścieżce sprawdzanej), to znaczy, że tworzymy nowe podrzewo i wyn++.

O(N), bo każdy wierzchołek maksymalnie raz odwiedzimy. Kod bardzo skomplikowany, wystarczy jednego DFS-a puścić ;), koło 10 linii, oprócz wczytania danych i wypisania, includów, deklaracji zmiennych / vectorów itp. :)

#include <iostream>
#include <vector>

using namespace std;

int n = 0, wczytana_liczba = 0, wyn = 0, numer_spojnej = 0;
vector<int> krawedz;
vector<int> w_jakiej_spojnej;

void DFS(int v)
{
    w_jakiej_spojnej[v] = numer_spojnej;
    if (w_jakiej_spojnej[krawedz[v]] == -1)
        DFS(krawedz[v]);
    else if (w_jakiej_spojnej[krawedz[v]] == numer_spojnej)
        wyn++;
}

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

    cin >> n;
    krawedz.assign(n+1,0);
    w_jakiej_spojnej.assign(n+1,-1);
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        krawedz[i+1] = wczytana_liczba;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (w_jakiej_spojnej[i] == -1)
        {
            DFS(i);
            numer_spojnej++;
        }
    }
    cout << wyn << '\n';

    return 0;
}

Przykładowe drzewa, jeśli wynik jest 2. (Wynik to zawsze liczba drzew). Na żółto korzenie drzewa

Bardzo podobne jest zadanie Speedrun z 2 etapu XIV OIJ. Jest wątek na forum.

Jeszcze raz dzięki za hinta. Tobie też chodziło o to samo, czy jest jakiś inny pomysł oprócz tego / SCC?

komentarz 2 lutego 2023 przez Whistleroosh Maniak (57,400 p.)
Tak, mniej więcej chodziło mi o to samo. Ogólnie warto pamiętać że graf w którym z każdego wierzchołka wychodzi dokładnie jedna krawędź ma charakterystyczny kształt. Każda spójna to po prostu jeden cykl z drzewami ukorzenionymi na którymś wierzchołku z cyklu
komentarz 2 lutego 2023 przez Whistleroosh Maniak (57,400 p.)
Tę wersję z SCC dałoby sie pewnie poprawić żeby weszło na 100. Brakowało pamięci pewnie przez rekurencje dfs'a, więc wystarczyło go zrobić iteracyjnie
komentarz 2 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Tylko tam był problem, że jak odwracasz krawędzie do 2 DFS-a to musi być już vector vectorow i na starcie 20MB, bo N do miliona. A set też nie wyrabiał pamięciowo.

Podobne pytania

0 głosów
1 odpowiedź 539 wizyt
0 głosów
1 odpowiedź 171 wizyt
0 głosów
1 odpowiedź 914 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

93,327 zapytań

142,323 odpowiedzi

322,396 komentarzy

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

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...