Tkd2010

от Съзтезателно програмиране

Версия от 09:07, 29 ноември 2012 на Milo5 (Беседа | приноси)
(разл) ←По-стара версия | преглед на текущата версия (разл) | По-нова версия→ (разл)
Направо към: навигация, търсене

Съдържание

Идея

Wiki-Страница на турнира

Турнирът за купата на Декана се провежда ежегодно във ФМИ на СУ. Основна цел е да се поощри развитието младите студенти. Поради тази причина на 05.12.2010 г. ще се проведе поредното седмо издание на турнира. То ще има присъствена форма във ФМИ. Подробности, ще обявим скоро.

Актуално

  • Важно: Утре (05.12.2010):
    • участниците в присъствената форма трябва да бъдат най-късно в 8:40 във ФМИ (на третия етаж до компютърните зали)
    • участниците в online формата, трябва да бъдат на линия в 9:00 в http://judge.openfmi.net:9080/spoj0/
  • Благодарим на всички които се включиха в загрявката! Ако не сте загряли достатъчно, опитайте и задачите от миналогодишното издание на турнира. Ако пък не ви се решава, можете просто да прегледате кода на изпратените решения. --Milo 09:29, 29 ноември 2010 (UTC)
  • В Неделя, 28.11.2010, от 10:00 до 15:0013:00, ще се проведе online тренировка за турнира на купата на декана - виж #Загрявка

Регистрация

Всеки който желае да участва в присъствената или online форма на турнира, трябва да заяви желанието си с писмо до manev@fmi.uni-sofia.bg. Весеки желаещ да участва в загрявката, трябва да си регистрира потребител (ако вече няма) на http://judge.openfmi.net:9080/spoj0/. Имайте предвид, че регистрацията в spoj0 не отменя необходимостта от писмо.

Правила

Състезанието е индивидуално. Ще има определено добро количество задачи и 5 часа време за решаване. За всяка от задачите (или по-скоро за колкото можете повече) трябва да се напише програма която я решава.

Програмите трябва:

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

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

Присъствена форма

Присъственото състезание е индивидуално и се провежда по правила подобни на правилата от ACM състезания. В официалното класиране могат да участват студенти от ФМИ първи и втори курс. Ако имате въпроси и съмненя за това дали имате право на участие, използвайте беседата на тази страница.

Онлайн форма

Състезанието ще има и online версия, която ще се проведе по същото време. В нея може да участва всеки желаещ (а не само студенти на ФМИ).

Загрявка

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

  • То ще се проведе на spoj0 системата намираща се на http://judge.openfmi.net:9080/spoj0/
  • Ако нямате потребител в тази система, ще трябва да си регистрирате.
  • Задачите ще бъдат по-лесни отколкото на истинското състезание.
  • Времето ще бъде по-малко (3 часа), отколкото на истинското състезание (5 часа).
  • Самото състезание е предвидено за тренировка, неговите резултати няма да имат ниакакво значение за класирането на Турнира.
  • Ако имате въпроси или проблеми свързани със задачите, системата и др., може да пишете в беседата на тази страница (изисква да си регистрирате акаунт в това ўики) или на miloslav@gmail.com

Относно spoj0

Системата spoj0 е предназначена за автоматично оценяване за състезания по прогрмиране в ACM стил. Надяваме се, че е сравнително интуитивна, но ето най-основните неща в нея:

  • Тя е доста малка, и след кратко поразглеждане, би трябвало да се ориентирате какво къде има. Намерете къде е класирането на съответното състезание, статуса и условията (които ще можете да свалите след като състезанието започне).
  • След като си харесате задача от някое състезание и напишете решение (с любимата ви среда за разработване, не пишете направо във формата!), трябва да пейстнете вашият сорс кодът в submit формата. Има някои особености за това:
    • Не използвайте browse, а пействайте във формата, тъй като browse бутонът не работи добре при някои (доста) браузъри.
    • Проверете, че вашият код прави точно това което се иска и нищо друго спрямо вход/изход (т.е. не чете/пише файлове, не чете/пише допълнителни/недостатъчни неща)
  • Ако пишете на Java, имайте предвид че:
    • трябва да пейстнете точно един главен клас, който да е в default пакета (т.е. без пакет) и да се казва program (да, с малки букви)
    • би тряввало да няма проблем да при вложени класове, или други не-публични класове в същия код
    • вашият код ще се компилира и изпълнява с JDK 1.6.0
  • Ако пишете на C или C++ имайте предвид
    • няма отделни настройки за чисто C - ако пишете на чисто C, внимавайте кодът ви да е съвместим със C++.
    • кодът ви ще се компилира с g++ 4.3.2 и в 32-битова система.
  • След изпращане, можете да видите какво се получава от status страницата. Ето някои статуси:
    • ok - честито, решението ви е вярно
    • wa - решението ви вади грешен отговор
    • tl/tl1 - решението ви не завършва за времето което е определено за задачата
    • re - решението ви прекъсва с грешка по време на работа (т.е. гърми)
    • pe - решението ви вади резултат, който изглежда верен, но не е форматиран правилно (спрямо интервали, нови редове и т.н.)
    • ce - грешка при компилиране: обикновено е следствие на различия на компилаторите. Можете да видите каква е грешката в статуса на изпълнението.
  • Наблюдавайте класирането, ориентирайте се по него за трудността на задачите.

