Zadanie Kolekcjoner Monet, programowanie dynamiczne

Question

Mam problem z takim zdaniem:

Pewnie wejdzie tu jakieś dp, a dokładniej plecak. Napisałem kod w O(N^2 * K), zakładając, że nie używam danego przedmiotu i robię prosty plecak z pozostałymi w celu sprawdzenia, czy mogę ułożyć K pozostałymi. Dostaję 50pkt. Bardzo prosiłbym o hinta jak to przyśpieszyć.

Kod:

#include <iostream>
#include <vector>

using namespace std;

int n = 0, k = 0, wczytana_liczba = 0, cnt = 0;
vector<bool> visited;
vector<bool> dp;
vector<int> A;
vector<int> sprawdzane;
vector<int> do_dodania;

inline bool czy_pasuje(int x)
{
    dp.assign(k+1,false);
    dp[0] = true;
    sprawdzane = vector<int>();
    sprawdzane.push_back(0);
    for (int i = 0; i < n; ++i)
    {
        if (i == x)
            continue;
        do_dodania = vector<int>();
        for (int j = sprawdzane.size()-1; j >= 0; --j)
        {
            int val = sprawdzane[j];
            if (val + A[i] <= k and dp[val] == true and dp[val+A[i]] == false)
            {
                do_dodania.push_back(val+A[i]);
                dp[val+A[i]] = true;
            }
            if (dp[k] == true)
                return true;
        }
        for (int j = do_dodania.size()-1; j >= 0; --j)
            sprawdzane.push_back(do_dodania[j]);
    }
    return false;
}

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

    cin >> n >> k;

    visited.assign(k+1,false);
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        visited[wczytana_liczba] = true;
    }

    for (int i = 1; i <= k; ++i)
        if (visited[i] == true)
            A.push_back(i);

    for (int i = 0; i < n; ++i)
    {
        if (czy_pasuje(i) == false)
        {
            cout << A[i] << ' ';
            ++cnt;
        }
    }

    if (cnt == 0)
        cout << "OK";
    cout << '\n';

    return 0;
}

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

Comments

Jedyne spostrzerzenie jakie poczyniłem w kierunku czegoś szybszego to to, że jak chcemy ułożyć sumę K, to użyjemy co najwyżej sqrt(K) przedmiotów.

---

Mam kod na 96pkt, to samo tylko, że na bitsecie robię, i mam O(N^2 * K / 32), nie wiem jak to przyśpieszyć. Kod:

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

using namespace std;

int n = 0, k = 0, wczytana_liczba = 0, cnt = 0;
vector<int> A;
vector<int> ile;

const int SIZE = 10'000;
bitset<SIZE+5> B;

inline bool czy_pasuje(int x)
{
    B = bitset<SIZE+5>();
    B.set(0);
    for (int i = 0; i < n; ++i)
    {
        if (i == x)
            continue;
        B = (B | (B << A[i]));
        if (B[k] == 1)
            return true;
    }
    return false;
}

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

    cin >> n >> k;

    ile.assign(k+1,0);
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        ++ile[wczytana_liczba];
    }

    for (int i = 1; i <= k; ++i)
        for (int j = 0; j < ile[i]; ++j)
            A.push_back(i);

    for (int i = 0; i < n; ++i)
    {
        if (czy_pasuje(i) == false)
        {
            printf("%d ",A[i]);
            ++cnt;
        }
    }

    if (cnt == 0)
        printf("OK\n");

    return 0;
}

 

Answer 1

Jest pewien trick, który pozwala liczyć szybko dp pomijając jeden element. Korzysta z dziel i zwyciężaj. Działa mniej więcej tak:

Bierzesz wszystkie monety, dzielisz je na pół. Na jednej połowie liczysz dp (czyli to co robisz tutaj B = (B | (B << A[i]))) a drugą znowu dzielisz na pół i powtarzasz rekurencyjnie. W końcu nie będzie można dzielić na pół bo zostanie tylko jeden element. Czyli dostaniesz dp pomijające ten jeden element.

Jeśli dobrze licze to będzie działać O(nlogn*k)

Comments

Mamy drzewo binarne, takie jak w przedziałowcu. 2N-1 wierzchołków, w każdym trzymamy bitseta który mówi nam, jakie da się zrobić z liczb w przedziale, jak kontroluje. Przy takim założeniu, jak chcemy poprostu B[k] sprawdzić?

---

Nie ma drzewa. To ma działać podobnie jak merge sort. Wywołujesz jedną funkcję rekurenycjną, która wszystko policzy. Jak nie będziesz mógł dzielisz przedziału na pół, bo został jeden element to sprawdzasz B[k]

---

Tak masz rację. To działa w O(N lg N * K / 32) o ile się nie mylę

---

Jak skorzystasz z bitestów a nie tradycyjnego dp to pewnie tak

---

No i weszla 100pkt, super rozwiazanie. Chyba autorowi zadania chodzilo o dopilowanie bitseta, bo ten solv robi sie zazwyczaj 0.01 / 0.50s xD. Kod jest bardzo prosty, dokladnie to co mówisz. 

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

using namespace std;

int n = 0, k = 0, cnt = 0;
const int SIZE = 10000 + 5;
vector<int> A;
vector<bool> wyn;

inline void dziel_i_rzadz(int l, int p, bitset<SIZE> B)
{
    if (l == p)
    {
        if (B[k] == 1)
            wyn[l] = false;
        return;
    }
    int srodek = (l+p) / 2;
    bitset<SIZE> B_lewy = B, B_prawy = B;
    for (int i = l; i <= srodek; ++i)
        B_lewy = (B_lewy | (B_lewy << A[i]));
    for (int i = srodek+1; i <= p; ++i)
        B_prawy = (B_prawy | (B_prawy << A[i]));
    dziel_i_rzadz(l,srodek,B_prawy);
    dziel_i_rzadz(srodek+1,p,B_lewy);
}

int main()
{
    // O(N lg N * K / 32), dziel i rzadz z plecakiem.
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    cin >> n >> k;

    A.assign(n,-1);
    for (int i = 0; i < n; ++i)
        cin >> A[i];
    sort(A.begin(),A.end());

    wyn.assign(n,true);
    bitset<SIZE> B(0);
    B.set(0);
    dziel_i_rzadz(0,n-1,B);

    for (int i = 0; i < n; ++i)
    {
        if (wyn[i] == true)
        {
            cout << A[i] << ' ';
            ++cnt;
        }
    }

    if (cnt == 0)
        cout << "OK" << '\n';
    else
        cout << '\n';

    return 0;
}

Dzięki!