Kawiarnia

Tym razem będzie o zadaniu z kategorii ad-hoc, czyli takim, w którym w zasadzie nie trzeba niczego wiedzieć, a i tak jest ciekawie. W szczególności obiecuję, że w rozwiązaniu nie pojawi się nawet odrobina geometrii! Co nawet lepsze, zadanie brzmi (prawie) praktyczne: dysponujemy sporym zapasem stołów, przy których może siedzieć do r osób. Oprócz tego dysponujemy danymi o n grupach gości, a dokładniej wiemy, że i-ta z nich liczy a_i osób. Chcielibyśmy rozsadzić wszystkich gości używając jak najmniejszej liczby stołów, przy czym musimy uniknąć sytuacji, w której przy którymś stole siedzi tylko jedna osoba z jakiejś grupy.

Oryginalną treść (zadania A) można zobaczyć tutaj. Ważne dla nas są w zasadzie tylko dwa szczegóły: 3\leq r oraz n,r,a_i \leq 2000. To drugie sugeruje, że nasze rozwiązanie musi być dość szybkie. To pierwsze pewnie też coś sugeruje, ale co dokładnie przekonamy się dopiero za chwilę.

Pierwszy krok jest dość standardowy. Mimo, że celem jest minimalizacja liczby stołów, zajmiemy się efektywnym sprawdzeniem, czy X stołów wystarczy do rozsadzenia wszystkich gości. A co potem? A potem przejrzymy sobie kolejne X=1,2,3,\ldots i prędzej lub później trafimy na najmniejsze wystarczająco duże X. No, to może chwilę zająć, bo w najgorszym możliwym przypadku X=10^6, więc tak naprawdę pewnie sprytnie skorzystamy z wyszukiwania binarnego.

Dla nabrania intuicji warto zacząć od kilku przypadków szczególnych. No, nie jest do końca jasne, że będzie to przydatne, ale zaszkodzić pewnie nie zaszkodzi. Powiedzmy, na przykład, że wszystkie grupy są dwuosobowe. Wtedy nie mamy wielkiego wyboru: każdy stół pozwala na pozbycie się \lfloor\frac{r}{2}\rfloor grup, czyli musimy tylko sprawdzić, czy X\geq n \lfloor\frac{r}{2}\rfloor. No to żeby było trochę trudniej, powiedzmy, że wszystkie grupy są trzyosobowe. Wtedy też nie ma wielkiego wyboru: takiej grupy nie da się podzielić na dwie części tak, aby w każdej z nich była więcej niż jedna osoba, czyli każdy stół pozwala na pozbycie się \lfloor\frac{r}{2}\rfloor grup, i wystarczy sprawdzić, czy X\geq n \lfloor\frac{r}{2}\rfloor.

Na razie było łatwo. Spróbujmy więc rozważyć sytuację, w której wszystkie grupy są (a co!) czteroosobowe. Nie jest to jednak nic nowego: możemy podzielić każdą grupę na dwie grupy dwuosobowe, i zredukować sytuację do rozważanego wcześniej przypadku. Czemu? Albo wszystkie cztery osoby siedzą przy tym samym stole, albo dwie z nich siedzą przy jednym stole, a pozostałe dwie przy drugim. W obydwu przypadkach możemy myśleć, że tak naprawdę musimy niezależnie rozsadzić dwie pary. Podobna sztuczka działa także wtedy, gdy wszystkie grupy są pięcioosobowe, przy czym wtedy dzielimy każdą z nich na jedną parę i jedną trójkę. OK, skoro działa dla 2,3,4, a nawet (!) 5, to może działa dla dowolnie dużych grup? Trochę tak, a trochę nie. Jeśli na przykład wszystkie grupy są sześcioosobowe, nie jest do końca jasne, czy należy podzielić je na (dwie) trójki, czy może na (trzy) pary. To jedno. Druga kwestia jest taka, że nawet jeśli wszystkie grupy były oryginalnie takie same, po podziale możemy dostać zarówno pary, jak i trójki.