Резултати

Връчване на купата на Иван Георгиев


Победители в това издание на турнира станаха Иван Георгиев (победител в присъственото състезание и носител на Купата на Декана) и Румен Христов (победител в Online състезанието и безспорен победител в смесеното класиране за online и onsite). Иван е втори курс, специалност Компютърни Науки, докато Румен е ученик в 11ти клас, в Шуменската Математическа Гимназия. Честито на победителите!

На второ и трето място в присъстевеното състезание се класираха Стефан Аврамов и Красимир Георгиев. Забележете, че и миналата година Стеф съвсем замалко се размина с титлата (като беше победен само за 2 минути!).

На второ и трето място в online състезанието пък се класираха Антон Анастасов и Веселин Георгиев. Антон беше победител в миналогодишното издание на online състезанието, докато Веско е носител на Купата от 2005-та година.


Ето и пълното класиране: http://judge.openfmi.net:9080/spoj0/board.pl?contest_id=92

Rank Name Solved Timea-wordb-intersectionc-matrixd-legacye-dicef-fuelg-adamsh-knightsi-ribbonsj-strengthAttempts
1Rumen Hristov (147)105956 (0)14 (0)30 (0)42 (0)126 (1)50 (0)97 (3)24 (0)87 (0)36 (0)14
2Anton Anastasov (142)95911 (0)9 (0)23 (0)32 (0)239 (0)60 (0)0 (11)45 (0)80 (0)98 (0)20
3Иван Георгиев (517)9104411 (0)34 (0)49 (0)62 (0)299 (2)202 (0)0 ()142 (1)100 (0)81 (0)12
4Veselin Georgiev (984)9123361 (0)65 (0)138 (0)101 (0)216 (0)86 (1)294 (0)0 (3)120 (0)126 (0)13
5Yordan Chaparov (970)89658 (1)17 (0)148 (1)46 (3)248 (1)161 (1)0 (1)0 (6)121 (0)72 (0)22
6Stefan Avramov (999)8105734 (2)22 (2)50 (0)93 (0)0 ()109 (0)0 ()195 (2)138 (1)212 (3)18
7Ясен Трифонов (349)8107425 (0)33 (0)128 (1)157 (0)293 (0)189 (2)0 ()0 ()117 (0)68 (0)11
8Krasimir Georgiev (960)68769 (0)16 (0)146 (1)135 (0)0 (6)259 (0)0 ()0 ()0 ()289 (0)13
9Камен Донев (1009)61498217 (0)228 (1)0 (1)0 ()0 ()237 (1)0 ()262 (0)249 (0)243 (1)10
10Simeon Ivanov (998)545523 (0)56 (0)0 ()0 ()0 ()105 (0)0 ()0 (2)193 (0)76 (0)7
11Даниел Балчев (947)56799 (0)34 (0)0 (1)78 (0)0 ()0 (2)0 ()0 ()238 (1)298 (0)9
12Никола Таушанов (143)56866 (0)29 (0)0 (1)0 ()0 (4)245 (0)0 ()0 (1)197 (0)206 (0)11
13Мария Железова (210)569614 (0)100 (0)0 ()215 (1)0 ()0 ()0 ()0 ()289 (0)56 (0)6
14Николай Хубанов (949)44198 (0)27 (0)0 ()0 ()0 (1)275 (1)0 ()0 (3)0 (3)88 (0)12
15Ваня Данчева (212)446411 (0)0 (2)0 ()0 ()0 ()106 (1)0 ()0 ()199 (0)126 (0)7
16Rumen Paletov (755)467519 (1)185 (0)0 ()0 ()0 ()0 (4)0 ()0 ()251 (4)119 (0)13
17Ivaylo Dankolov (938)48269 (0)261 (4)0 (3)310 (0)0 ()0 ()0 (5)0 ()0 ()165 (0)16
18borislav valkov (948)331870 (2)94 (0)0 ()0 (7)0 ()0 ()0 ()0 ()0 ()114 (0)12
19sv and (119)3364172 (0)27 (1)0 ()0 ()0 ()0 ()0 ()0 ()0 ()144 (0)4
20Dobrin Paskov (946)3769256 (2)126 (3)0 ()0 (1)0 ()0 ()0 ()0 ()0 ()246 (2)11
21Mihail Karev (950)21288 (0)0 (1)0 (4)0 (3)0 ()0 ()0 ()0 ()0 ()120 (0)10
22Nikolai Petrov (993)220826 (0)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()181 (0)2
23Georgiev (991)221313 (0)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()199 (0)2
24Михаил Джурев (961)222368 (0)94 (3)0 ()0 (6)0 ()0 ()0 ()0 ()0 ()0 ()11
25Vladimir Vladimirov (979)224134 (0)127 (4)0 ()0 ()0 ()0 (4)0 ()0 (2)0 ()0 ()12
26Георги Гъмзаков (953)227776 (0)0 (2)0 ()0 ()0 ()0 ()0 ()0 (2)0 ()200 (0)6
27Anton Chernev (1002)2397145 (0)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()232 (1)3
28Калоян Йовчев (794)2439191 (2)207 (0)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()4
29Valentin Borisov (1005)2468165 (3)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()243 (0)5
30Недко Савов (1007)2512183 (2)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()288 (0)4
31Eli Hristova (994)2573167 (6)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()246 (2)10
32Velislav Nikolov (985)1910 ()91 (0)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()1
33Ivan Nikolov (945)1930 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()93 (0)1
34Konstantin Minev (997)1116116 (0)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()1
35Plamen iliev (1006)1165165 (0)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()1
36Iliqn Iliev (1004)1212212 (0)0 ()0 ()0 ()0 (1)0 ()0 ()0 ()0 ()0 ()2
37Alex Ivanov (1001)1215195 (1)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()2
38Marin Shalamanov (990)12270 ()0 (1)0 ()0 ()0 ()0 ()0 ()0 (2)0 ()227 (0)4
39Добрик Георгиев (1000)14580 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()258 (10)11
40Plamen Dimitrov (944)00 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 (10)10
41Nikola Gumzakov (981)00 ()0 (5)0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()5
42Krasimir Petrov (995)00 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 ()0 (6)6
43TODOR BONCHEV (935)00 (4)0 ()0 ()0 (1)0 ()0 ()0 ()0 ()0 ()0 ()5
44Daniel Tsvetilov (975)00 (1)0 ()0 (2)0 ()0 ()0 ()0 ()0 ()0 ()0 (1)4

