Akademickie Mistrzostwa Polski w Programowaniu Zespołowym

18.12.2011

Zadania

Zadania z zawodów można rozwiązywać w serwisie Młodzieżowej Akademii Informatycznej.

Dla tych, którzy chcieliby poczuć choć trochę smaku zawodów przedstawię jedno z zadań tegorocznych zawodów (zadanie J - Jaskinia).

Dane jest drzewo o $ n $ wierzchołkach ($ n \leqslant 3\:000\:000 $). To drzewo możemy dzielić na mniejsze drzewa (przecinając niektóre krawędzie). Celem takiego przecinania krawędzi jest uzyskanie drzew o takiej samej liczbie wierzchołków. Należy wyznaczyć wszystkie możliwe liczności, dla których jest to osiągalne.

Zadanie, mimo iż moim zdaniem nie było zbyt trudne, rozwiązało tylko kilka drużyn. Rozwiązanie sprawdzające wszystkie dzielniki $ n $ oczywiście nie wystarczało w tym zadaniu, ale stosunkowo nietrudno było wyznaczyć rozwiązanie w czasie $ O(n \log n) $. Kluczowa obserwacja jest taka, że wystarczy ukorzenić drzewo w dowolnym wierzchołku i wydajnie analizować liczbę poddrzew rozmiaru podzielnego przez ustalone $ k $.

Gorąco zachęcam do rozwiązywania zadań w serwisie MAIN. Na stronie mistrzostw znajduje się wiele innych ciekawych materiałów, takich jak np. rozwiązania zadań i testy.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com