Zadanie Odleglość OI, Grafy

Question

Robię zadanie Odległość z 1 etapu XIX OI: https://szkopul.edu.pl/problemset/problem/oK44vqt7NCKfz0ABHGh4gfAT/site/?key=statement

Zrobiłem na 30pkt(te ograniczenie pisze w treści N <= 1000 -> 30pkt), w O(N^2 * lg N), a mianowicie dla każda liczbe rozkladam na czynniki pierwsze z sitem, w O(N*168) (168, bo liczb pierwszych do pierwiastka z miliona jest tyle), i dla każdego i, porownuje z kazdym innym j, czyli O(N^2) i jeszcze czas porownania to log z N, bo liczba ma logarytmicznie wiele czynników pierwszych. Kod:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

int n = 0, wczytana_liczba = 0, min_idx = -1, min_dp = -1, wyn = 0, wyn_idx = 0;
vector<bool> sito(1e6+1,false);
vector<int> P;
vector<int> liczby;
vector<vector<int>> faktoryzowane;

int odleglosc(int x, int y)
{
    int L_x = liczby[x], L_y = liczby[y], wyn = 0, wsk_y = 0;
    if (L_x == 1 && L_y == 1)
        return 0;
    else if (L_x == 1)
        return faktoryzowane[y].size();
    else if (L_y == 1)
        return faktoryzowane[x].size();
    for (int i = 0; i < faktoryzowane[x].size(); ++i)
    {
        if (wsk_y == faktoryzowane[y].size())
        {
            wyn += faktoryzowane[x].size() - i;
            break;
        }
        if (faktoryzowane[x][i] == faktoryzowane[y][wsk_y])
            wsk_y++;
        else if (faktoryzowane[x][i] < faktoryzowane[y][wsk_y])
            wyn++;
        else if (faktoryzowane[x][i] > faktoryzowane[y][wsk_y])
        {
            wyn++;
            wsk_y++;
            i--;
        }
    }

    return wyn + (faktoryzowane[y].size() - wsk_y);
}

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

    for (ll i = 2; i <= (ll)1e6; ++i)
    {
        if (sito[i] == false)
        {
            P.push_back(i);
            for (ll j = i * i; j <= 1e6; j += i)
                sito[j] = true;
        }
    }

    cin >> n;

    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        liczby.push_back(wczytana_liczba);
        faktoryzowane.push_back({});
        for (int j = 0; j < P.size(); j+=0)
        {
            if (P[j] * P[j] > wczytana_liczba)
                break;
            if (wczytana_liczba % P[j] == 0)
            {
                faktoryzowane[i].push_back(P[j]);
                wczytana_liczba /= P[j];
            }
            else
                j++;
        }
        if (wczytana_liczba != 1)
            faktoryzowane[i].push_back(wczytana_liczba);
        sort(faktoryzowane[i].begin(),faktoryzowane[i].end());
    }
    for (int i = 0; i < n; ++i)
    {
        wyn = 1e9, wyn_idx = 1e9;
        for (int j = 0; j < n; ++j)
        {
            if (i == j)
                continue;
            int odl = odleglosc(i,j);
            if (odl != -1)
            {
                if (odl < wyn)
                {
                    wyn = odl;
                    wyn_idx = j;
                }
            }
        }
        cout << wyn_idx+1 << '\n';
    }

    return 0;
}

Mam problem jak podejść lepiej do tego zadania, bo tego pomysłu raczej nie da się przyśpieszyć. Myślałem, żeby puścić BFS-a równolegle (dodać wszystkie początkowe wierzcholki na kolejke) i iść sobie BFS-em, tylko nawet, gdy założę, że z wierzchołka x mogę iść do wszystkich jego liczb w rozkładnie na czynniki pierwsze(w sensie x / P[i]), czyli przy dzieleniu mam logarytmicznie wiele krawędzi z wierzcholka, to mam 2 problemy. Mianowicie:

1 - Nie wiem jak duży może być mój graf

2 - Jak obsłużyć dzielenie, sprawdzanie wszystkich liczb pierwszych, aż do momentu gdy x * P[i] > rozmiar grafu, może być zawolne.

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

Comments

Ale nie wiem, czy ten BFS, to dobry pomysł do tego zadania

Answer 1

Co do rozmiaru grafu to trzeba zrobić kilka obserwacji.

1) Wystarczy dodawać same krawędzie "dzielenia", bo jeśli masz krawędź a<->b reprezentującą dzielenie a / p = b, to jest to samo jakbys dodał krawędź "mnożenia" b * p = a.