Коментар по Състезанието

Временно класиране към 20-та минута :: Състезанието започна сравнително гладко, като повечето участници се нахвърлиха върху първа задача, която беше предвидена като една от най-лесните (всъщност задача J. Strength може би беше дори малко по-лесна). Впечатление правят много бързите времена на Антон Анастасов по първа задача и Краси Георгиев по втора.

Временно класиране към 45-та минута :: Четиридесет и пет минути след началото на състезанието, Румен вече има ШЕСТ задачи, като до сега няма грешен submit. Анастасов също няма грешен събмит, но има само 4 accept-нати задачи. Сред останалите състезатели се наблюдават нови хора с поне една задача и значителен брой участници с две. Малко учудващо за мен, доста хора загубиха много време на втора задача (да се пресекат две отсечки), предимно защото повечето писаха константния алгоритъм за това. Вместо това можеха просто за всеки тест да итерират по ВСЕКИ x и ВСЕКИ y и да проверят дали текущата точка лежи и на двете отсечки. Това е значително по-лесно и по-бързо за писане, като за всеки тест се проверяват по около 4 милиона точки - достатъчно малък брой за да върви. Друго интересно нещо в текущото класиране е, че Румен реши задачата H. Knights (една от най-трудните в дадения set) като 3-та задача и му трябваха едва 10 минути за това! Съдейки по кода му не е ползвал пренаписан код, което е трудно постижимо само откъм скорост на писане (пробвайте, след като сте решили задачата, само да направите графа и да напишете matching... на мен ми отне повече време дори без да чета условието на задачата).

