Zadanie samochody, eliminacje do EJOI 2020, po 14 OIJ

Question

Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/_2d84Hdvu-G-juPaRQvUAeZD/site/?key=statement

Nie wiem jak do tego podejśc. Mam kilka pomysłów i spostrzerzeń, ale one są brutami. 1 - Można napisać symulację dla każdego zapytania w O(Q*N*K), można podejść trochę szybciej i dla każdego samochodu zrobić maski bitowe, na zapalonych samochodach i, mieć unordered mapę masek bitowych i min wyn i na zapytania odpowiadać w czasie stałym. To pewnie weszłoby na koło 30pkt(Jak bym w-ifował kiedy robi jakie przypadki).

2 - na 90% obstawiam, że tu wejdą jakieś maski bitowe, tylko nie wiem jak to rozgryźć.

Ma ktoś jakiś pomysł? Z góry dziękuję za poświęcony czas!

Comments

Wymysliłem już O(2^K * N * K), dla każdej możliwej bitaski idę po wszystkich samochodach i sprawdzam czy pasują i na zapytania odpowiadam w czasie stałym. Jak byłbym szybciej niż w O(N * K), dla każdej bitmaski sprawdzić min wyn, to byłbym w domu.

---

Te bitmaski przeszły na 0pkt xD

---

Akurat to O(2^K * N * K) dałoby się zbić do O(2^K * N) jeśli zapiszesz bitmaski jako inty. Wtedy w czasie stałym można sprawdzić czy bity x są podzbiorem y

---

(x & y) == x ?

Mogę tak pisać jak mam inty?

---

Tak. Jakby K było większe to pewnie bezpieczniej by było na unsigned albo long longach

---

@Whistleroosh, 

Znalazłem na kanale OIJ, rozwiązanie, tylko nie dokońca je rozumiem. Oni mówią tak:

1 - Zamień na inty- i nalicz tablicę M[i], min koszt z wejścia dla samochodu o danej masce (ten krok kumam)

2 - Puść dp-ka od największych i, od 2^K, do 0, gdzie dp[i], to min wyn, biorąc pod uwagę, elementy, które mają w sobie tą maskę. I teraz dla każdego dp, oni mówią coś w stylu, że jak bierzemy je od największych, to dp[i] = min(M[i], przeiteruj się po dołożeniu jedynki, gdzie są zera, i weź z nich min dp)

3 - Na zapytania odpowiedź w czasie stałym, odwołując się do tablicy dp. 

Answer 1

Rozwiązanie będzie korzystać z masek bitowych a dokładniej z dp na maskach. Wyposażenie będziemy kodować jako unsigned int.

dp[x] = wynik dla zapytania o samochód z wyposażeniem x lub większym

dp[x] = min(samochody które mają dokładnie wyposażenie x, dp[x | 1<< i] dla i od 0 do K)

Zastanów się co oznacza to drugie wyrażenie w min

Comments

A nie wystarczy przejść się po wszystkich bitach co są zgaszone, i wziąć z dp z zapalonym?

---

Tak, rzeczywiście źle powiedziałem, pomieszało mi się. Ja bym zapisał to od 39 do 46 za pomocą operacji bitowych bo teraz jest to mało czytelne i mogły pojawić się tam nieoczywiste błędy. Tak samo nie wiem czy przypadkiem nie powinieneś zaczynać iterować od 1 << (k+1) - 1

---

Przeszło na 100pkt, błąd był taki, że w przypadku remisów po cenie, trzeba wypisać numer o jak najwcześniejszym idx-ie, więc wystarczyło dodać po else-ifa, czy idx, nie jest mniejszy.

Poprawiona wersja kodu dająca 100pkt:, a i to co pisałem wyżej, że niby znalazłem błąd, to chyba jednak nie jest potrzebne.

#include <iostream>
#include <vector>

using namespace std;

int n = 0, q = 0, k = 0, a = 0, b = 0, wczytana_liczba = 0, sum = 0;
vector<pair<int,int>> dp;
vector<pair<int,int>> M;

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

    cin >> n >> k >> q;

    M.assign((1 << k),{1e9+15,-1});
    dp.assign((1 << k),{1e9+15,-1});

    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
        sum = 0;
        for (int j = 0; j < b; ++j)
        {
            cin >> wczytana_liczba;
            sum += (1 << (k - wczytana_liczba));
        }
        if (a < M[sum].first)
            M[sum] = {a,i};
    }

    for (int i = (1 << k) - 1; i >= 0; --i)
    {
        if (M[i].first != 1e9+15)
            dp[i] = M[i];
        sum = i;
        for (int j = (1 << k) / 2; j > 0; j /= 2)
        {
            if (sum >= j) // Zapalony bit
                sum -= j;
            else // Zgaszony bit
            {
                if (dp[i+j].first < dp[i].first)
                    dp[i] = dp[i+j];
                else if (dp[i+j].first == dp[i].first)
                    dp[i].second = min(dp[i].second, dp[i+j].second);
            }
        }
    }

    while (q--)
    {
        cin >> a;
        sum = 0;
        for (int i = 0; i < a; ++i)
        {
            cin >> wczytana_liczba;
            sum += (1 << (k - wczytana_liczba));
        }
        if (dp[sum].first == 1e9+15)
            cout << "NIE" << '\n';
        else
            cout << dp[sum].second + 1 << '\n';
    }

    return 0;
}

Muszę poćwiczyć mocniej operacje bitowe i bitseta, a wiesz może jak najlepiej pisać bitseta, bo jak kiedyś próbowałem to #include <bitset>, to musiałem sztywno zdeklarować jego size, np 10000, a np nie moglem zrobić o rozmiarze N. Wiesz może, czy da się to jakoś zrobić? Albo innaczej używać bitseta?

Dzięki za pomoc!

---

bitset działa na templatkach, więc rozmiar musisz albo wpisać ręcznie albo dać ze zmiennej const. Bo kompilator musi znać tę liczbę

---

@pasjonat_algorytmiki, 

Jak ktoś związkiu z tym zadaniem chciałby poćwiczyć operacje bitowe, to jest fajne zadanie - Wiedźmak z dnia próbnego XVI OI. Robiłem przed chwilą i bardzo mi się spodobało. I jeszcze podobno jest współczesna komunikacja z finału OIG-a (ale tego nie zrobiłem jeszcze, więc ciężko mi potwierdzić ;) )