Zadanie warsztaty OIG

Question

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!

Answer 1

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?

Comments

Mi się nie udało wymyśleć, jak takie łączenie robić. Próbowałem robić osobny vector reprezentantów i potem zmieniać idxy grup, ale tych zmian będzie i tak dużo i nie przeszło.

---

No to ja twierdzę, że jeżeli musisz przekolorować auta koloru x na kolor y i v_x, v_y to wektory które trzymają auta odpowiednio kolorów x lub y to wystarczy że przeniesiesz zawartość mniejszego z tych vektorów do tego więszkego. I wtedy po wszystkich m przekolorowaniach nie wykonasz więcej niż nlogn przenoszeń

---

Mógłbyś uzasadnić dlaczego nie dostaniemy więcej niż n log n przenoszeń?, nie rozumiem zbytnio dlaczego. Ale faktycznie intuicyjnie wydaje się że to prawda.

---

Weźmy sobie dowolne auto. Jeżeli je przenosimy z vectora rozmiaru x do vectora rozmiaru y, to znaczy że x+y>=2*x. Czyli rozmiar vecotra w którym znajude się dane auto rośnie za każdym razem co najmniej dwukrotnie. No czyli każdy element przeniesiemy maksymalnie logn razy.

---

Faktycznie racja. Jak wrócę ze szkoły to zaimplementuję i dam znać jak wyszło.

---

@Whistleroosh, A masz może sposób jak to implementować, żeby nie musieć kasować mniejszego vectora? Próbowałem z kasowaniem, ale pamięc nie przeszła. Dla 90% testów

---

Pamięć powinna bez problemu przejść. Usuwasz elementy z tego mniejszego vectora?

---

Mój kod: prawie każdy test wywala pamięć: 

#include <iostream>
#include <vector>

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;
    int wczytany_samochod = 0;
    int kolor_od = 0;
    int kolor_do = 0;
    vector<int> samochody;
    vector<vector<int>> grupy;
    vector<int> zawsze_pusty;

    cin >> n >> m >> k;

    int kolory[k+1];
    int statystyki_kolorow[k+1];
    for (int i = 1; i <= k; ++i)
    {
        kolory[i] = i-1;
        grupy.push_back({i});
    }

    for (int i = 0; i < n; ++i)
    {
        cin >> wczytany_samochod;
        samochody.push_back(wczytany_samochod);
    }

    for (int i = 0; i < m; ++i)
    {
        cin >> kolor_od >> kolor_do;
        if (grupy[kolory[kolor_od]].size() <= grupy[kolory[kolor_do]].size())
        {
            if (grupy[kolory[kolor_od]].size() != 0)
            {
                for (int j = 0; j < grupy[kolory[kolor_od]].size(); ++j)
                {
                    grupy[kolory[kolor_do]].push_back(grupy[kolory[kolor_od]][j]);
                }
                grupy.push_back(zawsze_pusty);
                kolory[kolor_od] = grupy.size()-1;
            }
            else
            {
                // Zamieniamy tylko grupy
                int zapamietanie = 0;
                zapamietanie = kolory[kolor_od];
                kolory[kolor_od] = kolory[kolor_do];
                kolory[kolor_do] = zapamietanie;
            }
        }
        else
        {
            if (grupy[kolory[kolor_do]].size() != 0)
            {
                for (int j = 0; j < grupy[kolory[kolor_do]].size(); ++j)
                {
                    grupy[kolory[kolor_od]].push_back(grupy[kolory[kolor_do]][j]);
                }
                grupy.push_back(zawsze_pusty);
                kolory[kolor_do] = grupy.size()-1;
            }
            else
            {
                // Zamieniamy tylko grupy
                int zapamietanie = 0;
                zapamietanie = kolory[kolor_do];
                kolory[kolor_do] = kolory[kolor_od];
                kolory[kolor_od] = zapamietanie;
            }
        }
    }

    for (int i = 1; i <= k; ++i)
    {
        for (int j = 0; j < grupy[kolory[i]].size(); ++j)
        {
            statystyki_kolorow[grupy[kolory[i]][j]] = i;
        }
    }

    for (int i = 0; i < n; ++i)
    {
        cout << statystyki_kolorow[samochody[i]] << " ";
    }

    return 0;
}

 