Временно класиране към 60-та минута :: Петнадесет минути по-късно Румен се е справил с още една задача, а Анастасов с още 2 (и двамата продължават да са без грешен събмит). Мимс Железова е първият човек от присъственото състезание, който откри колко лесна всъщност е задача J. Иван излиза начело в присъственото състезание, с много бърз submit по задача C, като до сега също е предал всички задачи от пръв път.

Временно класиране към 90-та минута :: Час и половина след началото на състезанието Румен се е справил с поредната задача, имайки вече 8 accept-нати задачи. На второ място само на задача след него е Анастасов, а с 5 задачи е и първият от присъственото състезание Иван Георгиев. И тримата до сега нямат грешен submit! Страхотно постижение! За половин час още 5 човека осъзнаха, че задача J e много много лесна и я предадоха без особени затруднения. Вече се виждат и първите събмити на хората, които си мислеха, че състезанието започва в 10 часа, а не в 9, като най-значителните от тях са Веселин Георгиев, който вече има 3 задачи и Ясен Трифонов, който първите 15-20 минути нямаше интернет :). Виждаме люта борба за второто място на присъственото състезание, водена между Даниел Белчев, Ники Хубанов и Стефан Аврамов. Въпреки доста добрия си старт, Краси Георгиев все още не е предал 3-та задача, което го оставя за сега назад в класирането.

Временно класиране към 100-тна минута :: Десет минути по-късно Румен повежда с 9 задачи (срещу 7 на Анастасов), но една минута по-късно вторият предава още една задача и разликата отново става само 1 задача. Джо решава 6-тата си задача, продължавайки поредицата си от безпогрешни събмити. Антон също е без грешка, но Румен прекъсва серията си с цели 3 неуспешни по най-сложната задача в темата (задача G. Adams). Интересен е и първият му неуспешен събмит:

46293 Rumen Hristov(147) tkd2010(92) g-adams (441) 2010-12-05 10:26:42 cpp the first wa? wa view

От останалите състезатели в присъственото състезание, Стефан Аврамов решава четвърта задача и става втори в борещите се за купата. Интересно е, че още не е предал най-лесната задача в състезанието!

Временно класиране към 130-та минута :: Малко над два часа след началото на състезанието, вече имаме победител - Румен Христов, който успя за това време да реши ДЕСЕТТЕ задачи, които бяхме предвидили. В този момент, дори вторият в класирането да предаде 2-те му оставащи задачи без грешен събмит, отново би бил след Румен по време. В топ 5 сериозни промени няма, освен появяването на Веселин Георгиев на 4-то място. Въпреки, че започна с 60 минути закъснение, завидните му времена по задачите (около минута на първа, колкото имаше и Анастасов, и 4 минути на 2ра, което е и най-доброто време за цялото състезание) го изпратиха напред в класирането. Ясен Трифонов наваксва със задачите, въпреки също закъснялото си начало. Иван Георгиев все още е с 6 задачи, като в момента пише matching-а по H. На 11-то и 12-то място виждаме единствените две представителки на нежния пол, които участваха в присъственото състезание - Ваня Данчева и Мария Железова. Интересното тук е, че Ваня вече беше предала задача F. Fuel, която победителят в присъственото състезание предава след повече от час. Краси Георгиев ВСЕ ОЩЕ е с две задачи. Стеф вече е с 5, като приближава по задачи лидерът в присъственото състезание, но не и по време. С 5 задачи той има по-лошо време от Джо с 6.

Временно класиране към 150-та минута :: Двадесет минути по-късно промени в класирането в топ 8 няма, с тази разлика, че хората на 3то, 4то, 5то и 6то място предават по още една задача. Задачата C. Matrix отнема на Веселин Георгиев едва 13 минути, най-бързо време единствено след почти невъзможните 6 минути на Румен. Държа да отбележа, че "измерването" на тези времена е малко субективно, тъй като между задачите някои от състезателите четат други условия, ядат и т.н. На девето място се появява Краси Георгиев, предавайки 2 задачи през последните 20 минути. На пето място е Йордан Чапъров, който спечели есенния турнир по програмиране в Шумен миналата седмица, побеждавайки представителите на националния ни отбор от миналата година Румен и Влади Харалампиев.

