Zadanie Antytrójkątowe pudełko

Question

Cześć,

Mam problem z zadaniem Antytrójkątowe pudełko z 3 etapu OIJ: https://szkopul.edu.pl/problemset/problem/c-iPsg6lceV8Nkkk9Zw1s1iN/site/?key=statement

Udało mi się dostać 25pkt, pierwsze ograniczenie. Napisałem backtracking i sprwadzam wszystkie możliwe pudełka.

Mój kod:

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

using namespace std;

bool czy_antytrojkatowe(vector<int>& patyczki)
{
    vector<int> spr;
    for (int i = 1; i < patyczki.size(); ++i)
    {
        for (int j = 0; j < patyczki[i]; ++j)
        {
            spr.push_back(i);
        }
    }
    bool czy_antytrojkotowe_flaga = true;
    if (spr.size() <= 2)
    {
        return true;
    }
    else
    {
        int p = -1;
        int k = -1;
        int l = 0;
        for (auto f : spr)
        {
            if (f != -1)
            {
                l++;
                if (p == -1)
                {
                    p = f;
                }
                else if (k == -1)
                {
                    k = f;
                }
                else
                {
                    if (p+k > f)
                    {
                        return false;
                    }
                    p = k;
                    k = f;
                }
            }
        }
    }
    return true;
}


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

    int n = 0;
    int m = 0;
    int wczytana_liczba = 0;

    cin >> n >> m;
    int zliczanie[m+1] {0};

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

    queue<vector<int>> Q;
    set<vector<int>> permutacje;
    vector<int> nap;
    for (int i = 0; i <= m; ++i)
    {
        nap.push_back(0);
    }

    Q.push(nap);
    while(!Q.empty())
    {
        vector<int> sprawdzany = Q.front();
        for (int i = 1; i <= m; ++i)
        {
            sprawdzany[i]++;
            auto it = permutacje.find(sprawdzany);
            if (sprawdzany[i] <= zliczanie[i] && it == permutacje.end() && czy_antytrojkatowe(sprawdzany) == true) // Mozemy postawic, nie znalezlismy permutacji, jest antytrojkatowe.
            {
                permutacje.insert(sprawdzany);
                Q.push(sprawdzany);
            }
            sprawdzany[i]--;
        }
        Q.pop();
    }

    cout << permutacje.size() << endl;
    return 0;
}

Wiem, że pewnie to zadanie polega na zliczaniu a nie generowaniu przypadków.

Ma ktoś pomysł jak rozwiązać to zadanie?

Z góry dziękuję za pomoc!

Comments

Nie wiem jeszcze jakie jest rozwiązanie, ale obserwacja jest taka, że jeśli mamy jakiś zbiór liczb, z których żadne trzy nie tworzą trójkąta, to te liczby po posortowaniu rosną co najmniej tak szybko jak liczby Fibonacciego

---

No tak faktycznie jest taka zasada.

---

Moja obserwacja jest taka: Jeśli mamy jakiś zbiór patyczków które tworzą antytrojkotowe pudełko to przy decyzji interesują nas tylko 2 ostatnie patyczki(największe) Dlatego wydaje mi się że patyczki będzie trzeba przeglądać niemalejaco.

---

Można to na pewno rozwiązać programowaniem dynamicznym, ale dp które wymyśliłem działałoby w O(20*n^2). Gdyby nie było tej stałej 20 to pewnie by weszło na 100pkt, a ze stałą to trudno mi powiedzieć czy zmieści się w limitach

---

A jak ma działać ten dynamik?

---

Jak tak teraz sobie myśle to ten pomysł może nie być poprawny. Ale wyglądał tak, że dp[i, j] to ilość zbiorów (o elementach nie większych niż j) długości i o największej liczbie j, takich że żadne 3 liczby w tych zbiorach nie tworzą trójkąta. Iterujemy sie po i oraz j, a następnie iterujemy się po wszystkich liczbach > j (powiedzmy że aktualna liczba to x). Wtedy dp[i+2, y], dla takich y że y > x + j zwiększamy o dp[i, j]

---

Po wielu godzinach udało mi się zrobić O(n^3) - 75pkt.

Pomysł wygląda następująco:

1 - Na wstępie counting sortem sortujemy patyczki, zostawiamy co najwyżej 2 patyczki tego samego rozmiaru, gdyż każdym ułożeniu pudełka antytrójkątowego nie skorzystamy z 3 lub więcej tych samych patyczków.

i - największy patyczek w rozważanym pudełku antytrójkątowym

j - drugi największy patyczek w rozważanym pudełku antytrójkątowym

dp[i][j] - najwieksza mozliwa liczba uzyskania pudełka antytrójkątowego biorąc pod uwagę, że największe patyczki to i,j

2 - dodajemy do vectora patyczki - przetwarzamy je niemalejąco, gdyż jak zauważmy jeśli mamy jakiś zbiór patyczków tworzących antytrójkątowe pudełko to zastanawiając się przy decyzji czy dodać wystarczy porównywać go z dwoma największymi -> to prowadzi do programowania dynamicznego.

3 - Jeśli i,j to największe patyczki to nigdy w pudełku antytrójkątowym nie skorzystamy z żadnego innego patyczka, więc lecimy poprostu w pętli po i, dla każdego i zaczynamy od i-1 symulując j, a dla każdego j zaczynamy od j-1 symulując k i licząc kombinacje.

(w kodzie i - x, j - y, k - z)

Mój kod:

