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

Zadanie warsztaty OIG

VPS Starter Arubacloud
+1 głos
531 wizyt
pytanie zadane 10 kwietnia 2022 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Cześc,jakicz czas temu napotkałem się na zadanie warsztaty z 4 edycji OIG - link szkopul:

https://szkopul.edu.pl/problemset/problem/75WTu9ZZJlfrT_dO204-8djk/site/?key=statement

Wtedy nie umiałem go zrobić, teraz do niego wróciłem i łącznie poświęciłem na nie ponad 15 godzin, i jedyne co udało mi się to napisać bruta w O(n*m) poprostu za każdym razem zmieniając wartości samochodów wartego 27pkt.

Ma ktoś pomysł jak można podejśc do tego zadania?

Z góry dziękuję za pomoc!

2 odpowiedzi

+2 głosów
odpowiedź 10 kwietnia 2022 przez Whistleroosh Maniak (56,980 p.)
wybrane 17 lutego 2023 przez pasjonat_algorytmiki
 
Najlepsza

Mam dwa pomysły. Na razie dam hinta do tego pierwszego. Co by było gdybyśmy dla każdego koloru trzymali wszystkie auta w tym kolorze np. w jakimś vectorze. I teraz musimy musimy przemalować wszystkie auta koloru 1 na kolor 2. Czy jesteśmy w stanie jakos szybko połączyć vectory 1 i 2? Albo czy jesteśmy w stanie tak je łączyć, żeby po wykonaniu wszystkich m przekolorowań tych przenoszeń poszczególnych elementów w vectorach było jak najmniej?

komentarz 14 kwietnia 2022 przez Whistleroosh Maniak (56,980 p.)
Ogólnie gdyby to było zadanie z OI to moje pierwsze rozwiązanie powinno przejsć na 100. Nie wiem dlaczego dali tutaj takie małe limity czasowe. Tu możesz poczytać o F&U: https://platform.meetit.pl/articles/dan_fau
komentarz 14 kwietnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Okej dzięki, przeczytam i postaram rozwiązać.
komentarz 22 kwietnia 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Kod który znalazłem daje 100pkt.

/**
 * IV Olimpiada Informatyczna Gimnazjalistów
 * Zadanie: Warsztaty
 * Wynik 100/100
 * Wykonał: Marcin Wątroba
 * http://main.edu.pl/pl/archive/oig/4/war
 */

#include <iostream>
#include <cstdio>
#include <utility>

using namespace std;

int main() {
    int n, m, k;
    //cin >> n >> m >> k;
    scanf("%d%d%d", &n, &m, &k);
    int *samochody = new int[n];
    for (int a = 0; a < n; a++)
        //cin >> samochody[a];
        scanf("%d", &samochody[a]);
    int *kol = new int[k + 1];
    for (int a = 1; a < k + 1; a++)
        kol[a] = a;

    pair<int, int> *pom = new pair<int, int>[m];
    for (int a = 0; a < m; a++)
        //cin >> pom[a].first >> pom[a].second;
        scanf("%d%d", &pom[a].first, &pom[a].second);

    for (int a = m - 1; a >= 0; a--)
        kol[pom[a].first] = kol[pom[a].second];

    for (int a = 0; a < n; a++)
        //cout << kol[samochody[a]] << " ";
        printf("%d ", kol[samochody[a]]);

    system("PAUSE");
    return 0;
}

Jak ktoś rozumie to może wytłumaczyć.

komentarz 22 kwietnia 2022 przez Whistleroosh Maniak (56,980 p.)
Ciekawe rozwiązanie. Tu jest zastosowany trick z "odwracaniem czasu" popularny na OI. Czyli jak mamy jakieś zmiany w czasie to zamiast patrzeć na te zmiany od najnowszej do najstarszej to patrzymy od najstarszej do najnowszej
komentarz 22 kwietnia 2022 przez Whistleroosh Maniak (56,980 p.)
O tym rozwiązaniu łatwiej się myśli graficznie. Tu jest rysunek poglądowy: https://ibb.co/RPTr98N

