zadanie na bs z codeforces

Question

Witam,

Próbuję rozwiązać zadanie https://codeforces.com/problemset/problem/1736/C1. Pisze, że to jeden z problemów na binary search. Czy dałby radę mi ktoś powiedzieć jakie jest rozwiązanie z użyciem binary searcha oraz jak polecacie uczyć się tych różnych technik np. binary search to gdzie najlepiej waszym zdaniem rozwiązywać zadania.

Z góry bardzo dziękuję

Answer 1

Klasyczne zadania na gasienice. Ogólnie jest taka zależnośc, że jak da się coś zrobić gąsienicą, to zazwyczaj też bin searchem i odwrotnie. Tu prosta liniówka wchodzi gąsienicą, Binary searchem napewno można zrobić w O(N * lg N * lg N) - binary search z drzewem przedziałowym, pewnie też w O(N lg N) - binary search z sparse table, ale to zdecydowanie przesadzone struktury jak na to zadanie. Prosta gąsienica wchodzi w O(N).

A gdzie rozwiązywać najlepiej zadania, to oczywiście codeforces, atcoder, csesfi jest git, ale ja bardzo lubię szkopuła i archiwum zadań konkursowych(OIJ, OIG, OI), możesz zainwestować grosze w 2 książki(na ebook poincie masz pdf-y za 30-50 zł): "Zaprzyjaźnij się z algorytmami" oraz "Przygody Bajtazara 25 lat Olimpiady Informatycznej", przyczym, ta druga jest już dla trochę bardziej zawansowanych niż pierwsza. Są też ludzie, którzy polecają książki takich dwóch Azjatów - Competetive programing, chyba nawet jest kilka części, ja je mam, ale nie korzystam z nich. Jest też za darmo książka z mistrzostw polski w programowaniu zespołowym, za free pdf-a można sobie pobrać: https://www.mimuw.edu.pl/~idziaszek/algonotes/looking-for-a-challenge-2-pl.pdf   

jest też za free ksiązka z obozu proserwy: https://ilocamp.ilo.pl/images/stories/pros2010/proserwy_inf_2010.pdf

No i ogólnie masz jeszcze kółka OKI zawansowana,poziom2, od podstaw z wieeeloma archiwalnymi zadaniami i filmikami: https://oki.org.pl/

https://www.youtube.com/@OlimpijskieKoloInformatyczne

A co do zadań na binary searcha, to jest chyba moje ulubione zadanie na binary seacha: https://szkopul.edu.pl/problemset/problem/G50OwjoYk8gUak-2HGHGll4o/site/?key=statement

czy też zadanie największy plus z 2 etapu XV OIJ, jest też zadanko "Test na inteligencję" z OI-a, ono jest z OI-a ale jest banalne - zaimplementuj binary search.

Comments

Cześć, dziękuję za twoje rekomendacje. Zacząłem robić zadanie "Test na inteligencję", i już prawie je skończyłem tylko mam problem z binary search'em, który wyszuka najmniejszą wartość większą od x. Niestety mój kod nie działa, wiesz może co poprawić?

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

unordered_map<int,vector<int>> map;

int bs(int current,int index){
    int l = -1,r = map[current].size();
    while(l + 1 < r){
        int mid = l + (r - l) / 2;
        if(map[current][mid] >= index)
            r = mid;
        else
            l = mid;
    }
    return r;
}

int main(){
    int n;
    cin >> n;

    for(int i=0;i<n;++i){
        int x;
        cin >> x;

        map[x].push_back(i);
    }
    // int t;
    // cin >> t;
    // for(int j=0;j<t;++j){
    int k;
    cin >> k;

    bool notok = false;
    int index = 0;
    for(int i=0;i<k;++i){
        int current;
        cin >> current;
        int answer;
        if(map[current].size() == 0)
            notok = true;
        if(map[current].size() == 1)
            answer = map[current][0];
        else
            answer = bs(current,index);

        if(answer == map[current].size())
        {
            notok = true;
            break;
        }
        index = map[current][answer];
    }
    if(notok == false)
        cout << "TAK" << '\n';
    else
         cout << "NIE" << '\n';
    // }
    return 0;
}

 

---

Poprawiłem kod, i powinien działać, natomiast chciałbym dowiedzieć się co sądzisz na temat wyszukiwania najmniejszej wartości większej od x. Jakbyś ty tamto zoptymalizował

---

dziwnie piszesz tego bin searcha, pierwsza wartośc > x, możesz łatwo zaklepać np. tak:

