CERC 2010: Szkice rozwiązań

28.11.2010

F: Fields and Farmers

Treść (pdf) | wyślij rozwiązanie.

Proces wyznaczania końcowej parceli polegający na iteracji kroków opisanych w zadaniu będziemy nazywać znajdowaniem dziwnej otoczki danego początkowego zbioru pól. W problemie wymagane jest zliczenie podzbiorów początkowego zbioru pól, które mają tę samą dziwną otoczkę, co sugeruje, że powinniśmy zacząć od charakteryzacji takiej otoczki.

Na początku zauważmy, że jeśli współrzędne x wszystkich początkowych pól są pomiędzy xmin a xmax, to także wszystkie pola z dziwnej otoczki mają współrzędne z takiego zakresu. Innymi słowy, jeśli nie ma pól początkowych po jakiejś stronie prostej x=a, to nie ma też takich pól w otoczce. Ta sama reguła dotyczy prostych y=a, y=x+a, y=-x+a (ale żadnych innych!) Zauważmy, że jest to dokładna charakteryzacja pól z dziwnej otoczki: po obliczeniu minimalnych i maksymalnych wartości x, y, x-y i x+y dla wszystkich początkowych pól (x,y), dziwna otoczka zawiera wszystkie pola, których dodanie nie zmieniłoby tych minimalnych i maksymalnych wartości. Oznacza to, że brzeg dziwnej otoczki składa się z co najwyżej ośmiu odcinków pokazanych na poniższym rysunku.

strange hull

Wiemy zatem jak wyglądają dziwne otoczki. Wciąż jednak nie ruszyliśmy oryginalnego problemu! Ale teraz wiemy, że wszystkie podzbiory, które mają te same minimalne i maksymalne wartości x, y, x-y i x+y są dla nas interesujące (i powinniśmy je zliczyć). Można to zapisać jako następujący problem: dla danych masek bitowych o rozmiarze 8, zlicz wszystkie podzbiory, których bitowa alternatywa jest równa 11111111. Liczbę wszystkich takich podzbiorów można wyznaczyć dość prosto, korzystając z zasady włączeń i wyłączeń.

Informacje dodatkowe

Zadanie to można rozważać również w wariancie trójwymiarowym, co było przedmiotem długich dyskusji. W końcu grupa układająca zadania doszła do wniosku, że niepotrzebnie komplikuje to zadanie i sprawia dodatkowe problemy w ułożeniu wiarygodnej historyjki do zadania.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com