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

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