#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 wczytana_liczba = 0;
    long long wynik = 0;
    vector<int> patyczki {0};

    cin >> n >> m;
    int zliczanie[m+1] {0};
    vector<vector<long long>> dp(m+1,vector<long long>(m+1));
    for (int i = 0; i <= m; ++i)
    {
        for (int j = 0; j <= m; ++j)
        {
            dp[i][j] = 0;
        }
    }

    // Counting sort.
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        zliczanie[wczytana_liczba]++;
    }

    for (int i = 1; i <= m; ++i)
    {
        if (zliczanie[i] == 1)
        {
            patyczki.push_back(i);
        }
        else if (zliczanie[i] >= 2)
        {
            patyczki.push_back(i);
            patyczki.push_back(i);
        }
    }

    for (int x = 1; x < patyczki.size(); ++x)
    {
        for (int y = x - 1; y > 0; --y)
        {
            long long l = 0;
            for (int z = y - 1; z >= 0; --z)
            {
                if (patyczki[z] == patyczki[z+1] && z != y - 1)
                {
                    continue;
                }
                if (patyczki[z] <= patyczki[x] - patyczki[y])
                {
                    l += dp[patyczki[y]][patyczki[z]];
                }
            }
            dp[patyczki[x]][patyczki[y]] = max(dp[patyczki[x]][patyczki[y]],l);
        }
        dp[patyczki[x]][0] = max(dp[patyczki[x]][0],(long long)1);
    }

    for (int i = 0; i <= m; ++i)
    {
        for (int j = 0; j <= m; ++j)
        {
            wynik += dp[i][j];
            //cout << dp[i][j] << " ";
        }
        //cout << endl;
    }

    cout << wynik;
    return 0;
}

To dlaczego jest O(n^3), bo dla każdego sprawdzania lecimy po wszystkich licząc kombinacje. 

Teraz tylko muszę się zastanowić jak jakoś mądrze liczyć statystyki, żeby znikło jedno n. Pewnie jakieś sumy prefiksowe. Jak ktoś ma jakiś pomysł to może napisać.

---

super. Da się pewnie zoptymalizować do O(n^2logn) przy użyciu jakiegoś drzewa przedziałowego.  Nie wpadłem na to, że nie trzeba iterować się po długości końcowego ciągu. To w takim razie chyba dałoby się zoptymalizować mój pomysł do O(n^2)

---

No i się udało. Trochę mi to zajęło, ale wróciłem dzisiaj do tego zadania i napisałem od nowa, doklepałem drzewo przedziałowe w O(N^2 * lg N), przesżło na 100.

Wklejam kod z lekkimi opisami, jakbyktoś się kiedyś męczył:

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

int n = 0, m = 0, wczytana_liczba = 0;
const int base = 2048, rozmiar_drzewa = 4096; // Base, to potega dwojki >= max(M), a max(M) = 1500, wiec najblizsza potega dwojki to 2048.
ll wyn = 0;
vector<int> liczby;
ll dp[1501][1501]; // 1501, bo max M to 1500.
ll drzewo_przedzialowe[1501][rozmiar_drzewa]; // 1501, bo max M to 1500.

inline void update(int x, int v, ll val)
{
    v += base;
    drzewo_przedzialowe[x][v] = val;
    v /= 2;
    while(v > 0)
    {
        drzewo_przedzialowe[x][v] = drzewo_przedzialowe[x][v*2] + drzewo_przedzialowe[x][v*2+1];
        v /= 2;
    }
}

inline ll querry(int x, int l, int p)
{
    l = l + base - 1, p = p + base + 1;
    ll res = 0;
    while(l / 2 != p / 2)
    {
        if (l % 2 == 0)
            res += drzewo_przedzialowe[x][l+1];
        if (p % 2 == 1)
            res += drzewo_przedzialowe[x][p-1];
        l /= 2;
        p /= 2;
    }
    return res;
}

int main()
{
    // O(N^2 * lg N)
    // Ulepszenie rozwiazania w O(N^3), za pomoca drzewa przedzialowego punkt - przedzial.
    // dp[i][j], ile jest pudelek antytrojkatowych, gdzie najwiekszy bok ma dlugosc i, a drugi najwiekszy bok dlugosc j.
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    int stat[m+1] = {0};
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        stat[wczytana_liczba]++;
    }

    for (int i = 1; i <= m; ++i)
    {
        if (stat[i] != 0)
        {
            wyn++;
            for (int j = 0; j < min(stat[i],2); ++j)
                liczby.push_back(i);
        }
    }

    for (int i = 0; i <= m; ++i)
        for (int j = 0; j <= m; ++j)
            dp[i][j] = 0;

    for (int i = 0; i <= m; ++i)
        for (int j = 0; j < rozmiar_drzewa; ++j)
            drzewo_przedzialowe[i][j] = 0;

    dp[liczby[1]][liczby[0]] = 1;
    update(liczby[1],liczby[0],1);

    for (int i = 2; i < liczby.size(); ++i)
    {
        for (int j = i - 1; j >= 0; --j)
        {
            int L_I = liczby[i], L_J = liczby[j];
            if (dp[L_I][L_J] == 0)
            {
                ll val = 1 + querry(L_J,0,L_I - L_J);
                update(L_I, L_J, val);
                dp[L_I][L_J] = val;
            }
        }
    }

    for (int i = 1; i <= m; ++i)
        for (int j = i; j >= 1; --j)
            wyn += dp[i][j];

    cout << wyn << '\n';

    return 0;
}