Удивительно простая задачка, которую сдали 51 чел. из 4591

[Equinoxe]

Оригинальная версия условия от google codejam (мне довольно редко нравятся растянутые условия, но любовь к условиям с котятами победила): http://code.google.com/codejam/contest/das...?c=1150485#s=p2
Переводя на человеческий язык:
Есть правильный $n$-угольник, в котором провели диагонали, но так, что они могут пересекаться лишь в вершинах (т.е. дано $n$ и диагонали). Таким образом, начальный $n$-угольник был разбит на области. Необходимо раскрасить вершины исходного $n$-угольника в $k$ цветов так, чтобы $k$ было максимально, а вершины каждой области содержали в себе все $k$ цветов. Сама задача в том, чтобы предложить непереборный алгоритм выполнения задачи. Как-то так

(Оффтоп)

Собственно, убила простота задачки, совмещенная с удивительно малым кол-вом сдавших её (51 человек из 4591!) При том, что участвуют преимущественно студенты, да ещё и из разных стран!
Меня мягко говоря очень смутил этот факт, поэтому я решила, что не буду сразу постить решение, быть может эта задачка и правда только мне кажется настолько очевидной?

[Munin]

На олимпиадах важно не только то, насколько задача сложна сама по себе, но и насколько она кажется сложной: в условиях дефицита времени за неё могут просто не браться.

[Equinoxe]

Munin, возможно, но насколько я помню, в первом раунде последней задачкой всегда была какая-то идейная

[TOTAL]

Equinoxe в сообщении #448618 писал(а):

Сама задача в том, чтобы предложить непереборный алгоритм выполнения задачи. Как-то так

Предлагаю алгоритм: считаем, что все подобласти имеют одинаковое число вершин. Дальше очевидно.

[Equinoxe]

TOTAL, всё же не очень очевидно
Положим, n=8, а диагонали (1, 3), (3, 5), (5, 7) и (7, 1). Как Вы уравняете кол-во вершин в подобластях и что в итоге получите? (в этом примере кол-во цветов получается 3)

[TOTAL]

Equinoxe в сообщении #449118 писал(а):

TOTAL, всё же не очень очевидно
Положим, n=8, а диагонали (1, 3), (3, 5), (5, 7) и (7, 1). Как Вы уравняете кол-во вершин в подобластях и что в итоге получите? (в этом примере кол-во цветов получается 3)

Я ошибся, согласен.

[Equinoxe]

TOTAL, я уже говорила так про некоторые, так вот повторюсь:
Эта задачка из разряда большинства олимпиадных — решается всего лишь одной простой идеей «а что, если эта задачка — тупая?»

[Батороев]

Equinoxe в сообщении #449118 писал(а):

Положим, n=8, а диагонали (1, 3), (3, 5), (5, 7) и (7, 1). Как Вы уравняете кол-во вершин в подобластях и что в итоге получите? (в этом примере кол-во цветов получается 3)

А почему диагоналей (3, 7) или (1, 5) нет? Условие предполагает произвольное количество диагоналей?

[Equinoxe]

Батороев, да, произвольное

[TOTAL]

Находим число областей разного типа (отличаются количеством стен), одновременно создавая структуру данных для незатратного выполнения окрашивания. Количество цветов, очевидно, найдено.

Красим концы какой-нибудь внешней стены в разные цвета и заносим в буфер номер этой стены.

1 continue
Если буфер не пуст (иначе конец), считываем из него номер уже окрашенной стены, затем окрашиваем оставшиеся углы лежащей за этой стеной комнаты в неповторяющиеся на одной стене цвета, используя все. Если в процессе этого окрашивания встречаем внутреннюю стену, то переименовываем её во внешнюю и её номер добавляем в буфер.
goto 1

[Equinoxe]

TOTAL, да, именно так :)
Я описала это же (по сути) решение так:
0. Находим минимальную по кол-ву вершин область, k = кол-во вершин в ней
1. Если диагоналей нет, то красим многоугольник в 1 2 3 4 … k 2 3 2 3 … 2 3, если же есть, то делим ею многоугольник на два, решаем в обоих эту же задачку, а затем свапуем цвета во втором так, чтобы они на этой диагонали совпадали с первым (очевидно, проблем не будет, т.к. у нас любое ребро будет покрашено в два различных цвета, для того и были 2 3 2 3 (k не может быть меньше 3х)).