• 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

Object Storage Arubacloud
0 głosów
284 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 (56,980 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 (56,980 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 (56,980 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ź 283 wizyt
0 głosów
1 odpowiedź 128 wizyt
0 głosów
1 odpowiedź 583 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,660 zapytań

141,553 odpowiedzi

319,994 komentarzy

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

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

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!

...