2) Kolejność operacji nie ma znaczenia. Można założyć że przy przekształcaniu a w b (wieloma operacjami mnożenia/dzielenia) na początku wykonywalismy samo dzielenie a potem samo mnożenie. Ale to znaczy że przy przekształcaniu a w b nigdy nie otrzymaliśmy liczby większej od b. Zatem mamy max 1e6 wierzchołków

3) Ilość krawędzi wychodzących z wierzchołka x można oszacować przez log(x), ale w rzeczywistości będzie to dużo mniej (dla tego zadania maksymalnie 8. Dlaczego?). To znaczy że graf ma maksymalnie 1e6*8 krawędzi

Ogólnie pomysł z BFS'em jest dobry, tylko trzeba go zmodyfikować

Comments

Bo 2*3*5*7*11*13*17*19 w najgorszym wypadku. Ale da się szybciej sfaktoryzować liczby do miliona niż sitem wygenerować liczby pierwsze do pierwiasteka, i dla każdej liczby od 1 do 10^6 sprawdzic te 168 czy ile jest tych dzielników pierwszych?

---

Można dla kazdej liczby ztablicować najmniejszą liczbę pierwszę przez którą jest podzielna. Wtedy faktyryzacja jednej liczby trwa liniowo od rozmiaru rozkładu

---

Napisałem coś takiego:

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

using namespace std;
typedef long long ll;

struct Element_kolejki
{
    int wierzcholek;
    int jaki_poczatek;
};

int n = 0, wczytana_liczba = 0, wierzcholki_SIZE = 1e6;
vector<int> zapytania;
vector<vector<int>> faktoryzowane;
vector<bool>sito(wierzcholki_SIZE+1,false);
vector<int> P;
vector<pair<int,int>> dp; // Wartosc dp i jaki numer tam jest
vector<vector<int>> krawedzie;
vector<pair<int,int>> wyniki; // Wynik, numer wierzcholka
queue<Element_kolejki> Q;
vector<pair<int,int>> stat;

int main()
{
    // Mamy graf o 10^6 wierzcholkach i maksymalnie 16*10^6 wierzcholkach.
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for (ll i = 2; i <= (ll)wierzcholki_SIZE / 1000; ++i)
    {
        if (sito[i] == false)
        {
            P.push_back(i);
            for (ll j = i * i; j <= (ll)wierzcholki_SIZE / 1000; j += i)
                sito[j] = true;
        }
    }

    cin >> n;
    stat.assign(wierzcholki_SIZE+1,{-1,-1});
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        if (stat[wczytana_liczba].first == -1)
            stat[wczytana_liczba].first = i+1;
        else if (stat[wczytana_liczba].second == -1)
            stat[wczytana_liczba].second = i+1;
        zapytania.push_back(wczytana_liczba);
    }
    krawedzie.assign(wierzcholki_SIZE+1,{});
    faktoryzowane.assign(wierzcholki_SIZE+1,{});
    for (int i = 1; i <= wierzcholki_SIZE; ++i)
    {
        wczytana_liczba = i;
        for (int j = 0; j < P.size(); j += 0)
        {
            if (P[j] * P[j] > wczytana_liczba)
                break;
            if (wczytana_liczba % P[j] == 0)
            {
                wczytana_liczba /= P[j];
                if (faktoryzowane[i].size() == 0)
                    faktoryzowane[i].push_back(P[j]);
                else if (faktoryzowane[i][faktoryzowane[i].size()-1] != P[j])
                    faktoryzowane[i].push_back(P[j]);
            }
            else
                j++;
        }
        if (wczytana_liczba > 1)
        {
            if (faktoryzowane[i].size() == 0)
                faktoryzowane[i].push_back(wczytana_liczba);
            else if (faktoryzowane[i][faktoryzowane[i].size()-1] != wczytana_liczba)
                faktoryzowane[i].push_back(wczytana_liczba);
        }
        for (int j = 0; j < faktoryzowane[i].size(); ++j)
        {
            krawedzie[i].push_back(i / faktoryzowane[i][j]);
            krawedzie[i / faktoryzowane[i][j]].push_back(i);
        }
    }
    dp.assign(wierzcholki_SIZE+1,{-1,-1});
    wyniki.assign(wierzcholki_SIZE+1,{1e9,-1});
    for (int i = 0; i < zapytania.size(); ++i)
    {
        if (dp[zapytania[i]].first == -1)
        {
            Q.push({zapytania[i],i});
            dp[zapytania[i]] = {0,i};
        }
    }
    while(!Q.empty())
    {
        Element_kolejki spr = Q.front();
        for (int i = 0; i < krawedzie[spr.wierzcholek].size(); ++i)
        {
            int v = krawedzie[spr.wierzcholek][i];
            if (dp[v].first == -1)
            {
                dp[v] = {dp[spr.wierzcholek].first + 1,spr.jaki_poczatek};
                Q.push({v,spr.jaki_poczatek});
            }
            else
            {
                if (dp[spr.wierzcholek].second != dp[v].second)
                {
                    if (wyniki[zapytania[spr.jaki_poczatek]].first > dp[spr.wierzcholek].first + dp[v].first + 1)
                        wyniki[zapytania[spr.jaki_poczatek]] = {dp[spr.wierzcholek].first + dp[v].first + 1,dp[v].second};
                    else if (wyniki[zapytania[spr.jaki_poczatek]].first == dp[spr.wierzcholek].first + dp[v].first + 1)
                        wyniki[zapytania[spr.jaki_poczatek]].second = min(wyniki[zapytania[spr.jaki_poczatek]].second,dp[v].second);
                }
            }
        }
        Q.pop();
    }

    for (int i = 0; i < n; ++i)
    {
        if (stat[zapytania[i]].second != -1)
        {
            if (stat[zapytania[i]].first == i+1)
                cout << stat[zapytania[i]].second << '\n';
            else
                cout << stat[zapytania[i]].first << '\n';
        }
        else
            cout << wyniki[zapytania[i]].second + 1 << '\n';
    }

    return 0;
}