Zajmijmy się najpierw tą drugą kwestią, czyli załóżmy, że wszystkie grupy są dwu- lub trzyosobowe. Czyli mamy D par, T trójek, i chcemy upakować je wszystkie przy X stołach o pojemności r \geq 3. Dość naturalne jest oddzielne rozważenie przypadku, gdy r jest parzyste i nieparzyste, choćby dlatego, że mając same pary tak naprawdę interesuje nas tylko wartość \lfloor\frac{r}{2}\rfloor.

  1. Załóżmy, że r jest nieparzyste. Jeśli T\leq X, z rX dostępnych miejsc na pewno nie jesteśmy w stanie wykorzystać więcej niż rX-(X-T), gdyż w najlepszym możliwym wypadku każda trójka siedzi przy innym stole, czyli X-T stołów ma nieparzyście wiele pozostałych wolnych miejsc, które możemy obsadzić tylko parami. Łatwo się przekonać, że nie ma potrzeby tracić więcej. Sytuacja wygląda trochę inaczej, gdy T>X. Można jednak zauważyć, że bez straty ogólności w takim przypadku przy każdym stoliku siedzi (przynajmniej) jedna trójka. Rzeczywiście, załóżmy przeciwnie, czyli przy jakimś stoliku siedzą tylko pary (lub mamy jakiś stolik, który jest całkiem pusty, ale wtedy jest całkiem łatwo), czyli jest tam jakieś wolne miejsce. Wtedy przy innym stoliku siedzą dwie trójki, i możemy zamienić któraś z nich z jedną z tych par. Fajnie! Można więc zmniejszyć r o 3, a T o X, a następnie rozwiązać powstały mniejszy problem (co nawet lepsze, nie tylko mniejszy, ale już z parzystym r).

  2. A teraz załóżmy, że r jest parzyste. Wygodnie jest myśleć raczej o tym, ile miejsc na pewno pozostanie niewykorzystanych. Jeśli przy którymś stoliku siedzi nieparzyście wiele trójek (w szczególności, tylko jedna), tracimy jedno miejsce. Najlepiej więc podzielić trójki tak, aby przy każdym stoliku siedziała ich parzysta liczba, co na pewno jeśli możliwe jeśli r\geq 6 i T jest parzyste. Jeśli r\geq 6, ale T jest nieparzyste, na pewno stracimy jedno miejsce, nie ma też potrzeby tracić więcej. Daje nam to prosty arytmetyczny warunek dla r\geq 6. A co jeśli r=2,4? Wtedy w sumie nie bardzo jest nad czym myśleć: dla r=2 sprawdzamy czy T=0 i D\leq X, a dla r=4 czy D\leq 2(X-T).

Czyli udało nam się skonstruować funkcję, która w czasie stałym sprawdza, czy da się upakować D par i T trójek przy X stołach. Jeśli a_i\leq 5 dla wszystkich i, daje nam to odpowiedź na oryginalne pytanie, no ale przecież wcale nie musi tak być!

Okazuje się, że jeśli r jest parzyste, możemy zastąpić każde a_i przez co najwyżej jedną trójkę i pewną liczbę par. Dokładniej, możemy zastąpić parzyste a_i przez \frac{a_i}{2} par, a nieparzyste a_i przez jedną trójkę i \frac{a_i-3}{2} par. Wynika to z następującego lematu.

Lemat. Jeśli r jest parzyste, bez straty ogólności można założyć, że każda grupa jest rozsadzona w taki sposób, że przy co najwyżej jednym stole siedzi nieparzyście wielu z jej członków.