Временно класиране към 180-та минута :: В края на третия час от състезанието Йордан Чапъров предава своята 7-ма задача и изпреварва човека пред себе си по време. Ясен предава още една задача и започва да бори упорито задача F. Fuel. Binary search-ът, който се изискваше в нея явно успя да затрудни дори няколко от по-опитните състезатели, тъй като това е и задачата, която Иван Георгиев пишеше в момента, имплементирайки двумерното динамично за нея. Което е странно, тъй като задачата беше предвидена като една от лесните в темата.

Временно класиране към 210-та минута :: Още половин час по-късно Анастасов все още не е предал 9-та задача, като очевидно временно се отказа от G. Adams и премина на другия граф в темата - BFS-то Е. Dice. Иван най-накрая предаде F, като тя му отне точно около час (а е направима за 10-тина минути (8, в случая на Румен)). Симеон Иванов, Ясен Трифонов и Стефан Аврамов предават по още една задача, като Ясен също преборва F, Симеон се справя с динамичното I, а Стеф - с потока H. Ваня е първото момиче с 4 задачи днес!

Временно класиране към 230-та минута :: Веселин Георгиев и Стефан Аврамов предават по още една задача, ставайки съответно 3-ти и 4-ти човек с по 8 задачи. Интересен факт - въпреки, че почна с 1 час закъснение, Веско е ПРЕДИ Аварамов по време (тоест смятайте 8 * 60 минути допълнително наказателно време). Браво Стеф! 3 грешни събмита на най-лесната задача, 2 на втората най-лесна и 2 на третата най-лесна. Краси е все още с 4 задачи, като вече и двете мацки (Ваня и Мими) станаха също с толкова.

Временно класиране към 240-та минута :: Десет минути по-късно се включваме отново за да отбележем 9-тата задача на Анастасов, откъсвайки се от групата с по 8 задачи. Тя също му е приета от първи път, което го прави единственият състезател с 9 последователни задачи, предадени от първи път на това състезание. За сметка на това вече има 5 неуспешни събмита по Adams, тоест практически невъзможно да има общо по-малко от Румен за всички задачи. Следващата промяна е чак на 10-то място, където Даниел Белчев измества Мария Железова с малко по-добри времена на първа и втора задача.

Временно класиране към 300-та минута :: Час по-късно, близо до очаквания край на състезанието, вече не беше ясно какво точно се случва, тъй като сървърът се претовари от многото събмити и кликания на "Refresh" на класирането. В този един час Веселин Георгиев беше единственият друг участник (освен Румен), който реши графът на Боби (тоест задачата Adams), но пък не беше срещал задачата Knights (която, както се оказа, е сравнително известна). С това решение той се изкачи на 3-то място, изпреварвайки (временно) Иван Георгиев по задачи. Пет минути по-късно, обаче, след два неуспешни събмита, Джо успя да предаде BFS-то и си върна третото място (главно заради много лошото време на Веско в следствие на късния му старт). Ели Христова, третата дама, участваща в състезанието (но тя в неговата online версия), успява да предаде своята 2ра задача. Йордан и Ясен също успяват да предадат BFS-то (Ясен от първи път), като така задачите им стават осем на брой. Мимс също се справя с още една задача, като така става с 5 на брой и печели "женската" титла (ако имаше такава). Краси Георгиев предава още 2 задачи (той явно така си може - на групи по две), като така става с 6 задачи и се изкачва с още едно място нагоре. Освен Румен, от текущите ученици най-добре се справиха Йордан Чапъров, Ясен Трифонов и Симеон Иванов, съответно на 5-то, 7-мо и 10-то място.

В добавените 15 минути поради падането на сървъра не се случи почти нищо друго, тъй като през повечето време той беше недостъпен за submit. Все пак участниците имаха няколко минути, в които да предадат своите последни решения, които не повлияха на класирането в топ 10.

Екип

Състезанието се осъществява благодарение на следните хора:

  • Доц. д-р Красимир Манев
  • Александър Георгиев
  • Борис Странджев
  • Ивайло Странджев
  • Милослав Средков
  • Петър Армянов

Специални Благодарности

Също така специални благодарности към Мимс, която спаси 17/19 от хората на присъственото състезание, като отвори прозореца около 3-тия час от състезанието.

Лични инструменти