int poczatek = -1, koniec = n, srodek = 0;
while(koniec - poczatek > 1)
{
     srodek = (poczatek + koniec) / 2;
     if (liczby[srodek] > x)
           koniec = srodek;
     else
          poczatek = srodek;
}
if (koniec == n) // nie znalazłem
    return -1;
return koniec;

Ogólnie idea jest taka, że jak szukasz liczb z przedziału [0,n-1], to ustawiasz poczatek jedno wcześniej, koniec jedno dalej i tyle.

---

Po drugie możesz wywalić mapę, ona tylko spowalnia, zrób sobie vector vectorów.

---

Tak btw, jak zrobiłeś to zadanie, to możesz sobie spróbować zrobić je na drugi sposób. Napisz sobie vector setów, i set umożliwia Ci znalezienie pierwszej >= x, podajrze funkcją lower_bound, np tak:

set<int> S;
auto it = S.lower_bound(x);
if (it != S.end())
   cout << *it;

 

---

Gdy sprawdzam czy jakaś liczba znajduje się w mapie/vectorze to czy nie będzie tak że mapa ma stałą złożoność do znajdywania a vector n?Jak coś to mogę się mylić, dlatego chcę się upewnić

---

I ten lower bound ma wbudowany binary search?

---

aaa bo ty to zrobiłeś innaczej, tak jest, ale moja idea była taka, żeby zrobić vector<vector<int>> vect, i w vect[i] trzymać vector na jakich idx-ach jest wartośc x. I po vect[i] będziesz się bin searchować.

---

@Dani, 

Lower bound, to funkcja którą możesz zrobić na strukturze danych zwanej setem, czyli innaczej zbiorem.

---

Okej, mam jeszcze jeden problem. Niestety moje rozwiązanie wchodzi na 80 pkt. Coś musiałem przeoczyć

---

wklej kod aktualnego rozwiązania

---

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

unordered_map<int,vector<int>> map;
int tab[1000*1000+5];

int bs(int current,int index){
    int l = 0,r = map[current].size()-1;
    int ans = -1;
    while(l <= r){
        int mid = l + (r - l + 1) / 2;
        if(map[current][mid] < index)
            l = mid + 1;
        else if(map[current][mid] > index)
        {
            ans = mid;
            r = mid - 1;
        }
        else if(map[current][mid] == index)
            l = mid + 1;
    }
    return ans;
}

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

    //map[1]->indeksy_gdzie_jest
    for(int i=0;i<n;++i){
        int x;
        cin >> x;

        map[x].push_back(i);
    }
    //test_cases
    int t;
    cin >> t;
    for(int j=0;j<t;++j){
        int k;
        cin >> k;

        bool notok = false;
        int index = 0;
        //wrzucam całą listę zapytania do tablicy
        for(int l=0;l<k;++l){
            cin >> tab[l];
        }
        for(int i=0;i<k;++i){
            //biorę aktualną liczbę z zapytania
            int current = tab[i];
            int answer;
            //sprawdzam czy nie ma tam elementu
            if(map.find(current) == map.end())
            {    notok = true;break;}
            //sprawdzam czy element występuje raz
            if(map[current].size() == 1)
               answer = 0;
            else
                answer = bs(current,index);

            //jeśli nie ma 
            if(answer == -1 || map[current][answer] < index)
            {
                notok = true;
                break;
            }
            index = map[current][answer];
        }
        if(notok == false)
            cout << "TAK" << '\n';
        else
            cout << "NIE" << '\n';
        }
    return 0;
}

 

---

zapisz bin searcha tak jak ja Ci napisałem

---

Zedytowałem go i wchodzi na 40 pkt.
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

unordered_map<int,vector<int>> map;//mapa ma mieć liczby np. 1,2,3 i w wektorze zapisuje ich indeksy
int tab[1000*1000+5]; //tablica ma przechowywać zapytania

