2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Удивительно простая задачка, которую сдали 51 чел. из 4591
Сообщение22.05.2011, 07:08 


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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Удивительно простая задачка, которую сдали 51 чел. из 4591
Сообщение22.05.2011, 10:56 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Удивительно простая задачка, которую сдали 51 чел. из 4591
Сообщение22.05.2011, 10:59 


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

 Профиль  
                  
 
 Re: Удивительно простая задачка, которую сдали 51 чел. из 4591
Сообщение23.05.2011, 06:40 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Equinoxe в сообщении #448618 писал(а):
Сама задача в том, чтобы предложить непереборный алгоритм выполнения задачи. Как-то так :-)
Предлагаю алгоритм: считаем, что все подобласти имеют одинаковое число вершин. Дальше очевидно.

 Профиль  
                  
 
 Re: Удивительно простая задачка, которую сдали 51 чел. из 4591
Сообщение23.05.2011, 08:40 


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

 Профиль  
                  
 
 Re: Удивительно простая задачка, которую сдали 51 чел. из 4591
Сообщение23.05.2011, 09:43 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Equinoxe в сообщении #449118 писал(а):
TOTAL, всё же не очень очевидно
Положим, n=8, а диагонали (1, 3), (3, 5), (5, 7) и (7, 1). Как Вы уравняете кол-во вершин в подобластях и что в итоге получите? (в этом примере кол-во цветов получается 3)
Я ошибся, согласен.

 Профиль  
                  
 
 Re: Удивительно простая задачка, которую сдали 51 чел. из 4591
Сообщение23.05.2011, 11:06 


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

 Профиль  
                  
 
 Re: Удивительно простая задачка, которую сдали 51 чел. из 4591
Сообщение23.05.2011, 11:57 


23/01/07
3415
Новосибирск
Equinoxe в сообщении #449118 писал(а):
Положим, n=8, а диагонали (1, 3), (3, 5), (5, 7) и (7, 1). Как Вы уравняете кол-во вершин в подобластях и что в итоге получите? (в этом примере кол-во цветов получается 3)

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

 Профиль  
                  
 
 Re: Удивительно простая задачка, которую сдали 51 чел. из 4591
Сообщение23.05.2011, 12:09 


24/01/11
207
Батороев, да, произвольное

 Профиль  
                  
 
 Re: Удивительно простая задачка, которую сдали 51 чел. из 4591
Сообщение24.05.2011, 08:02 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Удивительно простая задачка, которую сдали 51 чел. из 4591
Сообщение24.05.2011, 08:37 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group