Zadanie Wilcze Doły

Question

Cześć,

W przygotowaniach do OI trafiłem na zadanie Wilcze doły z 3 etapu XXII OI: https://szkopul.edu.pl/problemset/problem/07Q0fFk7fU2TmGr6wpPeDCZj/site/?key=statement

Narazie wymyśliłem pomysł O(n^2 * log n) według ograniczeń powinno być około 30 pkt za to, więc nie najgorzej i pomysł jest taki, że przesuwamy deskę od 1 pozycji do coraz bardziej w prawo potem dla każdej pozycji próbujemy wziaść do dołu 1,2,3.. tyle ile możemy i dla każdego takiego wzięcia robimy binary searcha w prawych i mamy O(n^2 * log n). Jednak mam spory problem z implementacją dostaję złe wyniki w kilku testach (za duże) siedzę nad kodem już dobre 1,5 h. Ma ktoś pomysł gdzie jest błąd?

#include <iostream>
#include <vector>

using namespace std;

long long n = 0, d = 0, wczytana_liczba = 0, wynik = 0, poczatek_zapytanie = 0, koniec_zapytanie = 0;
long long p = 0, ile_mamy_workow;
vector<long long> doly;
vector<long long> sumy_prefiksowe;

long long binary_searchh()
{
    if (poczatek_zapytanie >= n)
    {
        return n-1;
    }

    long long p = poczatek_zapytanie;
    long long k = n;
    long long s = 0;

    while(k - p != 1)
    {
        s = (p + k) / 2;
        long long suma = sumy_prefiksowe[s] - sumy_prefiksowe[p-1];
        if (suma > ile_mamy_workow)
        {
            k = s;
        }
        else
        {
            p = s;
        }
    }

    if (doly[poczatek_zapytanie] > ile_mamy_workow)
    {
        return poczatek_zapytanie-1;
    }
    return p;
}

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

    cin >> n >> p >> d;

    if (d >= n)
    {
        cout << n << "\n";
        return 0;
    }

    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        doly.push_back(wczytana_liczba);
    }

    long long s = 0;

    for (int i = 0; i < n; ++i)
    {
        s += doly[i];
        sumy_prefiksowe.push_back(s);
    }

    for (int i = 0; i <= n - d; ++i)
    {
        ile_mamy_workow = p;

        // Najpierw sprawdzamy z nie braniem zadnego z lewej
        poczatek_zapytanie = i + d;
        //cout << "Wyn: " << binary_searchh() - i + 1 << " Binary Search: " << binary_searchh() << endl;
        wynik = max(wynik,binary_searchh() - i + 1);

        for (int j = i - 1; j >= 0; --j)
        {
            long long wyn = 0;
            if (ile_mamy_workow - doly[j] >= 0)
            {
                ile_mamy_workow -= doly[j];
            }
            else
            {
                break;
            }
            poczatek_zapytanie = i + d;
            wyn = binary_searchh() - j + 1;
            //cout << "Wyn: " << wyn << " Binary Search: " << binary_searchh() << endl;
            wynik = max(wynik,wyn);
        }
        //cout << "I: " << i << " max wynik: " << wynik << endl;
    }

    cout << wynik << "\n";

    return 0;
}

Z góry dziękuję za pomoc!

A i binary search zwraca idx w wektorze wilcze doly.

Answer 1

Wróciłem po długim czasie do tego zadania i tak jak ktoś by się kiedyś męczył:

33pkt wchodzi ten kod z binary searchem co tu pisaliśmy O(n*n*log*n)

44 pkt wchodzi ten pomysł co pisałem tu później, przy dobrej implementacji. O(n*logn*logn)

https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/OI/wilcze_doly_44pkt_O(n*logn*logn)binary_search_z_setem.cpp

66pkt wchodzi ten sam pomysł tylko z kolejka monotonniczną zamiast multiseta w O(n log n)

https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/OI/wilcze_doly_66pkt_O(n%20log%20n)kolejka_monotonniczna_z_binary_searchem.cpp

100pkt wchodzi ten sam pomysł co powyżej tylko zamiast binary searcha po wyniku idziemy gąsienica w O(n)

https://github.com/samek567/ZadaniaAlgorytmiczne/blob/main/OI/wilcze_doly_100pkt_gasienica_z_kolejka_monotonniczna.cpp

Dobre rozwiązanie jest w książeczce OI. Wsumie jak ktoś męczy się z tym zadaniem to polecam zrobić najpierw:

Piloci OI Finał XVII OI

Ptaszek 2 etap XXI OI (z programowaniem dynamicznym)

Paliwo 2 etap IV OI

Kolorowy Łańcuch Finał XX OI

Temperatura OI 2 etap XVIII OI

Też na kolejkę monotonniczną lub set, są łatwiejsze i np. ja nie umiałem zrobić tego, a po zrobieniu tych zadań już jakoś poszło.

Ps. Polecam przy sumach prefiksowych idx-owac od 1 zeby nie musiec if-owac przypadku, gdy poczatek = 0.
Powodzenia w męczeniu się z tym zadaniem!

Answer 2

if (doly[poczatek_zapytanie] > ile_mamy_workow)
 {
        return poczatek_zapytanie-1;
 }

nie ma być doly[p]?

Comments

long long ile_mamy_workow_2 = ile_mamy_workow - doly[p];
 
    while(k - p != 1)
    {
        s = (p + k) / 2;
        long long suma = sumy_prefiksowe[s] - sumy_prefiksowe[p];
        if (suma > ile_mamy_workow_2)
        {
            k = s;
        }
        else
        {
            p = s;
            ile_mamy_workow_2 -= suma;
        }
        if (ile_mamy_workow_2 < 0)
        {
            break;
        }
    }