Dowód. Pokażemy, że jeśli r jest parzyste, zawsze można zmodyfikować rozwiązanie tak, aby wymusić powyższy warunek. No to weźmy jakieś rozwiązanie. Podzielmy osoby należące do tej samej grupy i siedzące przy tym samym stole na pary i trójki (tworząc co najwyżej jedną trójkę). Teraz popatrzmy na grupę a_i, która została rozsadzona tak, że przy więcej niż jednym stole siedzi nieparzyście wielu z jej członków (nazwijmy takie grupy interesującymi). Oznacza to, że w wybranym podziale ma ona przynajmniej dwie trójki siedzące przy różnych stołach. Jeśli któryś z tych dwóch stołów nie jest pełen, możemy przesadzić osobę z jednej trójki tworząc czwórkę i parę. Jeśli zaś któryś z tych dwóch stołów jest pełen, siedzi tam jeszcze przynajmniej jedna trójka pochodząca z grupy a_j dla jakiegoś j\neq i. Teraz możemy wymienić tę trójkę z jedną z pozostałych dwóch otrzymując sytuację, w której przy jakimś stole siedzą dwie trójki z tej samej grupy, które następnie zamieniamy na trzy pary. Powtarzając rozumowanie zmniejszamy liczbę trójek, więc prędzej lub później otrzymamy rozwiązanie o żądanej własności.

Załatwia to kwestię parzystych r. A co dla nieparzystych? Powyższy lemat w spektakularny sposób zawodzi już dla r=3, więc pewnie trzeba trochę inaczej.

A może i nie trzeba? Przyjrzyjmy się bliżej sytuacji, w której powyższe rozumowanie nie daje rady, czyli mamy dwie trójki pochodzące z tej samej grupy, które siedzą przy różnych stołach. Problematyczna sytuacja wygląda tak, że obydwa z tych stołów są pełne, co więcej są wypełnione parami. Co więcej, jeśli przy jakimś (być może innym, być może jednym z tych dwóch) stołów siedzą przynajmniej dwie trójki, możemy wykonać podmianę, w wyniku której otrzymamy dwie trójki pochodzące z tej samej grupy i siedzące przy takim stole (które można zamienić na trzy pary). Czyli w kłopotliwej sytuacji przy każdym stole siedzi co najwyżej jedna trójka.

To prawie daje nam sposób na poprawienie lematu używając prostej strategii zachłannej. Każdy stół generuje nam jeden slot, w którym możemy posadzić jakąś trójkę, i \frac{r-3}{2} slotów, które mogą zostać zajęte przez pary. Wiemy, że wszystkie nieparzyste a_i potrzebują przynajmniej jednej trójki, czyli możemy (a nawet musimy) od razu przydzielić im jeden taki slot. Następnie przeglądamy pozostałe (być może zmniejszone) grupy zabierając z aktualnej grupy 6 osób i rozsadzając je jako dwie trójki tak długo, jak jest to możliwe. Następnie zamieniamy sloty dla trójek na sloty dla dwójek, i rozsadzamy wszystkich pozostałych gości parami. Po chwili zastanowienia można dojść do wniosku, że prowadzi to do optymalnego rozsadzenia wszystkich gości, oraz że taką procedurę można zaimplementować w czasie \mathcal{O}(n).

OK, czyli dostaliśmy rozwiązanie całego zadania, które działa w czasie (mniej więcej) \mathcal{O}(n\log(rn)). A może dałoby się szybciej?

Dałoby się! Dla parzystych r tak naprawdę sprawdzamy tylko, czy X jest wystarczająco duże (przekonanie się o tym wymaga pewnie zapisania całego rozwiązania). Dla nieparzystych r jest trochę gorzej: nasze postępowanie wydaje się zależeć od pozostałej liczby slotów, w których można umieścić trójki, a to z kolei zależy od początkowej wartości X. Można jednak poradzić sobie z tym problemem rozważając a_i w kolejności rosnącej, i otrzymać rozwiązanie o złożoności \mathcal{O}(n). Szczegóły takiej modyfikacji pozostawiam jednak Czytelnikowi.

Advertisements

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s