Skip to Content

Резултати от финала за сезон 2012/2013

Написано на 06/21/2013 4:19 pm, от

След около 7 месеца, 5 онлайн кръга, много мегабайти предаден код, тестове, логове и един грандиозен, 24 часов, присъствен финал, можем да кажем, че сезон 2012/2013 завърши успешно и победителите в него са ясни. Те бяха наградени вчера, непосредствено след финала, а в тази публикация ще можете да прочетете подробности относно как финалът протече, както и самото класиране и линкове към предадените от състезателите решения.

Как протече финалът?

Както беше обявено, финалът беше планиран за два дни, като до края на първия ден състезателите трябваше да изпратят решенията си за алгоритмичната част, а за приложната имаха време до сутринта на следващия ден, когато трябваше да я представят пред журито на финала.

Борбата с алгоритмичната част

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

Освен възможността да тестват своите алгоритми директно върху системата, състезателите имаха и друга възможност – да търсят пролуки в тестващата система и да ги съобщават, или експлоатират – както и в истинския живот. Действително получихме няколко съобщения, за потенциално проблемни участъци от кода, като реагирахме с коригирането им и дадохме новата версия на състезателите. Един отбор дори се беше възползвал частично от един „бъг“ – макар това никак да не помогна на резултатът на съответния алгоритъм.

В крайна сметка след доста разписване, премисляне, писане на код и тестване, всички отбори пратиха решения за алгоритмичната част – като този път, за радост на журито, всички бяха спазили формата на файловете, дори и не открихме проблеми при входно-изходните данни.

Приложения посред нощ

Както предполагахме, повечето състезатели се концентрираха върху алгоритъма през деня и оставиха приложната част за писане до сутринта на следващия ден. Беше дълга нощ. С наближаването на изгрева, упоритостта на участниците намаляваше, но все пак до последно останаха няколко отбора – което в последствие се отплати за повечето.

Хранителните запаси свършиха бързо и имаше притичващи до близките магазини за презареждане. За щастие, обаче, кафето беше достатъчно, въпреки олимпийските постижения от 10-20 консумирани бройки, за които някои участници разказаха.

Презентациите пред журито

Спали, недоспали, всички отбори, които се справиха с приложната част, се явиха на защита пред журито, което сформирахме. Имаше както добри, така и не толкова добри приложения, но беше видимо, че всички се бяха потрудили и всяко приложение имаше с какво да се гордее.

За няколко часа успяхме да изгледаме и препитаме всички, като в качеството си на жури се постарахме да дадем и съвети за подобрение на съответните приложения – разбира се отчитайки малкото време, което състезателите имаха.

Интересни впечатления от финала

Правейки равносметка, забелязахме някои интересни факти за участниците и шампионите, които тук ще разкажем.

Всички се усмихваха

Макар и не постоянно, макар и че бяха супер уморени, всички участници се усмихваха – надяваме се, че тези усмивки показваха желанието и удоволствието от участието на този тежък но интересен финал.

Шампионите в алгоритмичната част не успяха да влязат в топ 3

Най-успешният алгоритъм беше изготвен от отбор от двама участници, но явно времето не достигна, за да успее този отбор да изготви достатъчно успешна приложна част. Въпреки това поздравяваме отбора на Красимир Николов и Огнян Петков за най-добро представяне в алгоритмичната част на финалния кръг и убедителното предимство в точките спрямо останалите алгоритми!

Създателите на най-доброто приложение също не достигнаха топ 3

Почти същата ситуация, както при шампионите от алгоритмичната част – отбор с доста добре направена приложна част, изпълняваща почти всички изисквания от условието, с коректен error-handling и сравнително добър дизайн (с малки забележки за цветовото оформление) и ползваемост, също не успя да се пребори за челната тройка, като техният пропуск съответно беше в алгоритмичната част. Отборът започна работа върху приложението сравнително рано, което явно е отнело от времето им за разработка на алгоритъм. Въпреки това, Марио Стоилов и Ивайло Кирилов заслужават похвала за най-изпипаната приложна част на финалния кръг!

„Jack of all trades, master of none, Certainly better than a master of one“

В резултат от последните явления, шампионите в генералното класиране бяха отбори, които са направили „почти най-добрия алгоритъм“ и „почти най-доброто приложение“ – което може би е показателно, че притежаването на добри умения в много сфери надделява на притежаването на най-добрите умения, но само в една сфера. Тъй като мненията по този въпрос са много и с добри доводи, няма да стигаме до заключения и ще ги оставим за читателите.

Самостоятелен участник е в челната тройка

Не е прецедент за състезанието, но все пак е интересно че не малко самостоятелни участници стигнаха до финала, при това един от тях успя да завоюва второ място. Поздравяваме „човекът-отбор“ и му пожелаваме да продължава в същия дух с успехите – а името му ще видите в класирането по-долу.

Определихме челната ++тройка

Типично при онлайн кръговете закръгляме крайните резултати, тъй като разлики по-малки от единица в рамките на 5 кръга не оказват влияние. За финалът обаче, решихме, че е най-добре да запишем резултатите в пълният им вид, или поне закръглени дотолкова, че увеличаването на цифрите след десетичната запетая да не оказва влияние върху класирането.

Така стигнахме до закръгляне до първата цифра след десетичната запетая, което не попречи отборите от второ до четвърто място да са изключително близки по резултати. Не искахме да нарушаваме концепцията за челната тройка, но в този случай направихме компромис и наградихме и четвъртия отбор, тъй като смятаме че техният успех също е значителен.

Финални резултати и шампиони за сезон 2012/2013

Време е да обявим крайните резултати и да поздравим шампионите за сезон 2012/2013. Не сме забравили и да качим всички материали от състезанието – предадени приложни части и алгоритми, логове от тестването на алгоритмичната част наред с тестващата система – можете да ги намерите на обичайното място, по-конкретно на този адрес: http://downloads.academy.telerik.com/svn/pc-magazine/Public/season-2012-2013/final-round/

Поздравяваме шампионите и всички участници и им пожелаваме още успехи както в програмирането, така и в живота!

Място Автор 1 Автор 2 Общо точки Точки алгоритъм Точки приложение
1 Антони Бойков Жеков Ралица Никифирова 14.2 7.3 6.9
2 Пирин Карабенчев 13.3 8.2 5.1
3 Александър Тодоров Надер Дабур 13.2 7.3 5.9
4 Лазар Емилов Георгиев Петър Иванов 13.1 9.1 4
5 Павел Сотиров 13 8.2 4.8
6 Огнян Петков Красимир Николов 12.4 10 2.4
7 Ангел Николов Стоянов Милен Играчев 10.9 6.4 4.5
8 Марио Стоилов Ивайло Кирилов 9.4 1.4 8
9 Деян Петров Йосифов 4.1 4.1
10 Слави Георгиев Иван Лазаров 3.2 3.2
11 Симеон Николов Никита Мошенский 2.7 2.7
12 Пламен Жеков 2.3 2.3
13 Димитър Лазаров 0.9 0.9

Финален кръг на конкурса за сезон 2012/2013 – Битката за гьола

Написано на 06/19/2013 10:15 am, от

Битката за гьола (Жабокалипсис)
Финал на конкурса на Telerik и PC Magazine Bulgaria, сезон 2012/2013

 

Всяка жаба да си знае гьола, но с това глобално затопляне гьоловете на героите в този кръг започват да стават все по-трудноузнаваеми. По последни данни около 18 жаби се борят за оцеляване в намаляващите водни ресурси.

Гьоловете на нашите жаби са малко по-особени – те не са какви да е локви, а са идеални кръгове, в които жабите се помещават. Във всеки гьол има по две жаби, които никак не обичат да се допират една до друга. Толкова не обичат, че като се допрат – умират. Когато гьолът е достатъчно голям това не е проблем. Но както казахме глобалното затопляне е започнало да влияе на тези райски кътчета за нашите жаби – гьоловете се смаляват!

Ако жабите ни можеха да говорят, щяха да кажат, типично по каубойски: „В този гьол няма място и за двамата (двете) ни“. Може би нашите жаби не са толкова далеч от каубоите, защото освен че така биха казали, те са се научили да ползват огнестрелно оръжие. Това прави битката за територия в гьола още по-интересна, нали? Още по-екстремни стават нещата, когато разберем, че жабите ни са доста чувствителни на липса на вода. В момента, в който и най-малката част от тях напусне гьола, жабите умират.

Ще помогнете ли на вашата жаба (нямате си жаба? – е, вече си имате), като напишете програма, която я упътва така, че да оцелее по-дълго от другата жаба в гьола? Е… и в двата случая поне ще ядем жабешки бутчета.

Описание на поведението на жабите и гьола

Гьолът ще представим като окръжност, с център (0,0) и радиус 100 в Евклидова координатна система.

Съответно жабите също ще бъдат кръгове, всяка с радиус 3.5.

Първата жаба се намира на позиция (-80, 0), а втората се намира на позиция (80, 0), тоест симетрично на центъра на гьола по координатната ос X.

За всяка единица време, жабите могат да извършат общо 2 действия, като двете жаби извършват тези действия едновременно:

  • Стрелба в определена посока
  • Скок в определена посока

Също така, за всяка единица време гьолът свива радиусът си с 1, тоест за общо 100 хода гьолът ще стане с радиус 0.