teraz powinno przejść na 33. Worki na krańcach były za dużo razy odejmowane

---

Przeszło, ale dlaczego to działa? Bo przyznam, że nie rozumiem.

---

Zakładamy że wszystkie doły od poczatek_zapytanie do p są zakopane. I wtedy jak robisz p = s to musimy odjąc sume głebokości od p+1 do s. W poprzedniej wersji liczylismy niektóre s/p podwójnie

---

A no faktycznie. Pierwszy raz spotkałem się z binary serachem gdzie trzeba modyfikować podczas iterowania. Dzięki za pomoc. Teraz muszę zastanowić się nad szybszą wersją.

Korzystając z okazji, preferujesz jakąś konwencję pisania binary searcha, pytam bo ja zawsze tak na oko pisałem i na kartce sobie rozpisywałem przypadki, ale pewnie jest jakiś stały sposób?

---

Ja też nigdy nie jestem pewny, czy dobrze rozważam wszystkie przypadki, dlatego przeważnie daje tę wersje z left <= right, lf = mid+1, rt=mid-1, bo jest najbezpieczniejsza. Inna dobra wersja to ta z left < right, lf = mid+1, rt = mid, ale rzadko z niej korzystałem bo nigdy nie pamiętałem czy to jest lf = mid +1 czy rt = mid -1 :)

Answer 3

Zrobiłem coś takiego:

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

using namespace std;

long long n = 0, p = 0, d = 0, wczytana_liczba = 0, jak_dlugi_przedizal = 0;
vector<long long> doly;
vector<long long> sumy_prefiksowe;

bool czy_da_sie_ulozyc()
{
    // Bedziemy pelzac przez tablice i wiemy ze zawsze najlepszy jest dla nas max.

    if (d >= jak_dlugi_przedizal)
    {
        return true;
    }

    long long poczatek = 1;
    long long koniec = d;
    long long suma_przedzialu = sumy_prefiksowe[jak_dlugi_przedizal];
    multiset<long long,greater<long long>> S;

    while (koniec <= jak_dlugi_przedizal)
    {
        S.insert(sumy_prefiksowe[koniec] - sumy_prefiksowe[koniec - d]);
        koniec++;
    }

    auto it = S.begin();
    if (p >= suma_przedzialu - *it)
    {
        return true;
    }

    poczatek++;
    while(koniec <= n)
    {
        S.insert(sumy_prefiksowe[koniec] - sumy_prefiksowe[koniec - d]);
        S.erase(S.lower_bound(sumy_prefiksowe[poczatek + d - 1] - sumy_prefiksowe[poczatek - 1]));
        suma_przedzialu = sumy_prefiksowe[koniec] - sumy_prefiksowe[poczatek - 1];

        auto it = S.begin();
        if (p >= suma_przedzialu - *it)
        {
            return true;
        }

        poczatek++;
        koniec++;
    }

    return false;
}

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

    cin >> n >> p >> d;

    if (d == 0)
    {
        cout << "NIE";
        return 0;
    }

    if (d >= n)
    {
        cout << n << "\n";
        return 0;
    }

    doly.push_back(0);
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        doly.push_back(wczytana_liczba);
    }

    long long s = 0;
    sumy_prefiksowe.push_back(0);

    for (int i = 1; i <= n; ++i)
    {
        s += doly[i];
        sumy_prefiksowe.push_back(s);
    }

    /*
    poczatek = -1;
    koniec = n;
    srodek = 0;

    while(koniec - poczatek != 1)
    {
        srodek = (poczatek + koniec) / 2;
        //cout << "Srodek: " << srodek << endl;
        if (czy_da_sie_ulozyc() == true)
        {
            poczatek = srodek;
            //cout << "Da sie ulozyc! " << endl;
        }
        else
        {
            koniec = srodek;
            //cout << "Nie da sie ulozyc! " << endl;
        }
    }
     */

    for (int i = n; i >= 1; --i)
    {
        jak_dlugi_przedizal = i;
        if (czy_da_sie_ulozyc() == true)
        {
            cout << i << "\n";
            return 0;
        }
    }

    cout << "0";

    return 0;
}

Wynik szukamy binarnie i pełzamy z przedziałem przez n i korzystam z tego, że dla przedziału zawsze najlepiej jest brać jak największą sumę i za nią dawać tamę. O(n log n log n). Wiem ze moge to zoptymalizowac robiac kolejke monotonniczna zamiast multiseta w O(n log n), ale najpierw chcę zeby to przeszło. Nie przechodzą mi 4 testy o kilka za dużo wynik daje. Ten kod to najładniejsza wersja jaką udało mi się napisać.

Binary serach zarymowany, bo niedziała funkcja szukająca.

Comments

Nie wiem czy nie ma problemów z indeksami. Np. tutaj:

sumy_prefiksowe[koniec] - sumy_prefiksowe[koniec - d]

Moze powinno być:

sumy_prefiksowe[koniec - 1] - sumy_prefiksowe[koniec - d - 1]

Ale moge się mylić. 

---

Masz już działający kod także innym rozwiązaniem jest napisanie testerki do tego programu, wtedy bez problemu znajdziesz małe testy dla których będzie błedny wynik.

---

A jak pisać testerkę?

Pytam bo np na OI w 1 etapie ludzie wrzucają swoje testy, a ja napisałem tylko narazie program który odpala mój kod na tych przykładach i sprawdza czy są takie same. A właśnie się zastanawiałem jak generować

---

Normalnie piszesz program w c++ który tworzy losowe dane. I potem żeby zapisać te dane do pliku to najłatwiej zrobić przekierowanie strumienia w linuksie.