Олимпиада ШАДа.

Вторая задача олимпиады. Полное условие с тестами оставлю в комментариях.

На плоскости расположены N различных окружностей, любые две либо не пересекаются, либо вложены.
Требуется найти количество подмножеств окружностей мощности K, таких, то их можно упорядочить в цепочку вложенных друг в друга окружностей.

Решение:
Давайте отсортируем окружности по возрастанию радиуса. То есть после сортировки получим r[i] <= r[j] для всех i < j.
В условии сказано, что окружности не пересекаются.

Давайте построим граф на этих окружностях.
Пусть окружности - это вершинки графа. Проведем ориентированное ребро от вершины i в вершину j если окружность j находится внутри i.

Ну такой граф неудобный, так как может содержаться циклы и излишний ребра, давайте лучше построим дерево.
И так построение дерева:
Как мы помним наши окружности отсортированы по возрастанию радиуса. Пусть мы в вершине i, тогда мы проводим ребро к вершине j, если j < i и окружность j находится внутри i, а также у вершины j нет предка.
Если вы будете проводить ребра именно таким образом, то получите дерево.

- А в чем преимущество дерева ?
- В том что если все поддерева вершины i находится строго внутри окружности i.

Теперь как посчитать ответ ?
Мы фиксируем вершинку дерева, пусть это вершина v. Давайте найдем все такие подмножества окружности содержащий v из которых можно построить вложенную цепочку.
Можно легко заметить, что мы должны просто взять подмножество предков вершины v размера k - 1.
Пусть количество предков вершины v равно, тогда в ответ добавляем C(count_parents, k - 1).

Время работы алгоритма O(N ^ 2)
Код в комментариях.