Една жаба може да скочи най-много на разстояние 2 от текущата си позиция. Жабите са много бързи и скокът става мигновено, тоест пренебрегва се времето за придвижване.

Когато една жаба стреля, тя произвежда куршум, който се движи в посоката, в която е изстрелян, със скорост 10 за единица време. Това означава, че ако в първата единица време е изстрелян куршум от (80, 0) към центъра (0, 0), то на втората единица време този куршум ще е стигнал до (70, 0) и в следващите ходове ще продължи да се движи.

Жабите не стрелят точно по нормалния начин – техните куршуми отскачат от водата, като разстоянието между два отскока на един куршум е точно 1. Куршумът може да порази жаба само ако попадне в нея при отскок. Тоест, ако една жаба се намира на една от позициите, на които куршумът ще отскочи, тя ще бъде убита. Математически, ако позицията, от която куршумът отскача, се съдържа в кръга описващ жабата, жабата ще бъде убита.

Куршумът винаги тръгва от центърът на жабата, като първите 3 отскока се пренебрегват (тъй като попадат в стрелящата жаба). Ако куршумът не уцели жаба, той излиза извън гьола.

Посоката на стрелба и посоката на скок се определят с „целево местоположение“, тоест мястото към което скача/стреля жабата. При скок това място може да е извън обсега на жабата, при което жабата ще скочи в тази посока и ще падне там където ? свършва обсега. При стрелбата важи същото правило, с изключението че стрелбата няма обсег, т.е. в определена единица време е гарантирано, че куршумът ще стигне до целта (но не е гарантирано, че там ще има отскок) и след това ще продължи.

Например ако имаме жаба на позиция (-80, 0) и ? кажем да скача към позиция (0,0), то на следващия ход жабата ще бъде на позиция (-78, 0). Скачане и стреляне по диагонал също е възможно, както и във всяка друга посока.

След като стреля веднъж, една жаба има нужда от 7 единици време (хода) за да презареди, през което време не може да стреля.

Ако окръжността, която описва една жаба, пресече или допре окръжността, която описва друга жаба, и двете жаби умират и „двубоят“ завършва наравно.

Ако окръжността, която описва една жаба, пресече или допре ръбът на гьола (т.е. ако част от жабата излезе извън гьола), жабата умира и ако втората жаба е все още жива в този момент, втората печели (и обратно).

Възможно е две жаби се уцелят едновременно с куршуми, „двубоят“ също завършва наравно. Едновременно означава за една и съща единица време (тоест не е от значение на кой отскок са уцелени едната или другата жаба, достатъчно е в един от отскоците това да се е случило).

Алгоритмична задача – стратегия за управление на жаба

Напишете програма, която управлява една жаба, спрямо правилата описани по-горе. Алгоритъмът ще бъде стартиран веднъж за всеки ход, като на всеки ход ще му бъде подавано текущото състояние на гьола, наред с всички куршуми и жаби. Алгоритъмът трябва да изчисли най-доброто действие, което може да предприеме за текущия ход и да го изпечата на стандартния изход, след което да приключи своята работа.

Входни данни

Входните данни се въвеждат от стандартния вход (конзолата)

На първия ред от входните данни стои числото R – текущият радиус на гьола (при първото стартиране на алгоритъма, това число ще бъде 100).

На следващия ред стоят 2 реални и 1 цяло число, разделени с интервали. Двете реални числа описват координатите на жабата, която алгоритъмът управлява (съответно x и y). Цялото число описва след колко единици време жабата ще може да стреля отново (при първото стартиране на алгоритъма, това число е 0, обозначаващо, че е възможна стрелба веднага).

На следващия ред под същата форма е описана жабата на противника

На следващия ред стои едно цяло число N – броят на куршумите, които се намират в гьола в момента.

На всеки един от следващите N реда е описан един куршум, в следния формат:

4 реални числа, разделени с интервали, първите 2 от които описват текущата позиция на куршума, а втората двойка – позицията, на която би стигнал куршумът, ако не уцели жаба (позицията е възможно да бъде извън гьола).

Изходни данни

Изходните данни се печатат на стандартния изход (конзолата).

Алгоритъмът трябва да изведе точно 2 реда на стандартния изход.

Първия ред трябва да съдържа команда за скок, в следния формат:

move координатиX координатиY

Втория ред трябва да съдържа команда за стрелба, в следния формат:

shoot координатиX координатиY

Ако алгоритъмът прецени, че не се нуждае от задаване на някоя от командите, трябва да изпечата празен ред на нейното място.

Ограничения

  • Алгоритъмът трябва да завършва работата си в рамките на 0.2 секунди, в противен случай ще бъде прекъсван автоматично и ще бъде считано, че просто е дал празни команди за тази единица време.

Оценяваща система

Текущата версия на оценяващата система можете да намерите тук: http://downloads.academy.telerik.com/svn/pc-magazine/Public/season-2012-2013/final-round/BattleExecutor.zip

Приложна задача – симулация на Жабокалипсис

За приложната задача, направете приложение, което симулира битката между две жаби, като:

  • Зарежда два алгоритъма, които да бъдат противопоставени един срещу друг
  • Визуализира самата битка между двата алгоритъма
  • Показва резултати от битката, както и статистическа информация (напр. брой на изстрелите, общо изминато разстояние и т.н.)
  • Дава възможност за игра на човек срещу компютър (или човек срещу човек)

Както обикновено, подтикваме състезателите да проявят творчество, като сами преценят как да имплементират изброените функционалности. Възможно е визуализацията да бъде 2D или 3D, приложението да работи в уеб среда или в Desktop режим (а защо да не бъде и Windows Store App). Журито ще оцени положително допълнителни функционалности и оригинални решения.

Критерии за оценяване

Оценяване на алгоритмичната част

При оценяването всеки алгоритъм ще бъде изправен срещу всеки друг алгоритъм. За победа, на един алгоритъм ще се присъждат 2 точки, за равенство – 1, а за загуба – 0. Накрая алгоритъмът с най-много точки ще бъде обявен за победител и ще получи 10 точки в крайното класиране, а останалите – съответната част от тези точки.

Оценяване на приложната част

Оценяването на приложната задача ще се извърши по-следните критерии:

  • Коректност (доколко са имплементирани посочените функционалности) – 2 точки
  • Справяне с грешки (справяне с некоректно поведение и непредвидени ситуации) – 2 точки
  • Ползваемост (доколко е удобна и интуитивна е работата с приложението) – 2 точки
  • UI дизайн (доколко е приятен и удобен дизайнът на приложението) – 2 точки
  • Оригинални функции и решения, които да впечатлят журито – 2 точки
  • Максимални точки в крайното класиране за приложната част: 10

Оценяването ще бъде под формата на представяне на приложението на всеки отбор пред журито. Представянията ще се проведат спрямо програмата на финала.

Допълнителни изисквания

