Musala Soft and PC Magazine Bulgaria

Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria

Състезателна система

Задача 4 от брой 1/2001 - ОЦВЕТЯВАНЕ

Условието на задача 4 можете да изтеглите от тук (RTF Format).

Коментари по условието на задача 4:
Във входния файл НЕ може да има две точки с еднакви координати.

Класиране:

Място	Име	Град	Точки	Време
1	Петър Петров	София	20	0,66
1	Трендафил Трифонов	Велико Търново	20	0,67
3	Мартин Вълканов	София	20	0,78
3	Стоян Йорданов	София	20	0,79
3	Димитър Ковачев	София	20	0,80
3	Тихомир Върбанов	София	20	0,85
3	Владмир Недев	Варна	20	1,49
3	Свилен Колев	София	20	1,70
3	Григор Илиев	Сандански	20	1,86
3	Кирил Тодоров	София	20	1,95
11	Илиян Ненов	Русе	19	-
11	Славяна Генинска	Враца	19	-
13	Владимир Молотков	София	*13	-
14	Даниел Симеонов	Габрово	11	-
15	Даниел Трифонов	Балчик	4	-
15	Димитър Димитров	?	4	-
15	Иван Станишев	Габрово	4	-
15	Николай Чилев	София	4	-
15	Николай Събев	Стара Загора	4	-
15	Петър Събев	Русе	4	-
15	Петко Минков	Пловдив	4	-
15	Валери Цеков	Грамада	4	-
23	Иван Георгиев	Бургас	2	-
24	Деян Ламбов	Пловдив	1	-
24	Камен Добрев	София	1	-
24	Стефан Минков	Габрово	1	-
24	Антон Дончев	Варна	1	-
28	Мартин Русков	София	0	-

Владимир Молотков
(закъсняло решение)

София

* точките на участника Владимир Молотков са намалени с 30% заради неправилнo име на изходния файл.
Пълното класиране по тестове можете да видите тук .

Тестовете:
Тестовете, въз основа на които журито е формирало класирането са достъпни за всички. Можете да ги вземете от тук (ZIP Format).

Коментар по решението и резултатите на участниците:
Както и очакваше журито, получените решения бяха разнообразни и реализираха различни стратегии за оцветяване. Резултатите ясно разделиха решенията в две групи: 19-20 точки - коректен и ефективен алгоритъм; 1-4 точки - backtracking (за по-големите тестове не завършва за определения времеви лимит) или лакома, но некоректна стратегия (за по-големите тестове намира неправилно оцветяване). Радостен е фактът, че 10 участници имат максимален брой точки. Техните решения обаче, въпреки че са коректни и минават всички тестове на журито за определения вртемеви лимит, се различават по ефективността на използваните алгоритми, т.е. по скоростта за изпълнение. С най-добри времена измежду "шампионите" са Петър Петров и Трендафил Трифонов - сумарните времена, за които техните решения минават всички тестове са съответно 0,66 и 0,67 секунди. Това, на практика, са идентични времена - разликата от една стотна можем да пренебрегнем, тъй като точно една стотна е отклонението в сумарното време, което може да се случи при две последователни тествания на програмите. И така, победителите в четвъртия кръг на конкурса са двама - Петър Петров и Трендафил Трифонов. Времената на останалите осем решения с максимален брой точки са с повече от 10 стотни от секудната по-големи от техните - това вече е сериозна разлика с оглед на малките органичения на входните данни (15000 точки).

Алгоритмичният анализ на задача 4 можете да прочетете тук.

Участници (по дата и час на последното получено решение):
1. Николай Чилев - София - 28.01.2001, 07:38
2. Даниел Симеонов - Габрово - 29.01.2001, 09:24
3. Андон Дончев - Варна - 29.01.2001, 17:27
4. Николай Събев - Стара Загора - 05.02.2001, 19:49
5. Валери Цеков - Грамада - 07.02.2001, 13:38
6. Трендафил Трифонов - Велико Търново - 08.02.2001, 17:45
7. Тихомир Върбанов - София - 09.02.2001, 18:21
8. Стоян Йорданов - София - 11.02.2001, 12:11
9. Иван Георгиев - Бургас - 12.02.2001, 17:27
10. Петър Събев - Русе - 13.02.2001, 23:28
11. Петър Петров - София - 14.02.2001, 00:05
12. Мартин Вълканов - София - 14.02.2001, 11:15
13. Свилен Колев - София - 14.02.2001, 11:29
14. Димитър Ковачев - София - 14.02.2001, 13:11
15. Мартин Русков - София - 15.02.2001, 10:51
16. Славяна Генинска - Враца - 15.02.2001, 15:05
17. Димитър Димитров - ? - 15.02.2001, 15:44
18. Григор Илиев - Сандански - 15.02.2001, 16:14
19. Кирил Тодоров - София - 15.02.2001, 17:08
20. Илиян Ненов - Русе - 15.02.2001, 17:31
21. Владимир Недев - Варна - 15.02.2001, 20:52
22. Владимир Молотков - София - 15.02.2001, 22:34
23. Деян Ламбов - Пловдив - 15.02.2001, 23:11
24. Петко Минков - Пловдив - 15.02.2001, 23:40
25. Даниел Трифонов - Балчик - 15.02.2001, 23:44
26. Камен Добрев - София - 15.02.2001, 23:46
27. Иван Станишев - Габрово - 15.02.2001, 24:00
28. Стефан Минков - Габрово - 15.02.2001, 24:00
29. Владимир Молотков - София - 16.02.2001, 18:20 ---> Закъсняло решение

Решенията на всички участници:
За да може всеки лично да се убеди защо класирането е такова и защо има X, а не Y точки, публикуваме всички изпратени решения заедно с изходните кодове на всички програми (с изключение на тези, които пожелаха сорсът им да не се публикува). Можете да ги разгледате от тук (ZIP Format). За всеки участник е създаден и един .log файл, който отразява как са преминали тестовете върху програмата му. Въпросният .log файл се дава само за да добиете представа защо получавате точките, които са ви дадени, но не винаги отразява точната причина за провала на тестовете. Имайте предвид това.

Контестации:
Контестации могат да се подават от всички участници, стига да са основателни . Ще се разглеждат само претенции на участници, които са оценени неправилно в резултат от грешка на журито. Моля преди да изпратите контестация, внимателно прочетете условието на задачата за да прецените дали тя е основателна. Журито ще отговори на всички ваши въпроси, свързани с оценяването. Можете да ни пишете на адрес: konkurs@sagabg.net.

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.