Na sprawdzarce daje dobre odpowiedzi, ale daje 0pkt, bo sama faktoryzacja trwa zbyt długo. Ale co nam da, że ztablicujemy najmniejsza liczbę pierwszą, przez którą jest podzielna? Co dalej?

---

Napisałem już coś szybszego, ale dalej jest zawolne:

sito.assign(1e6+1,false)   
 for (ll i = 2; i <= (ll)wierzcholki_SIZE; ++i)
    {
        if (sito[i] == false)
        {
            for (ll j = i ; j <= (ll)wierzcholki_SIZE; j += i)
            {
                 sito[j] = true;
                 krawedzie[j/i].push_back(i);
                 krawedzie[j].push_back(j/i);
            }
        }
    }

edit: daje złe wyniki

---

Powiedzmy że p[i] to najmniejsza liczba pierwsza przez którą podzielne jest i. Wtedy zapamiętujesz p[i] jako czynnik pierwszy i oraz powtarzasz to samo dla i / p[i]

---

No jestem kompletnym idiotą, że tego nie zauważyłem. Bardzo fajny trik z tą faktoryzacją w logu. Wcześniej umiałem tylko, że naiwnie sprawdzam wszystkie liczby pierwsze do pierwiastka, a tu taki fajny pomysł. Napisałem kod co wchodzi na 80pkt:

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

using namespace std;
typedef long long ll;

struct Element_kolejki
{
    int wierzcholek;
    int jaki_poczatek;
};

int n = 0, wczytana_liczba = 0, wierzcholki_SIZE = 0;
vector<int> zapytania;
vector<int>sito;
vector<pair<int,int>> dp; // Wartosc dp i jaki numer tam jest
vector<vector<int>> krawedzie;
vector<pair<int,int>> wyniki; // Wynik, numer wierzcholka
queue<Element_kolejki> Q;
vector<pair<int,int>> stat;
vector<int> faktoryzowane;