---

Zamieniłem, że nie robimy tego z samochodami, tylko z kolorami aut, bo ich powinno być mniej. Tak też może być?

---

Nie czyścisz tych mniejszych vectorów. Jak przenosisz elementy z vectora mniejszego do większego to musisz te elmenty z vectora mniejszego usunąć. A poza tym wygląda dobrze

---

Ale muszę je czyścić jak tworze nowe puste i je przypisuję jako porównywalne? Myślałem, że w ten sposób wyjdzie lepsza złożonnośc pamięciowa.

---

Nie rozumiem co dokładnie chcesz zrobić. Z tego co widzę dodajesz nowy pusty vector na koniec i ustawiasz, że on teraz przechowuje kolory "od" lub "do". Ale ten wektor  grupy[kolory[kolor_do]] i grupy[kolory[kolor_od]] wciąż tam w pamięci gdzieś jest

---

Ogólnie próbowałem to długo zaimplementować (zrobiłem clearowanie vectorów) ale...

Twój algorytm faktycznie działa w O(n log n) czasowo, jednak samo stworzenie vectora i przechowywanie tam pustych początkowych elementów zajmuje już 1/3 dostępnej pamięci. A potem to się bardzo rozrasta. Mi nie udało się tego zaimplementować. Jeśli komuś się uda to bardzo prosił bym o jakieś podpowiedzi.

---

Można zaimplementować tak:

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

typedef uint32_t ul;
typedef int32_t l;
typedef uint64_t ull;
typedef int64_t ll;

const l INF = 1000000000 + 9;
const ll MOD = 123456789;
const l PRIME = 200003;
const ll L_INF = 1000000000000000000LL + 7;
const double EPS = 1e-5;

#define FOR(x, y, z) for (l z = x; z < y; z++)
#define FORE(x, y, z) for (l z = x; z <= y; z++)
#define FORD(x, y, z) for (l z = x; z > y; z--)
#define FORDE(x, y, z) for (l z = x; z >= y; z--)
#define REP(x, y) for (l y = 0; y < x; y++)
#define ALL(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()

#define PF push_front
#define POF pop_front
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FS first
#define SC second

l n, m, k;
l car_color[1000005];
vector<l> *color_groups[1000005];

void UNION(l from, l to) {
    if (!color_groups[from] && !color_groups[to])
        return;

    else if (color_groups[from] && !color_groups[to]) {
        color_groups[to] = color_groups[from];
        color_groups[from] = nullptr;
        return;
    }

    else if (!color_groups[from] && color_groups[to])
        return;

    if (color_groups[from]->size() > color_groups[to]->size())
        swap(color_groups[from], color_groups[to]);

    while (color_groups[from]->size()) {
        color_groups[to]->PB(color_groups[from]->back());
        color_groups[from]->POB();
    }

    color_groups[from] = nullptr;    
}

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

    cin >> n >> m >> k;

    fill(color_groups, color_groups+1000005, nullptr);

    FORE(1, n, i) {
        l a;
        cin >> a;

        if (!color_groups[a])
            color_groups[a] = new vector<l>;

        color_groups[a]->PB(i);
    }

    REP(m, i) {
        l from, to;
        cin >> from >> to;
        UNION(from, to);
    }

    FORE(1, 1000000, i)
        if (color_groups[i])
            for (auto car: *color_groups[i])
                car_color[car] = i;

    FORE(1, n, i)
        cout << car_color[i] << " ";
    cout << "\n";
}

Jeżeli pamięć Ci się rozrasta to cos nie tak implementujesz. U mnie jest stała

---

@pasjonat_algorytmiki Z tego co sprawdziłem, moje rozwiązanie dostaje niestety TLE, choć nie powinno. W takim razie innym pomysłem na rozwiąznie tego zadania jest po prostu Find & Union

---

Gdzie mogę znaleźć jakieś materiały o union findize? Nigdy się z taką techniką nie spotkałem.

---

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

---

Okej dzięki, przeczytam i postaram rozwiązać.

---

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ć.

---

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

---

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

Answer 2

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.