int bs(int current,int index){
    int l = -1,r = map[current].size(),mid=0;
    while(r - l > 1){
        int mid = (l + r) / 2;
        if(map[current][mid] > index)
            r = mid;
        else{
            l = mid;
        }
    }
    if(r == map[current].size())
        return -1;
    return r;
}

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

    //map[1]->indeksy_gdzie_jest
    for(int i=0;i<n;++i){
        int x;
        cin >> x;

        map[x].push_back(i);
    }
    //test_cases
    int t;
    cin >> t;
    for(int j=0;j<t;++j){
        int k;
        cin >> k;

        bool notok = false;
        int index = 0;
        //wrzucam całą listę zapytania do tablicy
        if(k > n){
            notok = true;
            break;
        }
        for(int l=0;l<k;++l){
            cin >> tab[l];
        }
        for(int i=0;i<k;++i){
            //biorę aktualną liczbę z zapytania
            int current = tab[i];
            int answer;
            //sprawdzam czy nie ma tam elementu
            if(map.find(current) == map.end())
            {    notok = true;break;}
            //sprawdzam czy element występuje raz
            if(map[current].size() == 1)
               answer = 0;
            else
                answer = bs(current,index);

            //jeśli nie ma 
            if(answer == -1 || map[current][answer] < index)
            {
                notok = true;
                break;
            }
            index = map[current][answer];
        }
        if(notok == false)
            cout << "TAK" << '\n';
        else
            cout << "NIE" << '\n';
        }
    return 0;
}

 

---

To nie problem w binary searchu z tego co widać, bo tutaj dalej pierwszy i ostatni test nie przechodzi. Tutaj wczytuje w niektórych testach EOF

---

czekaj czekaj, czemu nazwałeś unordered_mape map? Raczej tak nie rób, może to nie gryzie z map, ale bez sensu prosisz się o kłopoty

---

Masz rację, już to zmieniłem

---

Wziałem twój kod na warsztat i było kilka rzeczy bez sensu:

- nazwałeś unordered_mape map, bez sensu, prosisz sie o klopoty, nazwij ja np. stat czy wystapiena

- zmieniłem bin searcha, na szukającego pierwszej > x, i ty miałeś idx = 0 co jest bzdurą, bo szukasz pierwszej większej niż -1, a nie 0, więc zmieniłem idx = -1

no i przeszło na 100pkt:

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

unordered_map<int,vector<int>> map;
int tab[1000*1000+5];

int bs(int index, int current){
    int poczatek = -1, koniec = map[index].size(), srodek = 0;
    while(koniec - poczatek > 1)
    {
    	srodek = (poczatek + koniec) / 2;
    	if (map[index][srodek] > current)
    		koniec = srodek;
    	else
    		poczatek = srodek;
    }
    if (koniec == map[index].size())
        return -1;
    return koniec;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    //map[1]->indeksy_gdzie_jest
    for(int i=0;i<n;++i){
        int x;
        cin >> x;
        map[x].push_back(i);
    }

    //test_cases
    int t;
    cin >> t;
    for(int j=0;j<t;++j)
    {
        int k;
        cin >> k;

        bool notok = false;
        int index = -1;
        //wrzucam całą listę zapytania do tablicy
        for(int l=0;l<k;++l){
            cin >> tab[l];
        }
        for(int i=0;i<k;++i)
        {
            //biorę aktualną liczbę z zapytania
            int current = tab[i];
            int answer;
            //sprawdzam czy nie ma tam elementu
            if(map.find(current) == map.end())
            {    notok = true;break;}
            //sprawdzam czy element występuje raz

            answer = bs(current,index);

            //jeśli nie ma
            if(answer == -1)
            {
                notok = true;
                break;
            }
            index = map[current][answer];
        }
        if(notok == false)
            cout << "TAK" << '\n';
        else
            cout << "NIE" << '\n';
    }
    return 0;
}

Możesz nauczyć się pisać tego sposobu bin searcha, bo ten twój brzydko wygląda.

---

A i tak btw, możesz wywalić unordered mapę i dać vector vectorów, bo wartości są chyba do max 10^6  czy coś tego typu o ile dobrze pamietam

---

Dzięki wielkie za pomoc. Nauczyłem się sposobu z codeforces edu, ale nie wychodził mi i znalazłem taki na geeksforgeeks. Czy to miałoby jakąś różnicę jakbym wyznaczał srodek
srodek = l + (r - l) / 2 ? Bo z tego co słyszałem to zapobiegam nadużyciu pamięci

Edit: Tak też wchodzi

---

l + (r - l) / 2

nie nie nie nie niesłucha się takich głupot

---

Ten mój sposób jest świetny, są inne fajne, ale ja najbardziej lubię ten, początek jedno wcześniej, koniec jedno dalej, żeby nie było WA i lecisz normalnie

---

l + (r - l) / 2 służy zapobieganiu integer overflowa. Ale to i tak praktycznie nigdy się nie wydaży, bo liczby raczej nie będą większe od 1e18