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