Wierzchołki w danej kolumnie oznaczają kolejne kolory (w tym przypadku kolory a, b, c i d). Kolejne kolumny reprezentują jak kolory "zmieniają się" w czasie. Czyli jak np. na początku zamieniamy auta koloru c na b to dajemy krawędź c -> b między pierwsza i drugą kolumną. Jak potem zamieniamy auta koloru b na d to dajemy krawędź b -> d między drugą i trzecią kolumną itd. Jeśli jakis kolor się nie zmienia to dajemy strzałke od tego koloru do tego samego koloru (u mnie te strzałki są rysowane przerywaną linią). Teraz jeżeli chcemy powiedzieć jakiego koloru na końcu będa auta początkowo koloru c, to idziemy krawędziami (ta czerwona ścieżka) od wierzchołka c pierwszej kolumny do ostatniej kolmny i widzimy, że te auta będa koloru d. Teraz chyba od razu widać dlaczego ten krótki algorytm działa
0 głosów
odpowiedź 10 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Tak jeszcze swoją drogą. Znalazłem dzisiaj ciekawy wykład z F&U - bardzo polecam: https://www.youtube.com/watch?v=EQIFihYife4 , dobrze tłumaczy zagadnienie. I zacząłem pisać kod z F&U i natknąłem się na bardzo ciekawy pomysł - trochę podmienienie tego z pomysłem F&U a mianowicie:

mamy 2 tablicę. Jedna to tablica kolory[k] oznaczająca jaka grupa odpowiada za dany kolor. Oraz tablicę vectorów zaleznosci, która mówi nam np grupa 2 jest zależna od grupy 4 (takie tak jakby F&U tylko nie przepinamy korzenia)

I jak dostajemy np 2->4 , to zmieniamy kolor[2] na 0 i kolor 4 zostawiamy jeśli tam coś jest i dopinamy - dodajemy zaleznosci[kolory[4]].push_back(kolory[2]), jak niema nic to poprostu zamianiamy kolory[4] = 2.

I w ten sposób na koniec algorytmu lecimy po kolorach od 1 do n i musimy odczytywać po zależnościach na kolejce tak jakby BFS-em. np dla i = 1. jak kolory[1] = 5, to oznacza ze grupa 5 i jej zaleznosci są odpowiedzialne za kolor 1. W ten sposób mamy O(n+m) złożonnośc zamortyzowana. Mój kod:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

    int n = 0;
    int m = 0;
    int k = 0;

    cin >> n >> k >> m;
    int samochody[n];
    int kolory_po_zmianie[m + 1];
    int kolory[m + 1];
    vector<int> zaleznosci[m + 1];

    for (int i = 0; i < n; ++i)
    {
        cin >> samochody[i];
    }

    for (int i = 0; i <= m; ++i)
    {
        kolory[i] = i;
        kolory_po_zmianie[i] = i;
    }

    for (int i = 0; i < k; ++i)
    {
        int kolor_od = 0;
        int kolor_do = 0;
        cin >> kolor_od >> kolor_do;

        if (kolory[kolor_od] == 0 || kolor_od == kolor_do)
        {
            continue;
        }
        else if (kolory[kolor_do] == 0)
        {
            kolory[kolor_do] = kolory[kolor_od];
            kolory[kolor_od] = 0;
        }
        else
        {
            zaleznosci[kolory[kolor_do]].push_back(kolory[kolor_od]);
            kolory[kolor_od] = 0;
        }
    }

    for (int i = 1; i <= m; ++i)
    {
        queue<int> Q;
        kolory_po_zmianie[kolory[i]] = i;
        for (int j = 0; j < zaleznosci[kolory[i]].size(); ++j)
        {
            Q.push(zaleznosci[kolory[i]][j]);
            kolory_po_zmianie[zaleznosci[kolory[i]][j]] = i;
        }
        while (!Q.empty())
        {
            for (int j = 0; j < zaleznosci[Q.front()].size(); ++j)
            {
                Q.push(zaleznosci[Q.front()][j]);
                kolory_po_zmianie[zaleznosci[Q.front()][j]] = i;
            }
            Q.pop();
        }
    }

    for (int i = 0; i < n; ++i)
    {
        printf("%d ",kolory_po_zmianie[samochody[i]]);
    }
    return 0;
}

Niestety dostaję 93pkt, bo mam jakiś błąd w odtczytywaniu (implementacja) (pewnie gdzies brakuje jakiegos if-a) i na 47 testów jeden ma przekroczenie limit czasu. (bardzo wczesny 5c.) Jak znajdę to zaktualizuję kod.

Ogólnie to całe zadanie, żeby zrobić w O(n+m) to strikte chyba na pomysł. Jak napiszę z F&U to też wrzucę.

Wyniki czasowe dla pozostałych testów minimalnie lepsze niż to rozwiązanie z zmienianiem czasu.

Podobne pytania

0 głosów
0 odpowiedzi 465 wizyt
pytanie zadane 16 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
2 odpowiedzi 407 wizyt
pytanie zadane 28 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
0 głosów
1 odpowiedź 166 wizyt
pytanie zadane 24 marca 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,773 zapytań

141,696 odpowiedzi

320,530 komentarzy

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

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!

...