Задачите позволяват използването на различни езици за програмиране и технологии (например C#, PHP, C, C++, Delphi, Python, WPF, Windows Forms, Java, Swing, Flash, JavaScript, HTML5). Всички предадени решения ще бъдат тествани в Windows 7 среда съгласно общите условия на конкурса.

За алгоритмичната част се изисква да бъде предаден пълен сорс код + изпълним файл за Windows (.exe). Ако програмирате на език, който по природа не създава изпълними .exe файлове (например PHP, Python, Java или JavaScript), използвайте подходящ компилатор (потърсете в Интернет).

За приложната част се изисква да бъде предаден пълен сорс код + изпълним файл.Състезателите имат право да изберат начина, по който тяхното приложение ще бъде стартирано, така че това да е удобно в Windows среда (приложението може също да бъде web-базирано и да се отваря през браузър). Тъй като оценяването на приложната част ще бъде извършвано и от гледната точка на потребител (а потребителите искат да стартират едно приложение възможно най-бързо и лесно), сериозни затруднения при намирането и стартирането на приложението могат да намалят присъдените от журито точки.

Характеристики на системата, върху която ще бъде проведено тестването

  • Intel® Xeon® CPU E31225 @ 3.10 GHz
  • 16 GB RAM
  • 128 MB Video Memory (dedicated) Intel® HD Graphics video card
  • 232 GB HDD
  • Microsoft Windows 7 64-bit OS
    • за предалите приложна част на WinRT, тестването на приложната част ще бъде извършено на система с минимални характеристики OS Windows 8 64-bit, 6 GB RAM, Intel i7-720QM, 1GB ATI Mobility Radeon HD 4250.

Видове награди на финалния кръг

Написано на 06/10/2013 5:10 pm, от

Вече сме готови да дадем малко повече яснота по въпроса с наградите за финалния кръг, който ни предстои следващата седмица. Тъй като всички са нетърпеливи за такива вести, ще караме направо по същество.

Както на всяко състезание, първите 3 отбора по общ резултат за алгоритмична + приложна част ще бъдат обявени за шампиони за този сезон на конкурса и ще получат основните награди (самите награди все още няма да обявяваме).

За да бъде по-честно спрямо участниците, които са сами в отбор, решихме да обявим допълнителни, специални награди за тях. Всеки отбор, състоящ се от 1 участник, ще може да се бори за една от следните 2 награди:

  • 1 награда за най-добър алгоритъм на отбор от 1 участник
  • 1 награда за най-добро приложение на отбор от 1 участник

Както се досещате, това означава че освен генералното класиране ще направим допълнително класиране на участниците, които са сами в отбор, съответно по алгоритмични и по приложни части, за да определим получателите на тези награди.

Надяваме се, че се подготвяте духом и тялом за предстоящия финал в стил мини-хакатон на 19 и 20 юни 2013!

Финален кръг на конкурса за сезон 2012/2013

Написано на 06/03/2013 8:11 pm, от

И този сезон на конкурса вече е към края си, но ще се постараем този край да е бляскав. За финалът тази година поканихме 30 отбора, като вече започваме да готвим последното предизвикателство за сезона. Напомняме на състезателите, че на финала всички тръгват наравно – за определянето на финалното класиране ще бъдат ползвани единствено резултатите от самия финал.

В тази публикация накратко ще разкажем каква ще е програмата и какво се очаква от участниците на финала.

Програма на финалния кръг

Финалът ще се проведе в два състезателни дни – 19 и 20 юни, 2013 година – наподобявайки хакатон. Сутринта на първия ден ще обявим задачата. Както на кръговете досега, задачата ще се състои от 2 части – алгоритмична и приложна.

За алгоритмичната част на задачата участниците ще имат на разположение време до вечерта на първия ден, когато ще трябва да предадат решенията си, за да бъдат оценени от системата.

За приложната част участниците ще имат време до сутринта на следващия ден, като могат да изберат да започнат работа по приложната част след като завършат алгоритмичната част или паралелно с нея.

Във втория състезателен ден, отборите ще защитят на живо, пред жури, приложните части, които са разработили. Целта на защитите е отборите да покажат функционалностите, от които най-много се гордеят в приложните си части и да се борят за максимален резултат. Така журито няма шанс неволно да изпусне някоя функционалност, върху която участниците са се трудили, а състезателите ще могат да представят в най-добра светлина своите приложения.

Церемонията по обявяването на резултатите и награждаването ще се проведе малко след като всички участници са представили приложните си части.

Участниците имат право да работят по задачите си само на място – в предназначените за това зали в Академията на Телерик (ще бъдат уточнени на място) – като съответните зали ще бъдат отворени за състезателите през цялото време, в което тече състезанието (включително и през нощта).

По-долу ще видите програмата по часове, като са възможни  известни промени, предимно във втория ден, в зависимост от времето, което представянията ще отнемат:

Ден 1

Час Събитие
09:00-09:45 Настаняване
09:45-10:00 Откриване
10:00-12:30 Състезание
12:30-13:30 Обяд
13:30-20:00 Състезание
20:00-20:15 Предаване на алгоритмичната част
20:15-… Състезание (само приложни части)

Ден 2

Час Събитие
…-09:00 Състезание (само приложни части)
09:00-09:45 Настаняване
09:45-10:00 Приветствие
10:00-12:30 Представяне на приложната част(10 мин на екип)
12:30-13:30 Обяд
13:30-15:30 Представяне на приложната част  (10 мин на екип)
15:30-16:00 Заседание на журито
16:00-16:30 Награждаване на победителите

Награди и сертификати

Всички участвали на финала ще получат сертификати за участие, като шампионите ще получат сертификати за отлично представяне от Академията на Телерик, както и награди от спонсорите. Засега самите награди ще пазим в тайна.

Очакваме ви на финала!

Анализ и резултати от 5 кръг за сезон 2012/2013

Написано на 05/27/2013 5:39 pm, от

С няколко думи, този кръг, който е последен преди финала, може да бъде описан така: алгоритмите изкъртиха, а приложните части имат малко за лепене. Изглежда задачата от този кръг ентусиазира участниците, защото видяхме сравнително високо участие, особено спрямо четвърти кръг. По-силното представяне на алгоритмичната част е още една добра изненада. Сега ще опишем по-подробно какво се случи в този кръг и ще обявим резултатите – както и това кои отбори се класират на финалния присъствен кръг.

За оценяването и резултатите от алгоритмичната част

Както обикновено, за алгоритмичната задача не беше ясно дали съществува оптимално и бързо работещо решение и състезателите бяха принудени сами да измислят идеи за добри решения. Имахме опасения, че поради голямата свобода за решение на поставената задача – разместване на „фигури“ в почти всички посоки – е възможно резултатите да са доста близки. Затова се постарахме да генерираме доста тестове с различни конфигурации на фигури по полет0 – както с много натрупани на едно място фигури, така и с много групи такива фигури и дори с напълно произволни разпределения. Равносметката от генерирането на тестове – 120 на брой тестови файла с всевъзможни конфигурации на фигурите.

Изглежда имаше смисъл от обширното генериране на фигури – повечето резултати се различаваха с не повече от 10-15% (общо разстояние на разместване). Борбата за челните позиции в алгоритмичната част определено беше оспорвана, но въпреки това един от алгоритмите успя да излезе на челна позиция, а след него има няколко завършили „наравно“. Похвално е, че този път не попаднахме на грешки в данните на входа и изхода на алгоритмите, въпреки че нямаше предварително тестване (с изключение на един алгоритъм, при който в папката algorithm изпълнимият файл беше по-малко актуален от този в source).

За оценяването и резултатите от приложната част

Броят на изпратените приложни части беше наполвина на алгоритмичните и изглежда тази задача затрудни повечко участниците. Все пак ставаше дума за контрол над виртуален Бай Иван и събиране и разнасяне на фигури – което бегло наподобява ролева игра. Въпреки това видяхме интересни и добре работещи решения, но имаше и такива, които имат още доста за шлайфане.

Направи впечатление, че доста от приложенията не поддържаха изискваното придвижване на героя. За сметка на това някои решения компенсираха с доста добра ползваемост и насоки към потребителя. Като цяло проблемите, които бяха налице, изглеждаха по-скоро породени от липса на време, отколкото от липса на идеи за реализация.

Резултати и награждаване

В таблицата по-долу ще намерите резултатите за този кръг, като всеки отбор е представен чрез потребителските имена в студентската система на академията на участниците в него (където такива са налични). За този кръг ще обявим първите 3 места за призови, като това включва 4 отбора (3-то място е поделено между 2 отбора). Награждаване на отбелязаните с удебелен шрифт участници ще осъществим в следващите седмици, като ще пишем допълнително на отборите в близките дни.

Автор 1 Автор 2 Общо Алгоритъм Приложение
rnikiforova KOCTEHYPKATA 17 9 8
kaobg /няма username/ 15 8 7
mitko_lazarov 14 9 5
zdravko.beykov 14 10 4
plamen_1 hristy93 12 8 4
migrachev angel.n.stoyanov 8 8 0
ivanbuhov 8 8 0
aleks.todorov nader.dabour 8 7 1
NikolaNikolov 8 8 0
aslv1 7 7 0
FeRt1 7 7 0
technet moshensky 7 4 3
pirin 7 7 0
zhelyazkovn RumenTonev 7 3 4
d_p_y 5 5 0
JavaSTNT 2 2 0
krasi.nikolov ognyan.petkov 2 2 0

Подробни резултати и допълнителни материали

Всички допълнителни материали от състезанието (решения на участниците, тестове, лог файлове на тестването и т.н.) могат да бъдат намерени на този адрес: http://downloads.academy.telerik.com/svn/pc-magazine/Public/.

Класиране за финалния кръг

Както е по регламент, първите 30 отбора (включително) в генералното класиране (в секция Класиране на този сайт) след 5 кръг получават правото да се явят на присъствения финал, който ще се проведе в последните седмици на юни месец. Класиралите се на финал отбори могат да очакват допълнителна информация за финала в идните дни.

Забележка: Някои участници са участвали в повече от 1 отбор, други са участвали в отбори с различни участници (отбелязани са с въпросителна в генералното класиране). На финала един отбор може да се състои от не повече от двама души и отборите, при които има неясноти трябва в следващите дни да съобщят какъв е актуалният им състав, като това може да стане под формата на коментари към тази публикация, или чрез e-mail на адрес academy@telerik.com

Обновено генерално класиране и съкращаване на кръговете

Написано на 04/15/2013 4:53 pm, от

На няколко пъти вече пропускаме да обновим генералното класиране, за което се извиняваме на всички състезатели. Но ето че и затова остана време и генералното класиране след 4-ти кръг е вече факт – както очаквате, то може да бъде намерено в секция Класиране на този сайт.

Забележка: Поради присъединаването на някои нови членове, спирането на участие в конкурса на други, както и някои смени на потребителски имена на някои участници, е възможно в данните за отборите да има пропуснати участници или невярно въведени резултати. Приканваме всички участници да прегледат своите данни и резултати и при неточности да съобщят чрез коментари към тази публикация.

Имаме и друга важна новина за всички участници. Поради различни фактори (най-вече липсата на време за участие при доста от състезателите), организаторите на конкурса взехме решение да променим броя кръгове. По регламент конкурса трябваше да съдържа 6 „онлайн“ кръга и един финален, присъствен. Решихме да намалим онлайн кръговете до 5 – това означава, че текущата задача (към момента на излизане на тази публикация) е задачата за последният за това издание задочен (онлайн) кръг.

Останалата част от Регламента остава валидна – първите 30 отбора в генералното класиране след 5-ти кръг ще бъдат поканени да участват на присъствения финал, който ще се проведе през месец юни, в продължение на два дни, в Академията на Телерик.

Задача #5 за сезон 2012/2013 – къртим мивки, лепим плочки

Написано на 04/12/2013 12:55 pm, от

Къртим мивки, лепим плочки
Задача #5 от конкурса на Telerik и PC Magazine Bulgaria, сезон 2012/2013

 

Stanga

Stanga са спонсори на 5-ти кръг на конкурса

Бай Иван е луд джигит, той е много странен тип и много добър майстор по лепенето на плочки. Също така е и много изобретателен – дори когато клиентите му нямат пари за закупуване на плочки, той намира начин да се снабди с такива и да се залови за работа. Друг е въпросът, че често подходите на Бай Иван не са от най-мирните – любимият му е да разбива мивки (или на съседите на клиента си, или на самия клиент, докато не си е у тях) и да ползва парчетата от тях, за да си изработва плочки.

Тези си „положителни“ качества, обаче, Бай Иван компенсира със своя невероятен мързел. Най-много от всичко той мрази да пренася плочки – колкото по-дълги разстояния трябва да измине разнасяйки плочките, които трябва да лепи, толкова по-лошо. Мързелът на Бай Иван започнал да задейства креативните му способности и той започнал да търси начин да си намали разнасянето. По едно време чул за нещо, наречено „прогамениране“ (всъщност – програмиране) – Бай Иван е гамен и затова думичката му харесала.

Доколкото Бай Иван разбрал, някой може да му напише програма, която му показва начин, по който може да пренесе и постави наличните му плочки, при това с възможно най-малка нужда от носене.

Сега Бай Иван се е обърнал към вас – ще му помогнете ли като му „прогаменирате“ желаното, или ще рискувате вашата мивка да бъде ползвана за източник на плочки?

Съдържание

Описание на плочките, пренасянето и подредбата

Бай Иван, макар и голям майстор, работи по строго определени правила и с ограничен набор от „плочкови фигури„. Плочковите фигури са фигури, които се образуват от залепянето на няколко плочки една до друга, по техните ръбове. Например можем да образуваме символа „+“ (плюс) като залепим 5 плочки – една по средата и четири залепени за нейните ръбове. Бай Иван работи само и единствено с определен набор от такива фигури, като никога не разделя една фигура – например не може да „откачи“ една плочка от плюса. Също така, всички плочки съставящи една фигура са квадратни и с еднакъв размер.

Бай Иван обича да характеризира плочките си, за да изглежда по-умен. Той е измислил термина „централна плочка“, свързан с неговите фигури. Централната плочка е тази плочка от фигурата, която е свързана с най-много други плочки от фигурата. Така например за фигурата „+“, плочката, която е по-средата е свързана с 4 плочки, а всяка една от останалите 4 плочки е свързана с по 1 плочка (т.е. с тази по средата). Съответно тази по средата има най-много залепени за нея плочки и тя е „централна плочка“ за тази фигура.

Преди да започне работа, Бай Иван винаги разчертава работната си площ на квадрати с размера на плочка, под формата на матрица и номерира квадратите спрямо реда и колоната на която се намират, започвайки от 0 (нула). Така първия квадрат на първия ред е [0, 0], втория квадрат на първия ред е [0, 1], първия квадрат на втория ред е [1, 0] и така нататък. След като получи тази матрица, Бай Иван винаги реди своите фигури така, че плочките им да съвпадат с разчертаното на земята.

Видове фигури

Има няколко вида фигури, които Бай Иван ползва. Всяка една от тях ще описваме като квадратите от една матрица, които фигурата би заела, ако централната ? плочка се намира на ред R и колона C (т.е. на позиция [R, C]).

Тук позициите са отбелязани винаги започващи от централната плочка.

  • „деветоплочник“ – заема позиции
    [R,C], [R-1, C], [R-1, C+1], [R, C+1], [R+1, C+1], [R+1, C], [R+1, C-1], [R, C-1] [R-1, C-1]
  • „хоризонтална линия“ – заема позиции [R, C], [R, C-1], [R, C+1]
  • „вертикална линия“ – заема позиции [R, C], [R-1, C], [R+1, C]
  • „плюс“ – заема позиции [R, C], [R-1, C], [R, C+1], [R+1, C], [R, C-1]
  • „ъгъл горе-дясно“ – заема позиции [R, C], [R-1, C], [R, C+1]
  • „ъгъл долу-дясно“ – заема позиции [R, C], [R, C+1], [R+1, C]
  • „ъгъл долу-ляво“ – заема позиции [R, C], [R+1, C], [R, C-1]
  • „ъгъл горе-ляво“ – заема позиции [R, C], [R, C-1], [R-1, C]

Схематично, фигурите изглеждат по следния начин (зеленият квадрат е централната плочка):

деветоплочник

деветоплочник

хоризонтална линия

хор. линия

вертикална линия

верт. линия

плюс

плюс

ъгъл горе-дясно

горе-дясно

ъгъл долу-дясно

долу-дясно

ъгъл долу-ляво

долу-ляво

ъгъл горе-ляво

горе-ляво

С това се изчерпват всички фигури, които Бай Иван може да ползва.

Правила при пренасяне и дължина на път

Когато нашият герой пренася фигури, той има две важни правила.

Първо, той винаги се движи по квадратите, разчертани на земята, като прави стъпка във всеки един от тях. Бай Иван винаги избира най-краткия път за придвижване между две плочки, но НЕ по-права линия. Заради неговите суеверия, той никога НЕ се движи по диагонал, а преминава от един квадрат в друг квадрат, само ако те имат обща страна. Така Бай Иван извършва определен брой крачки, които ще наричаме дължината на пътя, който е изминат, при носене на фигура(брои се единствено пътят изминат в носене на плочки, иначе Бай Иван може да се разхожда без плочки колкото си иска, без това да влиза в сметките). Винаги началото на пътя е квадратът, върху който лежи централната плочка на фигурата и краят на пътя е квадратът, в който трябва да попадне централната плочка на фигурата.

Второто правило е, че при пренасяне на една фигура, нейната ориентация спрямо начертаната матрица не се променя, тоест фигурата не се върти. Формално, операцията по пренасяне на една фигура представлява само и единствено транслация, без ротация.

След като Бай Иван си разчертае работното място, фигурите които той ще ползва биват изсипани безразборно върху квадратите – но отново всяка фигура е цяла, без счупвания, и всяка плочка от нея лежи върху някой от разчертаните квадрати – като много често върху един квадрат се озовава повече от една плочка.

Бай Иван има за задача да подреди (по гореописаните правила) натрупаните фигури така, че никоя плочка от една фигура да не лежи върху плочка от друга фигура, тоест да няма квадрати от матрицата, върху които има повече от една плочка.При това Бай Иван иска да свърши тази задача, като извърви възможно най-кратко разстояние носейки плочки.

Алгоритмична задача – логика за подредба на плочки

Напишете програма, която по дадени фигури и тяхното начално разположение определя за всяка една плочка такова местоположение, до което трябва да бъде пренесена, така че в никой квадрат да не се намира повече от една плочка и така че общият изминат път от Бай Иван да е възможно най-кратък. Всяка фигура има местоположение определено от централната ? плочка. Обърнете внимание, че не е нужно всяка една фигура да бъде преместена. Например може да имаме всичко на всичко две фигури, които се застъпват – в такъв случай е

достатъчно да пренесем само едната на ново местоположение, а другата да си остане на предишното. Програмата ви трябва да опише крайно местоположение, за всяка една фигура, като крайното и началното положение на една фигура може да съвпада (както в примера), стига да е изпълнено условието описано по-горе.

Входни данни

Входните данни се въвеждат от стандартния вход (конзолата).

На първия ред от входните данни стои числото N – броя фигури, разположени върху разчертаното от Бай Иван работно поле.

На всеки един от следващите N реда стои име на фигура, номер на реда и номер на колоната в таблицата, върху които се намира нейната централна плоча, разделени с интервали.

Имената на описаните по-горе фигури са както следва:

  • фигура „деветоплочник“: ninetile
  • фигура „плюс“: plus
  • фигура „хоризонтална линия“: hline
  • фигура „вертикална линия“: vline
  • фигура „ъгъл горе-дясно“: angle-ur
  • фигура „ъгъл долу-дясно“: angle-dr
  • фигура „ъгъл долу-ляво“: angle-dl
  • фигура „ъгъл горе-ляво“: angle-ul

За пример, един ред дефиниращ вертикална линия с централна плочка на позиция [1, 3] (втори ред, четвърта колона – броим от нула) ще изглежда така:

vline 1 3

За алгоритмичната част входните данни винаги ще бъдат валидни и в описания формат.

Изходни данни

Изходните данни се печатат на стандартния изход (конзолата).

Алгоритъмът трябва да изведе точно N реда – по един за всяка фигура от входните данни(в същия ред), определящ крайното ? местоположение.

На всеки един от изведените редове трябва да има точно 2 числа, разделени с по един интервал – описващи реда и колоната, на които трябва да бъде крайното местоположение на съответната фигура (т.е. на които ще се намира централната ? плочка).

Ограничения

  • N ще бъде цяло число между 3 и 1000
  • Полето (матрицата), в което Бай Иван работи е винаги с размери 500 по 500, като първия ред/колони е с номер 0 (нула) а последния ред/колона е с номер 499 (т.е. съдържа общо 250000 квадрата)
  • Началното местоположение на фигурите ще бъде такова, че няма да има плочки на някоя фигура, които излизат извън полето
  • Крайното местоположение на фигурите трябва да бъде такова, че нито една плочка на която и да е фигура да не излиза извън полето
  • Алгоритъмът трябва да завършва работата си в рамките на 3 секунди, в противен случай ще бъде прекъсван автоматично и ще получи 0 точки за съответния тест

Примери

С тези примери ще онагледим правилно форматиран вход и изход. Примерите имат за цел само да покажат правилния формат, а не да дават оптимално решение на задачата. Изображенията в обясненията ползват представяне, където най-долния ред е нулев, този над него и първи и т.н.

Първи пример

Примерен вход Примерен изход
2
plus 1 1
vline 2 2
1 1
2 3

Първоначално състояние

Начално състояние

Крайно състояние

Крайно състояние

Обяснение:

Имаме точно 2 фигури, които се „пресичат“ (имат общи позиции на плочки), съответно със зелена и синя централна плочка. Достатъчно е да преместим само едната, в случая вертикалната линия. При това преместване Бай Иван ще измине точно 1 стъпка.

Втори пример

Примерен вход Примерен изход
3
plus 1 1
ninetile 3 1
vline 2 2
2 1
4 3
1 3

Начално състояние

Начално състояние

Крайно състояние

Крайно състояние

Обяснение:Имаме 3 фигури, всички от които се „пресичат“. Първа във входа е фигурата плюс и затова местим нея първо – качваме я един ред нагоре (в случая това е по-скоро излишна операция, която ни удължава общия път – но не е некоректно поведение, просто е неоптимално). След това местим „деветоплочникът“ и накрая преместваме „вертикалната линия“ с един ред надолу и една колона надясно. Общият път, които Бай Иван ще измине носейки е 1 + 3 + 2 = 6.

Приложна задача – симулация на Бай Иван

Освен алгоритъм, който му показва най-ефективния начин да премести фигурите, Бай Иван иска и още нещо. Той иска да експериментира и да изпробва какви подредби може да извършва, без да се поти – иска симулация на себе си!

Симулацията трябва да предоставя възможността да се контролира виртуално копие на Бай Иван, с което потребителя да може да събира плочки и да ги поставя по работното поле, както и просто да обикаля из него безцелно при желание (Бай Иван обича да обикаля безцелно). Също така Бай Иван иска някои допълнителни неща, които по-точно да симулират работата му:

  • Възможност за набавяне на допълнителни плочки от къртене на мивки (независимо дали са на съседи или не)
  • Възможност за следене на общото изминато разстояние
  • Запазване на резултати
  • Избор на автоматичен контрол на Бай Иван за подреждане на плочки (избиране на алгоритъм, работещ по гореописаният начин и автоматично изпълнение на посочените от алгоритъма действия)

Както обикновено, подтикваме състезателите да проявят творчество, като сами преценят как да имплементират изброените функционалности. Възможно е визуализацията да бъде 2D или 3D, приложението да работи в уеб среда или в Desktop режим (а защо да не бъде и Windows Store App). Журито ще оцени положително допълнителни функционалности и оригинални решения. Ето няколко (неизчерпателни и незадължителни за имплементация) идеи:

  • различни по размери полета
  • препятствия
  • възможност за ротация на фигурите
  • възможност за разбиване на фигурите на съставните им части
  • Бай Пешо, който да пречи на Бай Иван
  • възможност за „multiplayer“
  • възможност за „запис на симулация“ – запис на извършените действия и изпълняването им наново

Вярваме, че участниците ще измислят още и иновативни начини да удоволетворят Бай Иван.

Критерии за оценяване

Оценяване на алгоритмичната част

При оценяването ще бъдат генерирани тестове от журито, с различни подредби на фигури.

  • Данните от всеки тест на журито ще бъдат подадени на всеки един предаден алгоритъм.
  • За всеки тест ще се намира най-добрия резултат на алгоритъм и той ще получи максималните точки за този тест, а останалите ще получат съответния процент от тези точки за този тест (т.е. скалирането се извършва за всеки тест).
    • В тази задача най-добър означава най-кратко общо изминато разстояние (което оценяващата система ще изчислява на база изведените промени в местоположенията)
  • Например, ако за задачата има 10 теста, то всеки ще носи по 1 точка.
    • Ако на първото поле най-добре представилият се алгоритъмът G е описал премествания, за които общият път е 10
    • алгоритъмът M – 15,
    • а алгоритъмът L – 30, то
    • в крайна сметка точките за този тест са:
      • G: 1 точка
      • M: 0.67 точки = 1/(M/G) = 1/(15/10)
      • L: 0.33 точки = 1/(L/G) = 1/(30/10)
  • По същия начин се оценяват всички тестове, точките се сумират и след това се закръглят до цяло число
  • Максимални точки в крайното класиране за алгоритмичната част: 10

Оценяване на приложната част

Оценяването на приложната задача ще се извърши по-следните критерии:

  • Коректност (доколко са имплементирани посочените функционалности) – 2 точки
  • Справяне с грешки (справяне с некоректно поведение и непредвидени ситуации) – 2 точки
  • Ползваемост (доколко е удобна и интуитивна е работата с приложението) – 2 точки
  • UI дизайн (доколко е приятен и удобен дизайнът на приложението) – 2 точки
  • Оригинални функции и решения, които да впечатлят журито2 точки
  • Максимални точки в крайното класиране за приложната част: 10

Допълнителни изисквания

Задачите позволяват използването на различни езици за програмиране и технологии (например C#, PHP, C, C++, Delphi, Python, WPF, Windows Forms, Java, Swing, Flash, JavaScript, HTML5). Всички предадени решения ще бъдат тествани в Windows 7 среда съгласно общите условия на конкурса.

За алгоритмичната част се изисква да бъде предаден пълен сорс код + изпълним файл за Windows (.exe). Ако програмирате на език, който по природа не създава изпълними .exe файлове (например PHP, Python, Java или JavaScript), използвайте подходящ компилатор (потърсете в Интернет).

За приложната част се изисква да бъде предаден пълен сорс код + изпълним файл. Състезателите имат право да изберат начина, по който тяхното приложение ще бъде стартирано, така че това да е удобно в Windows среда (приложението може също да бъде web-базирано и да се отваря през браузър). Тъй като оценяването на приложната част ще бъде извършвано и от гледната точка на потребител (а потребителите искат да стартират едно приложение възможно най-бързо и лесно), сериозни затруднения при намирането и стартирането на приложението могат да намалят присъдените от журито точки.

Характеристики на системата, върху която ще бъде проведено тестването

  • Intel® Xeon® CPU E31225 @ 3.10 GHz
  • 16 GB RAM
  • 128 MB Video Memory (dedicated) Intel® HD Graphics video card
  • 232 GB HDD
  • Microsoft Windows 7 64-bit OS
    • за предалите приложна част на WinRT, тестването на приложната част ще бъде извършено на система с минимални характеристики OS Windows 8 64-bit, 6 GB RAM, Intel i7-720QM, 1GB ATI Mobility Radeon HD 4250.

Краен срок

Краен срок за предаване на решения: 12 май 2013 г, 23:59:59 часа.

Решенията се предават в студентската система на Академията на Телерик, на адрес http://telerikacademy.com/Courses/Courses/Details/13 според инструкциите, описани в раздела “Качи решение” на официалния сайт на състезанието.

Анализ и резултати от четвърти кръг за сезон 2012/2013

Написано на 04/10/2013 12:12 pm, от

Изглежда този път source-ът не беше с даджаите на тази им „мисия“ и малцина герои успяха да се преборят напълно с предизвикателството – малцина, но за щастие ги имаше. Преди няколко дни завърши четвърти кръг на конкурса и вече резултатите са готови и можете да ги видите, по традиция, на края на тази публикация. А преди това ще поговорим набързо за събитията случили се в нашата никак неотдалечена галактика – по конкретно за оценяването и впечатленията от алгоритмичната и приложната част на задачата от четвърти кръг.

За оценяването и резултатите от алгоритмичната част

За този кръг е трудно да се каже дали алгоритмичните или приложните части затрудниха повече състезателите. Както винаги изготвихме тестове, които да пуснем в алгоритмите, като в случая това беше сравнително лесна задача – просто си избирахме достижими публични страници от сайтовете на Академията на Телерик (или видеа от YouTube канала – които бяха „по-трудните“ тестове).

Получихме няколко алгоритъма, но за съжаление голямата част от тях имаха сериозни проблеми с бързодействието, дори и на „по-лесните“ тестове. Всички състезатели предали алгоритми, се бяха досетили, че трябва да се обходят страниците на академията и да се запазят локално адресите и връзките между тях, за да може да се осъществява намиране на път без нужда от Интернет връзка – което е похвално. Но изглежда търсенето в локалните данни не беше оптимизирано, или алгоритъмът за намиране на път при много е бил твърде бавен – за подсказка към състезателите, страниците и връзките между тях могат да се представят като свързан граф, където намирането на най-кратък път може да се осъществи ефективно чрез търсене в ширина. Намирането на адресите в локално запазените данни може да се забърза чрез запазването им в структура като двоично дърво за търсене, което да се сериализира върху диска, или дори като хеш-таблица. В допълнение, не е нужно зареждането на всички данни при търсенето, защото те най-вероятно ще са често повече от нужното. Това са само идеи, но най-вероятно с малко обмисляне биха забързали алгоритмите на участниците.

При добре работещите алгоритми най-честите проблеми бяха „пропускане“ на страници от пътя (най-вероятно самото извеждане пропускаше), както и извеждане на неправилни хиперлинкове – или такива, които не съществуват на страницата, или още по-често релативни, които имат няколко наклонени черти повече. На няколко пъти попаднахме на избиране на хиперлинкове които връщат на същата страница (например href=“#“) – което не е голям проблем, но потенциално удължава пътя и намалява резултата.

Поради малката бройка алгоритми, оценяването проведохме на ръка (единствено времето за изпълнение засичахме автоматично), за да сме сигурни, че алгоритмите избираха коректни и съществуващи пътища – така сме и по-сигурни, че нямаме „бъгове“ в оценяването.

За оценяването и резултатите от приложната част

Този път приложната и алгоритмичната част бяха по-тясно свързани и това си пролича по резултатите – авторът на най-добре представилият се алгоритъм е и автор на най-доброто приложение. Макар приложението да има още място за подобрение, за този кръг беше единственото, което напълно да изпълнява изискваното търсене и визуализация на свързани страници. Останалите приложни части или изобщо нямаха тази функционалност, или тя не работеше коректно или показваше повтарящи се резултати, несвързани с конкретната задача. Въпреки това журито се постара да оцени всички предадени приложения по описаните критерии.

Тук единствено трябва да отбележим, че ниски точки за „справяне с грешки“ и „ползваемост“ получиха приложения, които нямаха гореспоменатата основна функционалност,  тъй като за този кръг тези критерии мерихме предимно спрямо тази функционалност.

Резултати и награждаване

Ето и класирането – както обикновено, участниците са представени чрез потребителските им имена в студентската система на Телерик.

В този кръг ще наградим само първо място, тъй като разликата в резултата със следващите отбори е твърде голяма.Награждаването за този кръг ще бъде проведено със забавяне, най-вероятно следващия месец – като допълнително ще пишем на отбора на първо място.

Очакваме с нетърпение участието ви в следващия кръг, задачата за който ще обявим след няколко дни!

Автор 1 Автор 2 Общо Алгоритъм Приложение
KOCTEHYPKATA   18 10 8
krasi.nikolov ognyan.petkov 6 6 0
aleks.todorov nader.dabour 3  0 3
pemmpty  lazo003 3  0 3
aslv1 0  0 0
JavaSTNT 0 0 0

Подробни резултати и допълнителни материали

Всички допълнителни материали от състезанието (решения на участниците, тестове, лог файлове на тестването и т.н.) могат да бъдат намерени на този адрес: http://downloads.academy.telerik.com/svn/pc-magazine/Public/.

Анализ и резултати от трети кръг за сезон 2012/2013

Написано на 03/08/2013 7:15 pm, от

Доста пилешко и свинско отиде, но мирът в Га-нгнамландия вече е осигурен. Резултатите от трети кръг са готови. Състезателите се бяха постарали за алгоритмичната част, а в приложната също имаше добри попадения, макар и общото представяне да беше малко по-слабо от това на миналия кръг. Тъй като всички са нетърпеливи, набързо ще кажем няколко думи и ще обявим резултатите.

За оценяването и резултатите от алгоритмичната част

Тази задача беше интересна с две неща. На първо място, състезателите бяха изправени пред решаване на задача, която често се среща в съвременните стратегически игри (по-конкретно Turn-based strategy игрите) – да измислят игрова логика, справяща се възможно най-добре в зададения свят. Не е ясно дали оптимално решение в зададените ограничения съществува, и всички успешни алгоритми в един или друг смисъл ползваха определени евристични подходи в решението. Другата интересна част беше „играта“ и от двете страни – и на атакуващия и на защитаващия. Атакуващия съответно беше алгоритъма, а защита всъщност беше задача за генериране на тест, който е възможно най-труден за останалите алгоритми, но за който авторите би следвало да знаят най-доброто решение. Тук предполагахме, че състезателите ще генерират тест и предварително ще изчислят най-доброто възможно поведение за него, и в ще вкарат това поведение в алгоритъма си при разпознаване на техния тест. Поздрави на всички, които се постараха да се справят с тази задача.

Тестовете, проверката, резултатите

В този кръг, макар да имахме „помощ“ от състезателите с генерирането на тестовете, все пак искахме да сме коректни и да генерираме добри тестове. Но „добри“ и „изчерпателни“ тестове за тази задача не беше ясно как можем да създадем – променливите и взаимовръзките между тях бяха твърде много, за да е смислено напълно автоматизирано генериране (освен ако не бяхме решили да отделим 1 месец само за това). В същото време, генериране на ръка щеше да е също доста трудоемко и нямаше да покрие достатъчно случаи. Без малко да стигнем до вица за компромисния вариант, когато се досетихме, че можем да направим хибридно, полуавтоматизирано генериране на тестове.

Генерирането протече по следния начин: генерирахме определен брой матрици с размерите на игралното поле и във всяка от тях разположихме по определени начини солни мини и оборудвани пилета. Идеята беше проста – в контекста на тази задача смислени тестове са такива, в които позиционирането един човек защитник би създал, за да се защитава възможно най-добре, плюс няколко различни конфигурации, които не са най-добрите възможни защити, но са доста разпилени из пространството. След това върху всяка матрица пуснахме на няколко пъти генератор, който да избере по колко единици да сложи на определена позиция. Така получихме една сравнително разнообразна и смислена колекция от 45 теста. Оттам нататък включихме 14-те валидни тестовете и на участниците, за да си завършим колекцията.

Оценяването се проведе на две фази – първо изпълнихме всички тестове на журито, след това всички тестове на участниците върху всички алгоритми. След това взехме средно аритметичния резултат на всеки алгоритъм от двете фази като краен резултат – тоест изпълнихме обещанието за равнопоставеност на тестовете на журито с тези на участниците.

Резултатите, които получихме, бяха сравнително добри. Както винаги, имаше няколко алгоритъма, които не функционираха точно както се очакваше. За щастие обаче този път не се наложи да правим корекции по алгоритмите на участниците, а само направихме проверката малко по-толерантна към невалидни данни (предимно игнориране на излишни команди и закръгляне на не-цели числа за координатите, каквито по условие не може да има).

За оценяването и резултатите от приложната част

Ако трябва да сме честни, очаквахме повече в приложната част. Вярно, имаше доста силни решения, които си бяха почти напълно завършени игри, но много от участниците не бяха пратили решения изобщо, а някои от пратените имаха сериозни проблеми с функционирането и ползваемостта. Разбира се, журито много добре разбира сложността на създаването на една работеща игра и по никакъв начин не омаловажява труда на участниците.

Оценяването протече сравнително безаварийно и макар в началото да изглеждаше, все едно задачата сериозно е затруднила всички, се появиха решения които бяха впечатляващи. С две думи, някои приложения имаха проблеми с приемането на входни данни, както и с цялостното изпълнение на „играта“. В общата картина, повечето приложения бяха сравнително трудни за ползване (някои дори не представяха игралното поле), но почти навсякъде най-основните неща нужни, за да може да се „играе“ все пак бяха на лице (макар и не винаги твърде удобни). Трябва да се отбележе, че състезателите се бяха постарали да пресъздадат атмосферата на задачата – видяхме какви ли не карикатури на фермери и добитък, а на места и някои интересни истории. Имаше няколко решения, чиито техническо изпхълнение беше на доста добро ниво и те добре ще си проличат от класирането – силно препоръчваме да пробвате решенията на отборите в челните места по приложната част – няма да останете разочаровани.

Резултати и награждаване

Ето и класирането – както обикновено, участниците са представени чрез потребителските им имена в студентската система на Телерик.

В този кръг първите 3 места са доста добре отличени и представителите на отборите по традиция ще бъдат поканени на награждаване, за което ще се свържем със съответните участници в началото на следващата седмица.

Радваме се на продължаващото ви участие и очакваме да премерите сили в следващия кръг!

Автор 1 Автор 2 Общо Алгоритъм Приложение
paveld3 at.keranov 20 10 10
KOCTEHYPKATA desi.docheva 17 9 8
kdikov nikola76 16 9 7
krasi.nikolov ognyan.petkov 13 7 6
plamen_1 hristy93 12 7 5
pemmpty lazo003 9 5 4
d_p_y mariq88 8 5 3
mitko_lazarov 8 8 0
pirin isipro 8 8 0
aleks.todorov nader.dabour 7 3 4
aslv1 erik1001 7 4 3
angel.n.stoyanov migrachev 5 5 0
yonko.tsonev 4 1 3
staafl 2 2 0
cocodonchev rusiqt 1 1 0
JavaSTNT 0 0 0
MarinDraganov veke_D 0 0 0

Предстои да обновим и генералното класиране в страницата Класиране в следващите дни.

Подробни резултати и допълнителни материали

Всички допълнителни материали от състезанието (решения на участниците, тестове, лог файлове на тестването и т.н.) ще могат да бъдат намерени до няколо дни след класирането на този адрес: http://downloads.academy.telerik.com/svn/pc-magazine/Public/.

P.S.: Честит 8 март на всички празнуващи : ) !

Задача #4 за сезон 2012/2013 – от Интернет, батка

Написано на 03/06/2013 9:55 pm, от

От Интернет, батка!

Задача #4 от конкурса на Telerik и PC Magazine Bulgaria, сезон 2012/2013

 

Не много отдавна, в една никак неотдалечена галактика, двама даджаи обмисляли как да оптимизират навигацията в сайта на Академията на Телерик. Вокан и Орож, уморени от дългото мислене върху тази задача, решили да разнообразят малко нещата, като си направят едно „даджайско състезание“. Те решили да изберат два произволни URL адреса (сочещи само към страници, свързани с Академията на Телерик – от официалния сайт, YouTube канала, студентската система и сайта на конкурса по програмиране) и да се състезават кой по-бързо ще успее да „стигне“ от единия адрес до другия, единствено ползвайки хиперлинкове за „придвижване“. В едно от състезанията, Орож решил да си помогне, като генерира sitemap на сайта, в който били двата хиперлинка. Операцията била бавна, но когато завършила , Орож се ориентирал по-бързо от обикновеното. Когато показал тази хитрина на Вокан, той казал „Ахахахааа, откъде го взе това“, а Орож отговорил „От Интернет, батка!“.

Въпреки интересната случка, Вокан и Орож все още не били доволни – този sitemap бил приблизителен ориентир. Те искали бърз отговор, съдържащ всички хиперлинкове от пътя, по който трябва да се мине, за да се стигне от една страница до друга страница – ако такъв път изобщо съществувал. Готови ли сте да помогнете на Вокан и Орож, като откривате страниците, свързващи 2 други страници в мрежата от страници, свързани с Академията?

Съдържание:

Описание на „Даджайско състезание“

Както е описано по-горе, даджайското състезание представлява задача за намиране на път между 2 уеб страници, който се състои от хиперлинкове (хипервръзки/препратки…) – като допълнително, пътят трябва да има възможно най-малка дължина (защото може да има повече от един път). Дължина на пътя ще наричаме броя хиперлинкове, които един даджай трябва да кликне, за да стигне от началната до крайната страница включително.

По-формално, за всеки две страници A и B ще казваме, че A е свързана към B, ако някъде в страница A има поне един хиперлинк, препращащ към страница B. Съответно път от страница X до страница Y ще наричаме такава поредица от N страници, в която страница[1] = X, страница[N] = Y и за която всяка страница[i] е свързана със страница[j], където i е в интервала [1, N-1], a за j винаги е изпълнено j = i+1. Дължината на този път е точно равен на N-1 (ако имаме 2 страници в пътя – само начална и крайна – тогава дължината на пътя ни е точно 1)

За хиперлинковете, които могат да се ползват за придвижване, важат следните правила:

  • Хиперлинковете са валидни anchor тагове в изходния HTML код на страницата, с валидни href атрибути, състоящи се от URL на страница (по-долу ще видите и характеристики за страниците).
  • Хиперлинковете НЕ Е възможно да бъдат генерирани от изпълнението на код при клиента (напр. JavaScript който добавя линкове)
  • НЕ СЕ СЧИТАТ за хиперлинкове URL адреси в чист текст. Например този текст: http://academy.telerik.com НЕ Е хиперлинк

Всички страници от пътя, включително началната и крайната, задължително трябва да бъдат от следните:

Уточнение за YouTube канала:

НЕ Е разрешено ползването на други страници от YouTube – например главната страница на канала (забележка: този линк има няколко разновидности), списъкът с всички плейлисти, списъкът с всички видеа и т.н. – НЕ могат да бъдат страници в пътя.

Също така, НЕ всички хиперлинкове от страниците на видеата и страниците на плейлистите могат да бъдат ползвани. Ето и допълнителните изисквания за хиперлинковете от позволените страниците в YouTube канала:

  • За страници на видеа:
    • могат да бъдат ползвани само и единствено хиперлинкове, намиращи се в елементи с атрибут id=“eow-description“ (#eow-description), тоест в описанието на видеото
  • За страници на плейлисти
    • могат да бъдат ползвани само и единствено хиперлинкове, намиращи се в елементи с атрибут class=“primary-pane“ (.primary-pane), тоест хиперлинкове към видеа от съответния плейлист

Уточнение за Студентската система на Академията на Телерик (http://telerikacademy.com)

Разрешено е ползването на почти всички страници и хиперлинкове, при условие че те са видими без профил в системата – т.е. това което е видимо, когато потребителят не се е логнал.

НЕ Е разрешено, обаче, ползването на хиперлинкове, които се намират в някои елементи на главната страница:

  • Не е разрешено ползването на хиперлинкове от елемент с атрибут id=“fb0021a1c“ (Facebook plugin)
  • Не е разрешено ползването на хиперлинкове от елемент с атрибут id=“RecentVideoHeader“ („Последни видео материали“)
  • Не е разрешено ползването на хиперлинкове от елемент с атрибут id=“ForumPostsHeader“ („Последни форум постове“)
  • Не е разрешено ползването на хиперлинкове от елемент с атрибут id=“BlogPostsHeader“ („Най-нови блог постове“)
  • Не е разрешено ползването на хиперлинкове от елемент с атрибут id=“IndexCalendarHeader“ („Календар“)

Уточнение за сайта на Конкурса по програмиране (този сайт)

Всички страници от сайта на конкурса могат да бъдат ползвани, като единствено НЕ Е разрешено ползването на хиперлинкове, намиращи се в коментари към някоя от темите. Тоест, не е разрешено ползването на хиперлинкове намиращи се в елемент с атрибут id, започващ с „comment-„.

Алгоритмична задача

Алгоритмичната задача за този кръг отново ще бъде разделена на две части – една за създаване на алгоритъм и една за генериране на тест.

Задача за алгоритъм за намиране на най-кратък път по хиперлинкове между две страници

Напишете алгоритъм, който по дадени URL адреси на начална и крайна страница, намира най-краткия път между тези две страници по описаните правила и отпечатва хиперлинковете, които е използвал за да измине този път.

Всички тестове ще се провеждат, като се взема предвид състоянието на абсолютно всички страници, които потенциално могат да участват в някой път (спрямо условието на задачата) от дата 6 април 2013 г. Това означава, че ако в отговорът на някой алгоритъм се генерира път, в който участват страници или хиперлинкове, появили се след 23:59:59 на 6 април 2013 г., този отговор ще бъде счетен за невалиден и алгоритъмът ще получи 0 точки за съответния тест!

Забележка 1: ако 2 поредни страници са свързани с повече от един хиперлинк, за тях трябва да бъде изведен точно един от свързващите ги хиперлинкове.

Забележка 2: два хиперлинка може да изглеждат различно, но да сочат към един и същи ресурс – например http://konkurs.devbg.org/rules/#contest-description и http://konkurs.devbg.org/rules/.

Задача за генериране на тест – начален и краен URL адрес, между които да бъде намерен път

Напишете входни данни, в описания по-долу формат за входни данни, които описват стартов и краен URL, между които да бъде намерен път. Както е описано по-долу, задължително е такъв път да съществува. Входните данни трябва да бъдат валидни и в описания по-долу форматв противен случай тестът няма да бъде вземан предвид.

Входните данни трябва да бъдат записани в стандартен текстов файл (.txt) с ASCII кодировка, който може да бъде преглеждан в Windows среда чрез текстов редактор Notepad. За примери може да видите тестовите файлове публикувани за предишни кръгове на задачата (публичното хранилище на състезанието е на този адрес: http://downloads.academy.telerik.com/svn/pc-magazine/Public/)

Предаването на теста ще става чрез поставянето му в папката algorithmнаред с изпълнимия файл за алгоритмичната задача. Файлът трябва да бъде именован както е името на потребителя, който го е изпратил (например ако потребителят е george.s.georgiev, то файлът трябва да носи името george.s.georgiev.txt).

При тестването, входните данни от теста ще бъдат подадени на всеки един алгоритъм, включително и на алгоритъма на автора.

Входни данни

Входните данни се въвеждат от стандартния вход (конзолата).

Входните данни се състоят от точно два реда, на всеки от които има по един низ от символи.

На първият ред стои низ с URL на страницата, от която трябва да започва пътят (т.е. първата страница).

На втория ред стои низ с URL на страницата, в която трябва да свършва пътят (т.е. последната страница).

Във всички тестове задължително ще съществува път между двете страници.

Във входните данни НЕ може да се съдържа символът # (диез)

Входните данни ще бъдат винаги валидни и в описания формат.

Изходни данни

Изходните данни се извеждат на стандартния изход (конзолата).

Изходните данни се състоят от редове, като на всеки ред е изписан по точно един URL. Този URL е стойността на href атрибута на съответния <a> елемент, който свързва две поредни страници в пътя. href атрибутът не трябва да бъде променян спрямо първоначалния му вид в съответната страница.

Например ако от страница A към страница B имаме хиперлинк, чиито код е <a href=“http://example.com/B#some-element-id“>link</a>, тогава на съответния ред от изходните данни трябва да стои низът http://example.com/B#some-element-id.

Алгоритъмът трябва да изпечата точно толкова редове с низове, колкото хиперлинка е ползвал в най-краткия път между зададените начална и крайна страница.

Допълнителни ограничения

  • Всички тестове ще се провеждат, като се взема предвид състоянието на абсолютно всички страници, които потенциално могат да участват в някой път (спрямо условието на задачата) от дата 6 април 2013 г. Това означава, че ако в отговорът на някой алгоритъм се генерира път, в който участват страници или хиперлинкове, появили се след 23:59:59 на 6 април 2013 г., този отговор ще бъде счетен за невалиден и алгоритъмът ще получи 0 точки за съответния тест!
  • Във входните данни НЕ може да се съдържа символът # (диез)
  • В изходните данни, ако алгоритъмът е избрал хиперлинк с #, то както е по условие, този диез трябва да бъде изпечатан. Тестващата система ще съобразява, че URL с диез сочи към същата страница, към която и URL без диеза и низът след него
  • От 00:00:00 до 23:59:59 часа на 6 април 2013 г. няма да бъдат правени промени (или добавяне/премахване) на хиперлинкове в която и да било страница, която според условието е възможно да участва в който и да е път.
  • За всички тестове ще съществува път между началната и крайната страница
  • Интернет връзката на тестващата машина няма да бъде спирана, но не можем да гарантираме за скоростта и надеждността ? (нито пък за всички сървъри, на които се намират потенциални участващи в различните пътища страници). Ползването на Интернет връзка (и съответно обновени ресурси, които са в разрез с първата точка от тези ограничения) е риск, който състезателите могат да преценят дали да поемат
  • Ако някой от ползваните от алгоритъма URL адреси не съществува на съответните страници, алгоритъмът ще получи 0 (нула) точки за съответния тест
  • Ако последователността от изведените от алгоритъма URL адреси не води до зададената крайна/последна страница, алгоритъмът ще получи 0 (нула) точки за съответния тест
  • Програмата трябва да завършва своята работа за най-много 5 секунди. След изтичане на времето програмата ще бъде спряна автоматично.

Примери

С тези примери ще онагледим правилно форматиран вход и изход. Примерите имат за цел само да покажат правилния формат, а не да дават оптимално решение на задачата.

Примерен вход
http://konkurs.devbg.org
http://academy.telerik.com/school-academy/meetings/details/2012/11/22/databases
Примерен изход
http://konkurs.devbg.org/submit/
http://telerikacademy.com/Courses/Courses/Details/13
http:?/?/?academy.telerik.com/?
school-academy/meetings
meetings/details/2012/11/22/databases

Пояснение: Първо отиваме в страницата за „качване“ където има линк към студентската система, оттам намираме линк към academy.telerik.com (в секцията „Полезни линкове“), откъдето пък в секция Училищна Академия избираме Уроци и оттам – линка за срещата за бази данни, която ни е целта.

Примерен вход
http://www.youtube.com/watch?v=AoewJHW9Oqc
http://academy.telerik.com/
Примерен изход
http://academy.telerik.com/

Пояснение: Намираме се в страница с видео, в чието описание има директен линк към страницата на Академията, отпечатваме го и приключваме работа.

Приложна задача – визуализация на възможните за достигане страници от стартова страница

Напишете програма, която по дадена начална страница от гореописания вид генерира визуализация на всички страници, които могат да бъдат достигнати чрез движение по хиперлинкове от нея. Програмата трябва да приема входни данни за начална страница, да обхожда достижими от нея страници, да визуализира тези страници и връзките ? с началната – било то чрез обект представящ всяка страница и връзки между страниците (както е показано тук, но с по-детайлни „върхове“), или чрез дърво подобно на файловата система, или чрез контроли които позволяват семантично приближение (semantic zoom) за наблюдение на общата картинка или на детайли от нея, или чрез 3D свят в който страниците са свързани летящи обекти и т.н. – вариантите са много. Важното е ясно и удобно да се виждат местата, до които е възможно да се стигне и как те са обвързани с началната страница. Програмата трябва да има възможност за настройка на дълбочината на визуализацията (т.е. колко далеч от началната страница да се стига) и да има опция за работа в Интернет и извън нея (върху предварително изтеглени данни).

Обобщено, приложението трябва да поддържа:

  • Въвеждане на начална страница
  • Настройване на търсенето и генерирането
  • Генериране на визуализация
    • с възможност за навигация между визуализираните страници
  • Online и Offline режим на работа

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

Приложението може да бъде уеб, десктоп, както и WinRT-базирано. Единственото ограничение е да бъде изпълнимо под Windows 7 или Windows 8 и да бъде предоставен лесен начин за стартирането му в папката application.

Критерии за оценяване

Оценяване на алгоритмичната част

При оценяването ще бъдат генерирани тестове от журито, с различни начални и крайни страници, по описаните правила. Освен това, ще бъдат ползвани коректните тестове пратени от участниците. Тежестта ще бъде 50 на 50, тоест тестовете на журито ще носят общо толкова точки, колкото общо тестовете предадени от участниците.

  • Данните от всеки тест на журито, както и данните от всеки тест на участниците, ще бъдат подадени на всеки един предаден алгоритъм.
  • За всеки тест ще се намира най-добрия резултат на алгоритъм и той ще получи максималните точки за този тест, а останалите ще получат съответния процент от тези точки за този тест (т.е. скалирането се извършва за всеки тест).
  • Например, ако за задачата има 10 теста от които 5 са на състезатели и 5 на журито, то всеки ще носи по 1 точка.
    • Ако на първото поле най-добре представилият се алгоритъмът G е намерил път с дължина 10
    • алгоритъмът M е намерил път с дължина 15,
    • а алгоритъмът L е намерил път с дължина 30, то
    • в крайна сметка точките за този тест (закръглени до 2 цифра след десетичната запетая) са:
      • G: 1 точка
      • M: 0.67 точки = 1/(M/G) = 1/(15/10)
      • L: 0.33 точки = 1/(L/G) = 1/(30/10)
  • По същия начин се оценяват всички тестове, точките се сумират и след това се закръглят до цяло число
    • Ако след сумирането няма резултат 10 точки, се извършва скалиране на всички резултати (преди закръглянето), така че най-добре представилия се да получи 10 точки, а останалите – съответната част от тези точки, и след това се извършва закръгляне
  • Максимални точки в крайното класиране за алгоритмичната част: 10

Оценяване на приложната част

Оценяването на приложната задача ще се извърши по-следните критерии:

  • Коректност (доколко са имплементирани посочените функционалности) – 2 точки
  • Справяне с грешки (справяне с некоректно поведение и непредвидени ситуации) – 2 точки
  • Ползваемост (доколко е удобна и интуитивна е работата с приложението) – 2 точки
  • UI дизайн (доколко е приятно визуалното оформление на приложението) – 2 точки
  • Оригинални функции и решения, които да впечатлят журито – 2 точки
  • Максимални точки в крайното класиране за приложната част: 10

Допълнителни изисквания

Задачите позволяват използването на различни езици за програмиране и технологии (например C#, PHP, C, C++, Delphi, Python, WPF, Windows Forms, Java, Swing, Flash, JavaScript, HTML5). Всички предадени решения ще бъдат тествани в Windows 7 среда съгласно общите условия на конкурса.

За алгоритмичната част се изисква да бъде предаден пълен сорс код + изпълним файл за Windows (.exe). Ако програмирате на език, който по природа не създава изпълними .exe файлове (например PHP, Python, Java или JavaScript), използвайте подходящ компилатор (потърсете в Интернет).

За приложната част се изисква да бъде предаден пълен сорс код + изпълним файл. Състезателите имат право да изберат начина, по който тяхното приложение ще бъде стартирано, така че това да е удобно в Windows среда (приложението може също да бъде web-базирано и да се отваря през браузър). Тъй като оценяването на приложната част ще бъде извършвано и от гледната точка на потребител (а потребителите искат да стартират едно приложение възможно най-бързо и лесно), сериозни затруднения при намирането и стартирането на приложението могат да намалят присъдените от журито точки.

Характеристики на системата, върху която ще бъде проведено тестването

  • Intel® Xeon® CPU E31225 @ 3.10 GHz
  • 16 GB RAM
  • 128 MB Video Memory (dedicated) Intel® HD Graphics video card
  • Стандартна резолюция на тестващате машина: 1680×1050
    • Журито може да прецени да смени резолюцията при тестване на някои приложения
  • 232 GB HDD
  • Microsoft Windows 7 64-bit OS
    • за предалите приложна част на WinRT, тестването на приложната част ще бъде извършено на система с минимални характеристики OS Windows 8 64-bit, 6 GB RAM, Intel i7-720QM, 1GB ATI Mobility Radeon HD 4250.

Краен срок

Краен срок за предаване на решения: 7 април 2013 г, 23:59:59 часа.

Решенията се предават в студентската система на Академията на Телерик, на адрес http://telerikacademy.com/Courses/Courses/Details/13 според инструкциите, описани в раздела “Качи решение” на официалния сайт на състезанието.