int main()
{
    // Mamy graf o 10^6 wierzcholkach i maksymalnie 16*10^6 wierzcholkach.
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        wierzcholki_SIZE = max(wierzcholki_SIZE,wczytana_liczba);
        zapytania.push_back(wczytana_liczba);
    }

    stat.assign(wierzcholki_SIZE+1,{-1,-1});
    for (int i = 0; i < n; ++i)
    {
        if (stat[zapytania[i]].first == -1)
            stat[zapytania[i]].first = i+1;
        else if (stat[zapytania[i]].second == -1)
            stat[zapytania[i]].second = i+1;
    }

    krawedzie.assign(wierzcholki_SIZE+1,{});
    sito.assign(wierzcholki_SIZE+1,0);
    for (ll i = 2; i <= (ll)wierzcholki_SIZE; ++i)
    {
        if (sito[i] == 0)
            for (ll j = i * i; j <= (ll)wierzcholki_SIZE; j += i)
                if (sito[j] == 0)
                    sito[j] = i;
    }
    for (int i = 1; i <= wierzcholki_SIZE; ++i)
    {
        int spr = i;
        faktoryzowane.clear();
        while (sito[spr] > 0)
        {
            if (faktoryzowane.size() == 0)
                faktoryzowane.push_back(sito[spr]);
            else if (faktoryzowane[faktoryzowane.size()-1] != sito[spr])
                faktoryzowane.push_back(sito[spr]);
            spr /= sito[spr];
        }
        for (int j = 0; j < faktoryzowane.size(); ++j)
        {
            krawedzie[i].push_back(i/faktoryzowane[j]);
            krawedzie[i/faktoryzowane[j]].push_back(i);
        }
        if (faktoryzowane.size() == 0)
        {
            krawedzie[i].push_back(i/spr);
            krawedzie[i/spr].push_back(i);
        }
        else if (faktoryzowane[faktoryzowane.size()-1] != spr)
        {
            krawedzie[i].push_back(i/spr);
            krawedzie[i/spr].push_back(i);
        }
    }

    dp.assign(wierzcholki_SIZE+1,{-1,-1});
    wyniki.assign(wierzcholki_SIZE+1,{1e9,-1});
    for (int i = 0; i < zapytania.size(); ++i)
    {
        if (dp[zapytania[i]].first == -1)
        {
            Q.push({zapytania[i],i});
            dp[zapytania[i]] = {0,i};
        }
    }

    while(!Q.empty())
    {
        Element_kolejki spr = Q.front();
        for (int i = 0; i < krawedzie[spr.wierzcholek].size(); ++i)
        {
            int v = krawedzie[spr.wierzcholek][i];
            if (dp[v].first == -1)
            {
                dp[v] = {dp[spr.wierzcholek].first + 1,spr.jaki_poczatek};
                Q.push({v,spr.jaki_poczatek});
            }
            else
            {
                if (dp[spr.wierzcholek].second != dp[v].second)
                {
                    if (wyniki[zapytania[spr.jaki_poczatek]].first > dp[spr.wierzcholek].first + dp[v].first + 1)
                        wyniki[zapytania[spr.jaki_poczatek]] = {dp[spr.wierzcholek].first + dp[v].first + 1,dp[v].second};
                    else if (wyniki[zapytania[spr.jaki_poczatek]].first == dp[spr.wierzcholek].first + dp[v].first + 1)
                        wyniki[zapytania[spr.jaki_poczatek]].second = min(wyniki[zapytania[spr.jaki_poczatek]].second,dp[v].second);
                }
            }
        }
        Q.pop();
    }

    for (int i = 0; i < n; ++i)
    {
        if (stat[zapytania[i]].second != -1)
        {
            if (stat[zapytania[i]].first == i+1)
                cout << stat[zapytania[i]].second << '\n';
            else
                cout << stat[zapytania[i]].first << '\n';
        }
        else
            cout << wyniki[zapytania[i]].second + 1 << '\n';
    }

    return 0;
}

W kilku testach dalej wywala się ta faktoryzacja(na mniejsze testy jest limit 0.1 s i nie zdąrza) Masz pomysł jak to przyśpieszyć? Nawet narazie nie chodzi o BFS-a tylko o faktoryzacje

---

Sprawdziłem rozwiązanie wzorcowe i tylko jedno (z 3) przechodzi na 100 (reszta też ma TLE), także limity czasowe na szkopule muszą być dziwnie ustawione

---

Mi właśnie 3 testy wywala czas

---

Tak samo jest na tej jednej wzorówce. Ktoś po prostu kiepskie limity czasowe ustawił na szkopule

---

Wróciłem do tego wczoraj i te limity są bardzo kiepskie, żeby weszło na 100, to trzeba zrobić 2 rzeczy.

1 - Po wczytaniu ciągu A obliczyć max, a nie ustawić max sztywno na 10^6.

2 - Generowanie całego grafu na początku tak jak pisaliśmy jest zawolne, to już samo daje tle, ale można zrobić to sprytniej. Obliczyć sitem wszystkie liczby pierwsze do max, to działa bardzo szybko, a potem jak w bf-sie jesteśmy w wierzchołku v, to generujemy krawędzie wychodzące z niego dopiero jak jesteśmy w nim. Wiemy, że sumaryczny rozmiar grafu jest mały, wiec możemy sobie na to pozwolić. Mamy dwa rodzaje krawędzi. Pierwszy czyli te krawędzie, gdzie mnożymy v przez jakąś liczbę pierwszą. W tym rodzaju poprostu przeglądamy kolejno liczby pierwsze w kolejności od najmniejszych dopóki v * dana liczba pierwsza <= max. W przypadku tych krawędzi gdzie dzielimy v przez liczbę pierwszą obliczamy je faktoryzując v z sitem, które już mamy naliczone. Dzięki temu po pierwsze nie będziemy generować krawędzi z tych wierzchołków do których nie dojdziemy, ale też co ważniejsze nie będziemy tworzyć vectora vectorów, czy tablicy vectorów co zajmuje trochę czasu.

Ogólnie trzeba być bardzo oszczędny w implementacji tego, bo limity są bardzo ciasne, ale weszło na 100.

To wchodzi na 100pkt.