Zadanie Gdzie Zbudować Browar? OI

Question

Mam problem z takim zadaniem z OI: https://szkopul.edu.pl/problemset/problem/Z1C91LB8rGYMxy6wRLBmbXba/site/?key=statement

Napisałem bruta w O(N^2), zakładam, że browar jest budowany w każdym możliwym mieście(jest kandydatem), i symuluję najkrótszą drogę O(N), dla każdego kandydata, albo z lewej albo z prawej. Przechodzi na 40pkt, ale nie wiem jak podejść do tego lepiej. Ma ktoś jakiś pomysł?

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

Comments

W Przygodach Bajtazara jest omówienie tego zadania. Jest tam też ciekawa obserwacja, że "Jeśli miasta są połączone siecią dróg będącą drzewem, to lokalizacja browaru nie zależy od odległości między miastami a tylko od zapotrzebowania miast"

Ale to tylko taka ciekawostka, która nie jest potrzebna do rozwiązania zadania.

Hint: koszt zamortyzowany + coś w stylu gąsienicy

---

Dzięki!

Dokładnie coś w stylu gąsienicy wchodzi!

---

Krótki opis, a bardziej szkic rozwiązania.

Żeby rozwiązać całe zadanie, skupmy się na obserwacji. Policzmy koszt jaki trzeba, zapłacić, gdy zbudujemy browar w dowolnym mieście. Ja założę, że będzie to miasto o numerze 1. I teraz zaużmy, że pomarańczowe to do których opłaca mi się(jest mniejszy koszt na ścieżce) idąc w prawo, a niebieskie to samo, tylko idąc w lewo. Patrz na rysunek:

To zauważ, że jest tu jedna ciekawa zależność. Jeśli z miasta pierwszego opłaca nam się idąc w prawo dojść do miasta 4, to opłaca nam się też dojść do miasta 3,2. Ten fakt jest logiczny i intuicyjny. Bo jak chcielibyśmy iść lewym do tego miasta, to będzie większy koszt niż dojście do 4 idąc w lewo, a to jest jeszcze dalej, więc koszt idzie jeszcze bardziej w górę.

To spostrzerzenie prowadzi nas już praktycznie do końca. Liczymy wynik, numer ostatniego miasta, do którego opłaca nam się dojść idąc w prawo, sumę zapotrzebowania w gąsienicy, sumę odległości w gąsienicy, sumę odległości i zapotrzebowania poza gąsienicą. Te zmienne długości, to każdy sobie powinen zapisać jak chce, bo np. odległości i zapotrzebowania poza gąsienicą nie trzeba raczej liczyć, bo jak znamy sumę odległości i zapotrzebowania w całym mieście, sumę odległości i zapotrzebowania w gąsienicy, to można sobie wyliczyć jednym odejmowaniem. Przy założeniu, żę stawiamy browar w mieście np. pierwszym. I symulujemy potem stawianie w miastach 2,3,4,5,6....N i jak możemy to przesuwamy gąsienicę do kolejnych miast. -> O(N), bo takich skoków gąsienicą wykonamy maksymalnie około 2N, koszt zamortyzowany. Myśląc w gąsienicy mam na myśli, coś co jest w gąsienicy, czyli np dla rysunku na górze drogę pomiędzy 1,2,3,4.(ostanie do których nam się opłaca dojśc idąc w prawo, dla danego sprawdzanego początku gąsienicy)

Można analogicznie chodzić sobie w lewo zamiast w prawo, wydaje się być to obojętne.

W przygodach jest dokładny opis, i podlinkowanie zadań patrz także. W książeczce OI, na stronie oi-a pewnie też jest rozwiązanie.

Mnie zastanawiała jeszcze jedna rzecz. Czy można zamiast tego kosztu zamortyzowanego z "gąsienicą" podejść do tego innaczej, i z każdego wierzchołka odpowiadać niezależnie, nie znając wyników i sum długości i zapotrzebowania dla poprzednich wyników. Faktem jest, że najprawdopodobniej możemy binarnie znaleźć ostatni do którego opłaca nam się iść w prawo, i ostatni do którego opłaca nam się iść w lewo, ale nie wiem jak policzyć te koszty, na tej ścieżce, więc ja nie umiem, ale całkiem możliwe, że da się to jakoś zrobić. Jeśli ktoś wymyślił, by takie rozwiązanie w O(N lg N), to powinno wejść na 100pkt, ale nie jestem pewien.

Answer 1

Wydaje mi się, że browar może powstać między miastami.
Podejrzewam, że zadanie można zrealizować poszukiwaniem binarnym po autostradzie.

Comments

Tylko właśnie cały problem wydaje mi się, że polega na tym, że do danego miasta możesz dojechać albo z lewej, albo z prawej. Jakby dało się tylko jedna strona, to ja się zgadam, że wyszukiwanie binarne wchodzi.