Jak rozwiązałeś to zadanie na 10 punktów?

Ogólny szkielet rozwiązania jest identyczny, jak w zadaniu [ELE] (rozwiązanie opisałem w innym wątku).

Odcinamy kolejne liście. Każdy węzeł zawiera listę projektów agregujących dane z całego odcinanego poddrzewa.

W każdym projekcie istotne dla nas są trzy atrybuty: liczbą zamkniętych części, suma kwadratów wartości w zamkniętych częściach, suma wartości w niezamkniętej części. Różnica jest taka, że każdy wierzchołek musi agregować projekty być może z wielu różnych odcinanych fragmentów - dlatego przy odcinaniu kolejnego węzła robimy iloczyn kartezjański projektów: z odcinanego wierzchołka oraz jego sąsiada (posiadającego być może zagregowane projekty z innych odciętych części) - to powoduje wykładniczy wzrost wielkości list projektów.
Oczywiście każdą taką parę projektów możemy połączyć na dwa sposoby: zamykając otwarty fragment lub łącząc go z kolejnym wierzchołkiem.

Ponieważ listy projektów gwałtownie rosną, po każdym kroku oczyszczamy listy z projektów gorszych od innych projektów na liście. Okazuje się, że takich projektów do usunięcia jest bardzo dużo, co jest efektem losowych danych. Z tego też względu całość działa całkiem szybko. Złożoność to O(n * n * X), bo dla każdego z 'n' węzłów przechowujemy co najmniej 'n' projektów (dla różnej liczby obszarów), natomiast X we wzorze oznacza, że dla każdej liczby obszarów możemy mieć wiele nieporównywalnych projektów, jednak właśnie to X dla losowych testów jest względnie małe.

Czy ktos udowodnil lub uzasadnil (uczestnicy lub organizatorzy) dlaczego takie rozwiazanie dziala szybko?