The legend of Georgian ACM movement

The acronym "ACM" stands for the Association for Computing Machinery, which conducts the annual ACM International Collegiate Programming Contest, or simply ACM ICPC. This competition is widely recognized as the world championship, and its rules, possibly with mild alterations, are often used in other programming contests.

In general, the ACM rules suggest the following. The teams composed of one to three persons are provided with a set of mathematically-oriented problems and should code the solutions in one of the available languages. Upon writing the code, a team sends it to the server for evaluation on a set of testcases. Now, if the solution outputs the right answers in the time allotted and does not misperform in any way, the problem is marked as solved. Otherwise, the submission is rejected. Finally, the teams are ranked by the number of solved problems and by "penalty time" in case of ties, the latter depending on the number of wrong tries and solving time for each solved problem.

The contests which use the ACM rules are often referred to as ACM-style contests, and since they comprise the majority of the contests around, our whole activity can be called "The ACM movement".

I'm not sure about the exact birthdate of Georgian ACM movement but it's possibly around year 1999, when Tbilisi State University team participated in NEERC (the ACM ICPC semifinals region where Georgian teams participate) for the first time. For the next four years, the results have been stable but middling. The breakthrough came in 2004, when the TSU team, comprised of Nika Jimsheleishvili, Irakli Khomeriki and Revaz Khurtsilava, was just a problem away from the finals. Nika soon became the leader amongst domestic participants and his team fought every year to advance to the Finals. After a couple of line-up changes, the team Triumvirate with Nika, Giorgi Lekveishvili and me finally made it in 2008/2009 season.

You probably recognize all the names in the previous paragraph. There are several other people also worth mentioning when speaking about Georgian ACM movement, but this time I'd like to focus on one person instead. The person from whom I learned a lot in my olympic youth. The person who brought a lot into Georgian olympiads but never got the deserved credits. So, may I introduce the concealed legend of Georgian ACM movement - Davit Rachvelishvili aka rachvela.


I'll recall some of Davit's accomplishments, just to show you the whole picture. First of all, Davit was the first Georgian competitor on Topcoder and it was him who familiarized the rest of us with this truly helpful community. One can hardly overestimate the bonuses of Topcoder, including editorials and regular SRMs (which were far more regular in those distant times).
Davit also was the first of us to discover some algorithmic concepts which are extensively used in the contests nowadays - for instance, minimum cost maximum flow and fenwick trees.
Moreover, Davit was always willing to share his knowledge and help the fellow colleagues. Davit's easy temper and spiteless attitude were the perfect qualities for this. Sounds like an extract from a reference letter? Yep, but still maximally close to the truth ;)

Now let me tell about rachvela's way.

Chapter 1. The early years.
One might think that succeeding in programming, especially at the olympiads, is impossible without serious math and computer background from the very childhood. Now I'm telling you it's possible, since I have an example right before my eyes.
Davit never studied in a math-oriented school. He didn't bother studying at the normal one, either. Instead, he spent his adolescence breakdancing and hip-hopping (if you got the impression that he never went to school, that's false, he formally did). He still raps his self-written song from time to time, but his breaking will never be the same :D


Chapter 2. Engaging into olympiads.
When I was in eleventh grade, which was the final year in Georgian schools back in those times, I've set myself an objective of making it to the Georgian IOI team that year. So I worked hard and tried to participate in every contest that I found out about. UVA online judge hosted plenty of contests and I competed in the most of them. That was where I first encountered Davit. Soon, we also met at forum.ge and communicated this way for a long time. Davit was a freshman at Tbilisi State University and studied programming as diligently as me.

Now it's time for you to ask, hey, how did the break-boy leave the streets and find the aspiration for programming? Well, my friends, I doubt that there was any magic involved. Davit just grew up and found the occupation that was profitable, perspective and - the last but not the least - the occupation he liked. And once he found it, he did not stand back because of lack of knowledge or anything - he believed he's capable and he was going for it.


By the time when I joined TSU in 2005 (after failing the IOI team selection contests), Davit already was the leader of the university's second team. I also got on this team in early 2006 and we have competed together for several months, but had to break up before the start of the new season, since Davit went to the first team alongside Nika Jimsheleishvili and Giorgi Lekveishvili.

Chapter 3. The years of fame.
The first olympiad in which the new-formed first team took part was the All-Ukrainian Open Olympiad in Vinnytsia. This trip brought them the bronze medals of Ukrainian championship.

The next, and main, competition was NEERC 2006. We all pinned high hopes on the first team and believed it would advance to the Finals this time. Unfortunately, due to a malfunction of their machine (which was not properly compensated by the judges!) they lost a significant amount of time (and determination, I guess) and eventually finished 15 places behind the advancers.


The same team earned the first degree diplomas at the first Vekua Cup in April 2007. Davit was also granted the third degree diploma in the individual competition.

The last event where this team participated was KPI Open. The site stubbornly doesn't show the results for years before 2008, so I have to rely on my poor memory, which tells me that the boys took the third place then.


Since Nika had decided to skip the 2007/2008 ACM season, the teams reorganized again. Davit and Giorgi resurrected Irakli Khomeriki and began another advance-to-finals campaign. It was Davit's final year in baccalaureate and he wasn't going to pursue the Masters right away, so it was also his last chance to participate in ACM (because there also is a restriction on age and he would outgrow it). The team prepared thoroughly and was highly determined. However, eventually it all went completely wrong. Some really lame mistakes kept the first team well under the advancers zone. For Davit, the ACM Finals would remain a distant dream.

After the described events Davit quit programming contests, graduated from the university and fully concentrated on the job. We rarely heard of him in the course of the year and everybody, including him I think, thought his olympic career was over...

Chapter 4. The return of the Jedi.
...but we all were wrong. After having a year-long break, Davit entered The Georgian University of Saint Andrew the First-Called and, maybe inspired by Triumvirate finally advancing to the Finals and earning the Bronze medals, maybe just following the calling inside him, returned to the world of olympiads with all the diligence he had before.

The fortune did not turn its back on Davit, and he was granted permission to participate in ACM ICPC for one last season (the rules concerning the age were softened). His teammates were Avto Rukhadze, quite an experienced contestant, and Tornike Benidze, a debutant in ACM competitions. Hoping to advance to the Finals from NEERC in this situation would be barefaced impudence (those of you who ever took part in NEERC should understand). So the real fight was for the title of Champion of Georgia.

There were at least two teams from Tbilisi State University which were ought to beat Davit's in the domestic run - Tbilisi SU1 with ACM ICPC and IOI bronze medalist Giorgi Lekveishvili and IOI medalists Giorgi Nadiradze and Davit Tvalchrelidze, and Tbilisi SU2 composed of Giorgi Saghinadze, Andrew Lutsenko and Akaki Mamageishvili - this was their third successive season as a team, and they were quite serried.

But Davit managed to surprise us all. In a difficult contest, he managed to get the team on the top of Georgian teams ranklist, thereby finishing his ACM ICPC performances with the domestic Champion title and the head held high. An interesting thing is that both TSU teams named above lost to Tbilisi SU3 comprised of first-year students Zurab Kutsia, Nika Gabisonia and Beka Barbakadze. It's nice that the youth still keeps coming :)

Chapter 5. Epilogue.
So, I told you the story of Davit Rachvelishvili, one of the key figures in Georgian ACM movement evolution. You might ask me, what is he doing now?

Davit works as developer at JSC Georgian Card, where he performs stuff of all different sorts. He keeps claiming that Java is not an inch slower than C++, loves the Twilight Saga and still does not listen to metal.

Recently, Davit married his beloved Teo. You can look at the picture of the happy couple :)


And finally, even though ACM ICPC is definitely in the past, there are many other contests worth winning. And Davit knows that :) He still battles on Topcoder and is going to kick some asses at the next Google Code Jam. Moreover, Davit, Giorgi Lekveishvili and me are going to participate in Challenge 24 as Narwhals. Should be fun :)

SRM 459

It's been almost a year since my first and almost half a year since my last SRM, and I felt like making another one. So somewhen before the New Year I processed the ideas whirling in my head, wrote several problems and was offered the 459-th Single Round Match.

Div2 Easy - RecursiveFigures. The problem featured some eighth-grade level geometry, which, even with all the formulas in the statement, appeared to be not too easy (I guess there is nothing too easy for D2-250). The most interesting thing about it are the pictures by Lela Latsoshvili, who will be saving all of you from my mspaint-made illustrations from now on (I hope :D).

Div2 Medium / Div1 Easy - Inequalities. This problem can be solved in a number of ways, the most general of which has performance complexity of O(NlogN), where N is the number of inequalities, and can even produce the whole optimal intervals of values. However, since this is D1-Easy, the common solution to seek for is some neat brute force. With constraints as low as 1000, one could iterate over all possible values from -1 to 1001 with step 0.5 and check the answer for each of them - which is quite easy if you parse the input properly.

Div2 Hard - ParkAmusement. At first, the problem was deemed as too hard for Division 2, since it involved conditional probability - quite an uncommon topic for the second division. Even after the addition of thorough annotations, the tester still suggested to remove the conditional probability part - but I believed in Division 2, and Division 2 did not let me down. 24 successful submissions even made this my easiest D2-Hard yet. Not that I complain about it :) The key idea of the solution is that the probability of landing X being the starting landing is the ratio of (the probability of reaching an exit from X in K pipes) and (the probability of reaching an exit from any landing i in K pipes). Computing this probabilities is performed with dynamic programming, where the state is pair(landing, pipes left).

Div1 Medium - NumberPyramids. So, we have another problem featuring Lela's illustrations in place of my crooked landscapes. Though this time the problem itself can at least compete with its corresponding pictures. I was a little surprised with the high number of successful submissions for this problem, since its solution took me more efforts than, say, the SRM443's BinaryFlips. When I am not as sleepy as now at 3:30AM, I'll put the idea of the solution here.

Div1 Hard - TheContest. Actually, at first I proposed another problem for this slot. However, it finally turned out to be way too hard, so I have modified my easiest problem from Vekua Cup Individual Contest's problemset - problem G, and suggested to use it. Unfortunately, eventually nobody solved it (though we were a lot more optimistic before the match).
The solution for the problem is as follows. First, let us consider N<=M. It's provable that if we have several rows already filled, then we always can fill the rest in spite of exactly how we've filled the previous rows. Therefore, the problem reduces to filling a row in a way not to conflict with already filled rows. For each position, let us try every number (which was not used in this column before) in ascending order. If it is possible to arrange the rest of the numbers in the columns to the right, then we take this number. And this possibility can be checked with the help of matching techniques: if we build a bipartite graph with the left-side nodes corresponding to columns and right-sides corresponding to numbers left, and the edge between left-side i and right-side j denoting that j was not used in i-th column, there must exist a maximum matching in this graph for the number to be feasible.
When N>M, we encounter a little problem. It is no longer true that we can fill the rows not thinking about the next ones. For example, for N=3 and M=2, filling the rows in this manner will give us {"12","21"} and the third row will be no longer fillable. It's easy to notice that every value must be used in the whole matrix a total of MIN(N,M)=M times. Therefore, an obvious restriction on the numbers to use is: if there is a number X such that if you don't use it in this row, then you won't have enough rows to use it a total of M times, you should use X in this row. A much less obvious thing is that this is also sufficient to fill the whole matrix row-by-row. So, for each row we should first identify all the values which have to be used in it and then fill this row, making sure that these values are used. But how to deal with this in the matchings we use to determine feasibility? Since augmenting paths in matchings never change the nodes matched (just edges), it's enough to perform all the augmentations for those must-use values and then match the rest of the columns to some of the values.
So, this is it. I still believe the targets just had a bad day, or the problem wouldn't stay virgin.

Alright, here is the round overview and that's all for now.

The red-colored New Year

So, the year 2009 is over. First of all, let me wish you all a happy and successful year 2010.

The previous year saw by far the greatest results of Georgian programming olympiads movement in whole and me in particular, the quintessence of which were the Bronze Medals at ACM ICPC 2009. But let me recollect them all in chronological order.

So, January began with two Topcoder SRMs prepared by Georgian writers - first of them by nika and the second by my very self. These were the first (at least as far as I know) international-level competitions with problemsets written by Georgians.

Our problemsetting experiment continued soon after at Winter Programming School in Kharkiv in February. The sixth day of the School was fully prepared by our team Tbilisi SU Triumvirate (Bogdanov, Jimsheleishvili, Lekveishvili) and its coach Temuri Zarkua. Also, we finished second in the overall raiting of the School.

Then, April came and we went to Stockholm in our quest for Georgia's first medals at ACM ICPC Finals. And the debut was really successful :)


Soon after the Finals, George also conducted his first SRM, and I had another two (440, 443).

Well, what else was there? In the end of June, George and me took the third place at KPI Open 2009. In September, I wrote the problemset for Vekua Cup 2009 Individual Competition. In November, Eduard and me took the second place at Open South Caucasian Championship 2009, the team Tbilisi SANGU 1 (Benidze, Rachvelishvili, Rukhadze) won the title of Champion of Georgia for the first time, and Nika took the sixth place at Google Code Jam Finals.

And now, for those of you who think 'What the hell is that red thing in the title', let's get to the final part of this post and my olympic year - my Topcoder rating. I firmly announced somewhen in Autumn that I would meet the New Year with red color at Topcoder, which means getting one's rating over 2200. I changed my handle from eyler to gojira_tc (simply gojira was already taken :|) and kept repeating that the new handle would only look good in red color. In the meanwhile, my rating graph kept falling and climbing, and finally December came with me still hanging close to the cherished line. I took the 11th place at the next-to-last SRM of the year and came closer to red than ever and was looking forward to the last SRM.

The last match of the year was on 6:00AM by Georgian time. Moreover, I had been celebrating the coming holidays on the evening of the previous day. So nothing really assumed that I would manage to keep my word, but still I decided to try. After performing decently in the coding phase, I was around the 50th place, which would guarantee a sufficient rating increase. However, I've made a couple of successful challenges, and looking at the division summary again, was utterly surpirsed, seeing my handle at the 5th place. The thing that surprised me even more was my score - 666 points. I decided to stop any challenge activity and keep the score. I found a code which was failing - at least I was sure I had the proper testcase. But I forced myself to leave it alone. After the testing, my position changed to #3, making it my best performance ever and giving me an unconditional red color. I saw that the code I thought was wrong actually passed the system test, which means I would spoil my great result if I tried to challenge it. Therefore, 666 points saved me.

So, now you can see my red-colored handle and complacent mug. As for me, I am going to take my friends to khinkali as a tribute to the forces which assisted me with their 666 points.

KPI Open 2009

Как известно, международная открытая студенческая олимпиада по программированию им. С.А. Лебедева и В.М. Глушкова, или попросту KPI Open, - это мероприятие с наибольшим в Украине бюджетом среди всех олимпиадных баталий. С сожалением должен признать, что оно в то же время славится и как самое курьозное. В прошлые годы туры не обходились как без технических проблем, так и без ошибок в тестах или проверяющих программах. Тем не менее, эти факторы не становились решающими, и победители определялись более или менее справедливо.

Вот на эту самую олимпиаду нам и предстояло отправиться. Под "нами" подразумевается тренер Темури Заркуа и две команды по два человека: Tbilisi SU 1 в составе Леквы и меня, и Tbilisi SU 2 - в составе Гиоргия Сагинадзе и Акаки Мамагеишвили.

Прилетели мы за день до регистрации. Как обычно, Киев радует глаз в первую очередь обилием полураздетых красавиц, что сразу поднимает настроение. Настроение взлетело ещё выше, когда мои опасения не оправдались и вместо общежития с туалетом в другом конце коридора и душем на этаж ниже, мы оказались в профилактории, где все вышеупомянутые прелести жизни находятся в номере. Не меняя темы, мы собрались и ушли на пляж. В Киеве мы уже бывали, но почему-то на берег Днепра никогда не выходили. Чтож, всё бывает в первый раз © Ёлка

На пляже радости наших глаз уже не было предела. Воодушевлённый увиденным, Акаки, который по-русски говорит почти как я на китайском, решил выучить пару фраз и, естественно, обратился ко мне. Недолго думая, я предложил ему знакомиться с девушками фразой "Здравствуйте. Как к Вам можно обращаться?". Ну это шутка такая была. Но Акаки моего юмора не оценил и вот так и ходил по пляжу и обращался. Успешно по ходу :)


Второй день начался с регистрации команд. За что я люблю украинские олимпиады - регистрацию проводили главным образом девушки, которые ничем не уступали представительницам прекрасного пола, виденным нами снаружи KPI.



Далее в программе следовало само соревнование. KPI Open проводится в два тура: первый, отборочный, состоит из 4 задач на 4 часа. На втором, основном, предлагается 6 задач и 6 часов на их решение. Рейтинговая система на этой олимпиаде уникальная и совмещает в себе ACM, topcoder и школьные олимпиады. Спросить меня, так ничего в подобной смеси хорошего нет, но на вкус и цвет... Так или иначе, за решение по каждой задаче команда награждается неким количеством очков в зависимости от "веса" этой задачи, заранее определяемого компетентной командой судей, времени, потраченного на её решение и количества пройденных тестов.

В первом туре олимпиады разыгрывается сравнительно небольшое количество очков, поэтому написать его не очень хорошо совсем не значило потерять шансы на чемпионскую гонку. Многие сильные команды вообще пришли на него в неполном составе, надеясь бросить все силы в бой в основном раунде. Как выяснилось впоследствие, зря.

Так вот, первый тур. Самую лёгкую задачу, а вернее - задачу с наименьшим весом, на которую отводили 15 минут, никто не успел сдать даже за 20. Зато с той, которая была оценена в 45 минут, много команд расправилось быстрее, чем за десять. Ну это-то ладно, главное, что, как выразился позднее кто-то на закрытии, "задачи каждый год новые и оригинальные". На эти задачи вы сможете посмотреть, если их когда-нибудь выложат на сайте олимпиады. А до тех пор можете взглянуть на две задачи, похожие на предложенные на туре как две капли воды: Decoding Task и Amusing Numbers. По какому-то чудовищному совпадению, организационный комитет KPI умудрился не только заново изобрести такие же задачи, но и повторить текст условия слово в слово на разных языках. А если всё же преположить - чисто гипотетически [© "Enemy of the State"] - что это именно те задачи, то особо весёлым может показаться пункт в правилах по поводу подачи аппеляций: "Поводом для подачи аппеляции может быть неточность перевода условий задач на русский и английский языки".

Во втором раунде невероятных совпадений уже не наблюдалось, а может, их просто не успели заметить, потому что примерно на 100-ой минуте соревнования произошел невероятный сбой сервера. В течение трех часов производились не особо успешные попытки его реанимировать. В это время участники олимпиады из нашей комнаты (Леква и я в первую очередь) успели нарушить практически все правила олимпиады: звонили, слушали музыку, спали на приставленных друг к другу стульях, выходили наружу. Все команды пообщались между собой и с заглядывавшими иногда тренерами. Когда мы собрались пойти за пивом, в класс зашел дядька из оргкомитета и с прискорбным видом объявил трагическую весть: организаторами было принято решение о прекращении тура. После этого в течение пары часов тренерами и представителями оргкомитета обсуждались возможные варианты развития событий, и в итоге было решено аннулировать результаты неоконченного второго тура и объявить победителей на основе первого. Не знаю, лучшее ли это было решение, но в создавшейся ситуации вообще не видно было нормального выхода. Так что вот так выглядят окончательные результаты.


Что касается культурной программы олимпиады, один день был выделен на прогулку по Днепру на катере и экскурсию по городу. Также каждый вечер в профилактории проводили так называемые трейнинги, а по сути игры. Ребята делились на команды и соревновались в предложенных конкурсах. Однажды нам раздали журналы и предложили сделать плакат из вырезок, на котором была бы отражена жизнь программиста в нашем понимании. В итоге участвовало шесть команд, каждая с довольно своеобразным видением данного явления.



Ну что ж, а потом мы улетели домой, но обещали обязательно вернуться :)

SRM 443

Примерно в начале апреля был объявлен конкурс на составление задач для onsite-раунда TCO 2009 - ежегодного чемпионата, проводимого топкодером. Вплоть до начала мая авторы могли засылать свои задачи, из которых должны были выбрать лучшие 12. Потом в течение мая их тестили и отбирали лучшие шесть - 3 для полуфинала и 3 для финала.

Я тоже решил испытать судьбу и предложил пару задач - один Easy и один Medium. В итоге в 12 кандидатов ни одна не попала. Во время моего второго SRMа я пообщался с Иваном по их поводу, и он сказал, что Easy была слишком сложной, а Medium - слишком лёгкой :) Тем не менее, он считал, что первую можно использовать как Div1 Medium для обычного матча, а вторую - как Div2 Hard. Так что я вскоре состряпал ещё 3 задачи и попросил на них взглянуть.

Сразу после окончания TCO, то есть в первых числах июня, Иван действительно посмотрел на задачи. Более того, он сразу предложил мне выбрать дату матча - честно говоря, проведя SRM только за месяц до этого, я этого не ожидал. На календаре значился только SRM 443, а остальные ещё не были прописаны, поэтому особо выбирать мне не пришлось.

В процессе тестирования я пару раз заменил Div2 Easy, а также придумал другой Div1 Hard. Наконец задачи были утверждены в том комплекте, который и попал на матч. Но вот по поводу распределения очков за задачи довольно долго шел спор. Вернее, главным образом спорили по поводу задачи BinaryFlips - той, что я задумывал как Easy для TCO. Мне она представлялась не такой уж сложной, и я требовал за неё чуть ли не 450 очков. Тестер и Метельский же, напротив, настаивали на 600. В итоге я сдался, и результаты ясно показывают, что я был неправ.

Что касается решений, в каком-то виде они лежат в editorialе на топкодере, но я всё же опишу свои варианты.

Div2 Easy - SoccerLeagues. Как и подобает задаче этого уровня, никаких особых знаний или оригинальных подходов в ней не требуется. На самом деле задача была даже легче обычного: правильно написать два вложенных цикла умудрились почти все участники.

Div2 Medium / Div1 Easy - CirclesCountry. Тут я ещё в условии прикольнулся, правда без знания грузинского языка этого всё равно не понять. Так вот, к этой задаче есть два подхода. Первый, более сложный - построить граф (а собственно дерево) из окружностей и найти в нём длину пути между окружностями, содержащими требуемые точки. Честно говоря, моё решение было именно таким, и я был довольно удивлён, когда в процессе тестирования нашлось намного более лёгкое: просто посчитать количество окружностей, которые содержат ровно одну из требуемых точек. Таким образом, для многих опытных участников проблемой стало то, что они сразу начали реализацию первого подхода и потеряли минут десять относительно людей, имплементировавших подоход №2.

Div2 Hard - Polygons2. Учитывая, что многие кодеры во втором дивизионе справились с первыми двумя задачами за 20-25 минут, по этой задаче было много (92) submission-ов. Тем не менее, большинство из них было просто перебором. В итоге правильными было только 5 решений, и самое быстрое из них заняло 42 с лишним минуты. Это меня хоть немного успокоило, потому что для меня задача была совсем не лёгкой. А решать её надо с помощью динамического программирования: ответ можно легко вычислить, если знать, сколькими способами можно получить (K-1)-угольник с наибольшей стороной длины A и периметром P. Эту начальную идею нужно было несколько оптимизировать, но в итоге код получался длиной в несколько строк.

Div1 Medium - BinaryFlips. В отличии от подходов, описанных на топкодере, моё решение имеет сложность O(1). Я бы его и туда добавил, но боюсь, что не смогу нормально объяснить. По крайней мере, пока здесь попытаюсь.
Давайте каким-либо образом проиндексируем все A+B чисел. В конечном итоге нам нужно изменить ровно A индексов по отношению к их начальному состоянию. Очевидно, что за один ход мы можем изменить ровно K индексов. За два же хода можно изменить любое четное количество индексов в пределах от 2 до 2*min(K,N-K). Например, чтобы изменить ровно 2 индекса за 2 хода (при K>1), мы можем флипануть за первый ход некоторое множество индексов {i1,i2,...,i(K-1),j1}, а за второй - множество {i1,i2,...,i(K-1),j2}. Таким образом, относительно начального положения изменятся только индексы j1 и j2. Аналогично, для изменения большего количества индексов, надо брать меньше общих элементов для изменяемых на каждом ходе множеств. Именно поэтому невозможно изменить больше, чем 2*(N-K) индексов.
Так что мы имеем? Мы должны выразить число A в виде суммы чисел K и четных чисел между 2 и 2*min(K,N-K), причём цена числа K равна 1, цена остальных чисел равна 2, и сумма должна быть как можно дешевле. Вот тут уже надо рассмотреть несколько случаев:
1) A=0 => ANS=0
2) A=K => ANS=1
3) Если ни одно не выполняется, то K>=N => ANS=-1
4) (A%2=1) AND (K%2=0) => ANS=-1. В этом случае мы пытаемся получить нечётное число суммой четных.
Обозначим теперь Z=2*min(K,N-K) и функцию ceil(X)=наименьшее целое, большее или равное X.
5) (A%2=1) AND (K%2=1) => ANS=1+2*ceil(abs(A-K)/Z).
6) (A%2=0) AND (K%2=1) => ANS=2*ceil(A/Z).
7) (A%2=0) AND (K%2=0) => min(1+2*ceil(abs(A-K)/Z), 2*ceil(A/Z)).
Вдумавшись в каждое из этих выражений, можно (я надеюсь) понять, какая логика за ним стоит. Правда, написав всё это, я уже не думаю, что задача была такая уж и лёгкая :D

Div1 Hard - ShuffledPlaylist. Я снова написал задачу про музыку, правда, много наврал - никогда я ничего не shuffle-ю. Так или иначе, задачу можно было решать двумя методами. Для обоих общей частью является построение матрицы переходов из одного положения в другое. Положением в задаче описывается, песня какого стиля в данный момент проигрывается и сколько минут осталось до её окончания, плюс желательно иметь одно положение для начального момента.
Более сложный метод на этом останавливается и далее работает следующим образом. Если возвести начальную матрицу в степень X и посчитать сумму элементов, обозначающих переход от начального положения в конец песни для каждого стиля, мы получим количество плейлистов длины ровно X. Если мы как-то умудримся посчитать сумму таких элементов S(X) для всех степеней матрицы от 1 до X, мы получим количество плейлистов длины от 1 до X. Тогда ответом задачи будет S(maxLength)-S(minLength-1). А считать суммы в непрерывном интервале можно по формуле: S(1)+S(2)+...+S(X) = (S(X/2)+1)*[S(1)+S(2)+...+S(X/2)] (это при чётном X, при нечётном соответственно придётся отдельно прибавить элемент S(X)). Короче говоря, возни много.
Обойтись без суммирования матриц можно, если несколько видоизменить матрицу переходов, а конкретно - добавить в вершину, соответствующую концу плейлиста, из которой будут переходы только в саму себя. Тогда количество плейлистов длины от 1 до X будет храниться в элементе матрицы, соответствующем этой самой вершине.

В итоге SRM выдался довольно тяжелым, со всеми задачами в первом дивизионе справилось лишь 3 человека. Хотя в наших краях была глубокая ночь, и многие могут сослаться на это, оправдывая свои неудачи. Так или иначе, я снова получил удовольствие и до Нового года попытаюсь опять собраться с мыслями и выдать ещё один проблемсет ;)

SRM 440

После возвращения с зимней школы, у меня была пара свободных недель до начала следующего семестра в университете, и я уделил время созданию задач для своего второго матча на топкодере. На этот раз я написал 6 разных задач, но концепт обеих Easy и обеих Medium был общий, и в случае Medium-ов мне это очень нравилось.

Ответа я ждал примерно месяц. За это время сменился координатор задач на топкодере - Олексия сменил Иван Метельский. Ответил мне уже последний. Посмотрев задачи, он довольно скоро предложил мне выбрать матч - и я взял первый же неночной SRM после финала ACM.

Тестера на матч назначили в тот день, когда мы с финала вернулись, и им, к моей большой радости, оказался не кто иной, как Вася. За дело он принялся довольно скоро, а расправился с задачами ещё быстрее. Более того, он написал быстрое и красивое решение для div1 Hard, на которое я в итоге и заменил своё страшное и неповоротливое детище.

Опишу вкратце подходы к задачам:
Div2 Easy - IncredibleMachineEasy. Действительно, есть такая старая игра от компании Sierra, и когда-то я в неё играл. Было весело. Так вот, написав уравнение зависимости времени, ускорения и высот падений шариков, мы получим что-то этакое: T=sqrt(2*h1/a)+sqrt(2*h2/a)+...+sqrt(2*hN/a). Умножив обе части уравнения на sqrt(a)/T и возведя получившееся в квадрат, мы придём к формуле для ускорения: a=2*(sqrt(h1)+sqrt(h2)+...+sqrt(hN))/T]^2. Альтернативой этому подходу был перебор ускорения двоичным поиском: проверить, годно ли то или иное значение, можно подставив его в первоначальную формулу.

Div1 Easy - IncredibleMachine. Тут мы видим уже усложнённый вариант: в дело вступают наклонные плоскости. Решать задачу можно опять чисто аналитически, но в данном случае, на мой взгляд, намного легче применить двоичный поиск. Несмотря на то, что в условии даны были все формулы, кто-то всё равно посчитал его не достаточно ясным. Мне трудно судить, хотя учитывая, что большинство всё же решило задачу довольно быстро, наверное, условие всё же было понятным. Так или иначе, приносить задачи физического характера на топкодер довольно тяжело, потому что сложно описать все допущения и условия, принятые в задаче относительно классических законов физики.

Div2 Medium - MazeWanderingEasy. Задача эта возникла как дополнение к её более сложному собрату из первого дивизиона. Я на самом деле видел по Discovery программу, где подобным экспериментом показывали, как изменялись умственные способности мышей при прослушивании различной музыки. Несмотря на то, что я слушаю большей частью металл, подобная задача показалась мне весёлой (хотя кто-то воспринял условие MazeWandering как личное оскорбление :D). Что касается решения, надо было всего лишь найти путь в дереве между двумя вершинами и посчитать на нём количество вершин с decision-ами, то есть именно то, что сказано в условии.

Div1 Medium - MazeWandering. Я люблю задачи на вероятность, поэтому появление такой задачи на моём матче было лишь вопросом времени. Как только вспомню, как я её решал - сразу напишу ;)

Div2 Hard - WickedTeacher. Человеку, знакомому с динамическим программированием и решавшему задачи на битмаски, задача не должна показаться особо оригинальной. Понятно, что вероятность равна отношению [количества таких перестановок входящих фрагментов, для которых итоговое число делится на K] к [общему количеству перестановок, то есть собственно N!]. А для того, чтобы считать число в знаменателе, надо уметь считать NUM(mask,rem), то есть количество перестановок входных фрагментов, составленных из множества, определённого mask, и дающих при делении на K остаток rem. Всего аргументов у NUM может быть 2^N * K штук, что составляет примерно 3*10^6. В конечном счёте, в задаче было над чем повозиться, и решил её один-единственный участник.

Div1 Hard - SquareFreeSets. К этой задаче я видел два различных подхода. Первый, который я заметил в пяти из 7 прошедших systest решений и который описан в editorialе - перебор с запоминанием. Второй, который и использовал Вася - динамическое программирование. Положение описывается тремя параметрами: какие числа уже рассмотрены (а так как их можно рассматривать по возрастанию, то надо запоминать только наибольшее), сколько чисел взято в наше множество и маска простых чисел, которые уже использованы при составлении множества. Ясно, что маску всех простых запоминать невозможно - а достаточно запомнить маску тех простых, которые в квадрате не превосходят N. Чтобы не повторять варианты при рассмотрении чисел, делящихся на более большие простые, надо при рассмотрении простого числа, большего sqrt(N), сразу рассмотреть все кратные ему числа, и вообще исключить их из рассмотрения позднее.

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

ACM ICPC World Finals 2009 - Stockholm

This Olympiad-related post is a stub. Unfortunately, you cannot alter its content by simply clicking the Edit button. However, you are welcome to leave the appropriate stories in the comments.

SRM 433

Как известно, на топкодере довольно часто проводятся алгоритмические соревнования высокого уровня, называемые SRM-ами (Single Round Match). Каждый SRM, или попросту матч, длится примерно два часа. Первые 75 минут (называемые Coding Phase) участники занимаются непосредственно решением предложенных задач, затем идёт пятиминутный перерыв (Intermission), затем в течение пятнадцати минут (Challenge Phase) у соревнующихся есть возможность посмотреть на решения, присланные своими противниками, и попытаться их "зачеленджить", т.е. придумать такие данные, для которых решение не будет работать правильно. Потом некоторое время люди ждут окончательных результатов, болтают о том - о сём, сетуют на всё повышающееся количество китайских участников, и расходятся.

Учитывая, что уровень участников очень неоднородный, каждый матч проводится в двух дивизионах. Люди, имеющие более высокий рейтинг, соревнуются в первом, более низкий - соответственно, во втором дивизионе. Главное отличие между дивизионами - это предложенные задачи. В обоих дивизионах их по три. В рамках одного дивизиона задачи делятся на лёгкую, среднюю и сложную. Тем не менее, задачи первого дивизиона на порядок сложнее задач второго (лёгкая задача в первом дивизионе часто используется как средняя для второго). Так или иначе, для проведения матча всегда нужно от 4 до 6 более-менее оригинальных задач разного уровня сложности.

Упомянутое в первом абзаце "довольно часто" в конце 2008 года равнялось примерно четырём матчам в месяц. Человеку, хорошо знакомому со спецификой олимпиадных задач, должно быть понятно, что один и тот же человек или группа людей не в состоянии каждую неделю выдавать оригинальный комплект интересных задач. Так вот топкодер этого и не делает - он даёт возможность самим участникам предлагать свои задачи в обмен на некоторое денежное вознаграждение. То есть любой пользователь, достигший 18 лет, имеющий определённый рейтинг и количество проведённых матчей, может придумать свои задачи и, если они достаточно интересные, он получает шанс стать автором матча.

Провести свой собственный матч уже давно было моим заветным желанием, и ещё осенью у меня были готовы задачи, так что я терпеливо ждал своего шанса. И он появился примерно в то же время, когда мне предложили поработать на сборах. То есть в то время за мной закрепили SRM 433, дата которого была 21 января.

Процесс получения SRMа выглядит примерно так. Сначала человек делает наброски своих задач в специальном приложении MPSQAS, иначе говоря пишет условия, и необязательно оконченные. Потом надо написать администратору, ответственному за выбор задач, с просьбой посмотреть на плоды своих мучений. Рано или поздно ему приходится взглянуть на задачи, и тогда по каждой он или задаёт дополнительные вопросы, потому что наброски часто слишком далеки от совершенства, или сразу отклоняет, чаще всего потому, что она слишком неоригинальная и уже была на топкодере пару десятков раз, или утверждает её. Имея утвержденные задачи всех уровней для обоих дивизионов (в принципе, пару лёгких могут и простить для начала), можно смело просить SRM. Я не уверен, чем админы руководствуются, отдавая тот или иной матч в чьи-то руки, но могу сказать, что лично меня до сих пор не обижали.

Получив SRM, надо доводить его до ума. То есть если не хватало какой-либо задачи, надо её придумать, все условия надо максимально отточить, надо написать авторские решения - причём обязательно на Java, и на всех возможных тестах решение не должно работать больше 1 секунды, и надо добросовестно составить эти самые тесты. Потом за дело берутся люди, на которых возлежит ответственность за то, чтобы всё было максимально точно, правильно и понятно. По моему опыту, таких бывает трое: администратор, ответственный за выбор задач, тестер и PabloGilberto, который занимается исключительно английским языком. Выбор тестера происходит сразу после утверждения матча.

На моём первом SRMе координатором по задачам был OlexiyO, а тестером выступал Иван Метельский. Особо много нам мучаться не пришлось (разве лишь что меня заставили рисовать дополнительные картинки в div1 Medium), и день матча подошел довольно быстро. Перед матчем автору дают специально сгенерированный пароль от ника writer, который обладает разными прикольными функциями. Этот ник в арене обладает администраторскими привилегиями, и позволяет читать все чаты в арене, в том числе шепот. Хотя часто это становится просто проклятием, потому что чата чрезвычайно много. Также во время Coding Phase можно видеть коды любых участников. Вообщем, во время матча не соскучишься.

Что касается моих задач, бегло пройдусь по основным идеям:

Div2 Easy - RoyalTreasurer. Довольно стандартная задача - очевидно, что минимальная сумма достигается, когда наибольшие элементы первого массива сгруппированы с наименьшими элементами второго.

Div2 Medium / Div1 Easy - MagicWords. Несмотря на низкие ограничения, просто перебрать все возможные перестановки слов и проверить каждую тривиальным алгоритмом не получалось, или по крайней мере не должно было получаться. Есть множество методов, с помощью которых можно ускорить эту проверку: хеширование, KMP, технические оптимизации. Авторский вариант основывался на следующем наблюдении: если строка длины L повторяется в своих shift-ах ровно K раз, то она является периодической с периодом, равным L/K - и наоборот. Таким образом, надо было проверять периодичность строки для периодов, равных делителям L.
Ещё одно решение, которое я сначала не заметил, но потом мне очень понравилось, основывалось на том, что сместив последнее слово в нашей перестановке в начало, мы получаем строку с таким же множестов shift-ов. Таким образом, можно было перебирать все перестановки первых (N-1) строк, а последнюю всегда ставить в конец - тогда итоговый ответ получается при умножении полученного количества магических строк на N.

Div2 Hard - MakingPotions. Идеей решение похоже на алгоритм Дейкстры - на каждом шагу помечать полученным то снадобье, которое ещё не получено и имеет наименьшую цену. Если таким образом мы дойдём до LOVE, то получим его за наименьшую возможную цену, если нет - оно не достаётся. Проблемы могли возникнуть при парсировке входных данных, или с теми ситуациями, когда цены становились слишком большими.

Div1 Medium - SettingTents. Задача, которую решили, к моему удивлению, меньше ста человек, что для Medium в принципе маловато. На самом деле в ней проходил даже алгоритм сложности O(N^5), т.е. перебрать обе координаты обеих вершин диагонали ромба, а затем пройти одним циклом по длине второй диагонали и проверить, попадают ли её концы в целочисленные точки. От этого цикла можно было избавиться несложными математическими вычислениями. Во время матча большей частью были имплементированы более быстрые алгоритмы. Недавно я натолкнулся на довольно старый пост в блоге Petr-а, в котором были рассмотрены методы решения подобной задачи - советую посмотреть.

Div1 Hard - BarbarianInvasion. "Праздник потока", как её потом обозвали. Действительно, задача требовала нахождение минимального вершинного разреза, только при условии, что в первую очередь должно быть минимизировано количество вырезанных вершин, а потом их суммарная стоимость. В таком случае применяют следующий фокус: весом вершины делаем её стоимость + некую большую константу X, которая заведомо больше любой возможной суммарной стоимости вырезанных вершин при данных в задаче ограничениях. Тогда, найдя величину минимального разреза ANS между столицей и граничными клетками, мы будем иметь минимальное количество вырезанных вершин как ANS/X и минимальную стоимость этих вершин (при условии минимизации их количества) как ANS%X.

Можете также посмотреть editorial этого матча и его результаты.

Сборы кандидатов в Бакуриани

После полуфинала я решил расслабиться и позволял себе выступать только на топкодере. В принципе, смотря сейчас на мои тогдашние результаты, лучше б и не позволял :)

Не помню, до каких пор я планировал отдыхать, но в последних числах декабря я получил звонок от Deputy Leader'а грузинской сборной школьников по информатике, Гочи Мандария. В начале января планировалось проведение зимних сборов для кандидатов в сборную, и мне предложили позаниматься с детьми несколько дней. Это был первый раз, когда ко мне обратились с предложением подобного рода, а поработать с ребятами мне давно хотелось, поэтому я согласился без лишних раздумий, несмотря на довольно ограниченное время, остававшееся до начала сборов. Таким образом, предновогодние дни я провёл, с большим воодушевлением готовя материал для лекций и соответствующие ему задачи.

Сборы проводились в Бакуриани, на базе тамошней школы №1 (не хочу соврать, но вроде она там и единственная). Компьютерный класс там такой, какому позавидует по крайней мере большинство тбилисских школ, плюс к тому школа оснащена солнечными аккумуляторами и электричество работает без сбоев. А снаружи в это время стояла очаровательная зимняя погода.


В моём распоряжении было 5 дней, один из которых попадал на Рождество, и поэтому заниматься в него никто и не думал. Зато остальные четыре дня я собирался мучать детей по полной. Первые три дня я собирался проводить лекцию, а затем 3часовый контест по школьным правилам, состоявший из 3 задач на тематику объясненного материала. На последний день у меня был припрятан 5часовый контест из 5 задач на все темы вперемешку.

В итоге всё шло примерно по плану. У нас царила здоровая, весёлая атмосфера, которая не мешала ребятам концентрироваться на контестах.


Темы первых дней у меня были следующие: бинарный и тернарный поиск в первый день, битмаски во второй, а на третий ко мне присоединился Леква, и общими усилиями были разобраны деревья отрезков и поиск в ширину на графе с ребрами длины 0 и 1. Задачи, которые я составил для тех сборов, потом появились на различных контестах, к созданию которых я приложил руку - в том числе на туре, проведённом нашей командой на сборах в Харькове, и моём мини-контесте на armcoderе.

А между вторым и третьим днём был вышеупомянутый выходной, и мы вдоволь накатались на лыжах.


Также имела место эпохальная битва в джокер, в которой Ника Габисония и Гоча Мандария были повержены, за что одному пришлось лепить снеговика, а второму его украшать.


Ну а в мой последний день и мне, и Лекве пора была уматывать домой, а нас должны были сменить другие специалисты. Поэтому мы оставили ребятам задачи на 5 часов и сели в маршрутку. С утра погода не предвещала ничего зловещего, но по дороге к Тбилиси собрались тучи, поднялся страшный ветер, пошёл град, и мы были благодарны судьбе, когда наконец доехали. Как потом оказалось, в Бакуриани вообще была буря, так что не поспеши мы тогда, могли застрять надолго. Зато мы пропустили невероятное сражение в снежки, которое разразилось на следующий день в рядах нашей делегации и в результате которой кое-кого накормили большой кучей снега. Что поделать, каждому своё...

[aq unda iyos TovliT naWami varamas suraTi. visac mogepovebaT, dadeT :D]

NEERC 2008

26 ноября проводился полуфинал ACM ICPC в регионе северовосточной Европы. В этот регион входят все страны постсоветского пространства (кроме Украины и Молдовы), поэтому проведение соревнования в одном месте было бы несколько проблематично. Так что организаторы предпочитают сталкиваться с трудностями другого плана, проводя соревнование синхронизированно в четырёх местах одновременно: Санкт-Петербурге, Барнауле, Ташкенте и у нас на Кавказе, что из последних четырёх лет три раза было в Батуми.

В Батуми обычно приезжают команды из Грузии, Армении и Азербайджана. Учитывая, что на задачах полуфинала у нас проводится и Открытый командный чемпионат Южного Кавказа, с отдельным зачётом и иногда призовым фондом, каждый год у нас бывала гостевая команда, которой до сих пор обычно и доставалось первое место. В 2005 году это была Moscow x13, которая умудрилась не пройти из своего четвертьфинала, но тем не менее решила то ли 10, то ли 11 из 11 задач, предложенных на полуфинале. В 2007 году это была Lviv NU, которая впоследствии была награждена золотыми медалями на финале ACM ICPC. В 2008 году у нас было целых три гостя из Украины, и более того - две команды (NTUU KPI и Sumy SU) боролись за право учавствовать в финале именно из нашего региона. Третья же, Taurida NU, к тому моменту уже была финалистом, так как полуфинал их региона проводится раньше, чем NEERC.

Команды из Киева и Сум (Сумы, Сумов, не знаю как правильно склонять) приехали в Тбилиси 23-го числа, под вечер. Киевляне решили уехать в Батуми сразу ночным поездом, а Sumy SU остались, чтобы уехать с потоком команд из Тбилиси следующей ночью. Так что 24-ого у нас было время показать ребятам город.

Стоим слева направо: Гиоргий Сагинадзе (какой-то он тут грозный), я, тренер Sumy SU Сергей, Боря, а присевший - Саша. Фотографировал нас Виталий.

Как уже говорилось, в ночь с 24-ого на 25-ое большинство команд на поезде переместилось в Батуми (может, я с датами на день ошибаюсь, но да ладно). В первый день было открытие и пробный тур. Ничего особо интересного там на моей памяти не происходило.


Главное событие состоялось 26-ого. Проблемсет NEERC состоял из 11 задач, среди которых впервые присутствовала необычная для ACM-контестов интерактивная задача. То есть вместо стандартного "введи данные - выведи ответ" была целая череда "введи - выведи", причём входные данные подавались программе в зависимости от её предыдущих аутпутов. На этот раз задача была довольно простая - обойти некоторый граф DFS-ом. Но в принципе в будущем, я думаю, будут приносить в качестве интерактивной интересные задачи на теорию игр.

Как это часто у нас получается, начали мы с не самой лёгкой задачи, поэтому когда мы её провели на 28-ой минуте, у нескольких команд было уже по две, а SPb IFMO 1 вообще умудрилась решить 4ую на той же минуте, что мы первую. Но за следующие 40 минут мы решили ещё 4 и оказались среди лидеров. За следующий час мы расправились ещё с двумя задачами и с 7 задачами продолжали уверенно оставаться в первой десятке. Ещё более часа нам потребовалось на задачу K, которая, как выяснилось позднее, и вывела нас в финал. После этой задачи мы 100 минут безуспешно маялись с остальными задачами, долго писали D, но она так и не поддалась. Хуже получилось только у Бурундучков, Ижевска и Петрозаводска: у них не было AC последние 170 (!) минут. На мой взгляд, неуравновешенный получился проблемсет.

Как выяснилось позднее, NTUU KPI также решили 8 задач, и как выяснилось ещё позднее, 8 задач как раз и гарантировали попадание в финал для команд, обошедших своих конкурентов из того же университета. Что касается других команд Тбилисского Университета, две из них решили по 6, задач, заняв 46-ое и 56-ое места, а последняя решила 5 задач. В совокупности с достижением TSU1 это является лучшим результатом команд ТГУ на протяжении периода выступления наших команд в NEERC.

Можете посмотреть окончательные результаты NEERC и чемпионата Южного Кавказа.


27-ое число было посвящено спортивным соревнованиям, был проведён чемпионат по футболу и пинг-понгу. В футболе второй год подряд победу одержала команда учителей, а в настольном теннисе, если я не ошибаюсь, первое место занял Сергей Канищев.


В формате чемпионата Южного Кавказа, кроме командного первенства на задачах NEERC, бывает также личное первенство. Проводится оно по обычным правилам ACM, а задачи берут с в теории неизвестных в наших краях контестов. В прошлом году задачи были с South American Regional Contest 2007. Как ни странно, в этом году задачи взяли с этого же контеста, соответственно 2008 года. Боле того, на этих задачах проводился контест на uva.onlinejudge.org. Некоторые из участников личного первенства его даже писали. И ещё - эти задачи выложили на архиве spoj.pl (№№3405-3415) 23 ноября, а наше-то первенство проводилось 28-го числа... Так или иначе, можете взглянуть на результаты соревнования.


Ну а 29-ого числа состоялся банкет, на котором, несмотря на некоторую напряженность, в итоге было очень весело.

Open All-Siberian Olympiad 2008

Следующее событие - финал Открытой Всесибирской олимпиады им. Потоссина. В 2008 году эта олимпиада проводилась уже в девятый раз. Не знаю, как было сначала, но последние три раза перед onsite финалом проводился отборочный раунд через интернет. Можете посмотреть на результаты последнего.

Так вот, в 2008 году команда ТГУ в третий раз подряд прошла в финал этой олимпиады, но в этом году перспектива поехать была ещё более призрачной, чем когда-либо ранее, вследствие августовских событий. На этот раз организаторами олимпиады было допущено исключение по отношению к нашей команде - нам была представлена возможность учавствовать из Тбилиси, тем не менее оставаясь в конкурсе. К нам приехал представитель Новосибирского Государственного Университета, господин Николай Вячеславович Шилов, для контроля соблюдения нами правил во время соревнования.

Этот человек мне очень запомнился, он интересный собеседник и вообще приятная личность. Также он потряс меня своим умением вести беседу, вернее, одной особенностью. Я часто замечаю, что во время разговора человек, объясняя подробности чего-либо, вспоминает связанные с этим темы и постепенно разговор переходит в новое русло, а первоначальная идея теряется. Ну по крайней мере со мной так часто бывает, и я могу только позднее вспомнить, что на самом деле я хотел сначала досказать. А вот Николай Вячеславович умудрялся углубиться в детали, рассказать связанные с ними вещи, но сколь долго бы он не говорил, в итоге он возвращался к предыдущей теме и досказывал свои мысли до конца. Он мог так вспомнить что-то, затем что-то, связанное с этим чем-то, и так далее, а затем обязательно закончить каждую предыдущую мысль. Примечание ненасытного олимпиадщика: если представить все мысли как дерево, в котором каждая новая идея - вершина; ассоциация, приводящая от одной мысли к другой - ребро; а мысль, после которой тема исчерпана - лист, то этот человек обходил всё дерево поиском в глубину. Something like that :D

Ну чтож, может, в разговоре я и забываю первоначальную тему, но на бумаге я точно следую плану. Поэтому вернёмся к финалу Всесибирской олимпиады.

Формат финала подразумевал два дня соревнований. Первое соревнование было 5- или 6-часовым, точно не помню. Давалась одна страшная и неповоротливая задача в стиле Marathon Match, которая на этот раз была чем-то таким:

Дано некое пространство, в нём N треугольников и M точек (N<=10^5, M<=10^4). Найдите для каждой точки список всех точек, которые из неё видны. Видимость означает, что отрезок, соединяющий эти точки, не пересекается ни с одним из треугольников. Очки команда набирала за каждый правильно угаданный список. Time Limit был что-то вроде 10 секунд. К задаче прилагался визуализатор, с помощью которого можно было осмотреть это самое пространство для любого теста. Давалось около 5-6 example тестов, а всего их было что-то вроде 50.

Было ясно, что перебирать для каждой вершины все остальные и потом проверять все треугольники, т.е. O(M^2 * N), точно слишком медленно для больших тестов. Тем не менее, ничего лучше нам в голову так и не пришло, поэтому Ника имплементировал этот подход. Потом мы его максимально обрезали, не рассматривали треугольники вне какого-то интервала, определённого отрезком, и т.д. и т.п. В итоге мы вышли на четвёртое место по результатам этого дня, и по набранным командами очками было видно, что кроме первых двух команд (по-моему SPb IFMO и MSU Unpredictable), никто лучшего подхода к задаче не нашёл.

Второй день соревнований проводился по стандартным правилам ACM. Задачи были довольно сложные, мы в итоге только 7 решили и вышли на четвёртое место по результатам того дня. Задачи я особо не помню, из менее решаемых был вроде MCMF, FFT, ещё задача на нахождение мат. ожидания в довольно извращенных условиях.

По сумме двух дней мы вышли на третье место и уступили второму только по допольнительным показателям - т.е. мы имели с ними одинаковое среднее место, подсчитанное как [(PlaceDay1)/2+PlaceDay2], но во второй день они были выше, а приоритет отдавался именно ему. Окончательная таблица выглядит так.

ACM ICPC 1/4 Finals - Georgia Subregion

Первым в хронологическом порядке, вроде бы, следует четвертьфинал ACM ICPC, проведённый 1 ноября, который одновременно является этаким первенством Грузии, хотя никаких дипломов, титулов или призов на нём не раздаётся. Правда, в этом году, помимо грузинских команд, в нашем четвертьфинале участие приняли две команды из Украины (NTUU KPI и Sumy SU), которые в итоге успешно прошли в полуфинал.

Леква во время четвертьфинала был в Кутаиси, поэтому писали только Ника и я. Задачи, как и в прошлом году, представляли собой упрощенный вариант задач Северного четвертьфинального региона. Первые 50 минут у компа сидел я, а Ника читал задачи и говорил мне алгоритмы. Пустив так 6 задач, я уступил ему место и из оставшихся 5 задач 4 написал уже он. В итоге мы закончили за 126 минут и вскоре покинули место действия, окончательные результаты увидев уже дома. В полуфинал были допущены все команды, решившие хоть что-либо, за исключением Tbilisi SU 5 и 6, потому что квота на количество команд от одного университета для полуфинала в Батуми равна 4 командам.

Спустя несколько месяцев...

После довольно длительного молчания я снова переборол свою чрезвычайную лень и решился написать. С октября событий накопилось достаточно, и я попытаюсь пробежаться по медленно, но уверенно блекнущим в памяти впечатлениям и пересказать как можно больше.

Google Code Jam 2008 Semifinal - Zurich

Этот пост будет посвящен полуфиналу Google Code Jam 2008 в регионе EMEA (Europe, Middle East and Africa), вернее, моей поездке в Цюрих на этот onsite и оставшимся впечатлениям.

Для начала немного о предистории этого события, которой на этом блоге не имеется (по крайней мере пока), так как я пишу свой первый пост :D

Google Code Jam - ежегодное соревнование по спортивному программированию, которое проводится всемирно известной компанией Google. До 2007 года оно проводилось по формату и на сервере Topcoder, в 2007 году его не было вообще, а в 2008 его решили провести по совершенно изменённым правилам. Сейчас я не буду в них углубляться, а скажу лишь, что первые 4 раунда проводились онлайн, т.е. по интернету, и в результате последнего из них было избрано 500 человек, которые прошли в онсайт-раунд. Более двухсот из них были из региона EMEA и были распределены по Европейским офисам компании Google - из них наибольшее количество, 93, в Цюрихском офисе - в том числе я и Ника. К сожалению, остальные участники из Грузии не попали в этот этап соревнования, при чём большей частью из-за неспортивных препятствий...

Швейцарскую визу мы получили без особых проблем, и в ночь с 4ого на 5ое октября, совершив пересадку в Стамбуле, долетели до Цюрихского аэропорта.

Первым открытием для меня стала транспортная система Швейцарии. Общественным транспортом являются поезда (которые разъезжают как по туннелям, так и над землей), трамваи и водный транспорт (хотя на последнем мне покататься так и не удалось). Никаких автобусов или троллейбусов - соблюдают экологическую чистоту. Билеты на весь общественный транспорт одни и те же, то есть купив билет можно как сесть на поезд, так и на трамвай. В принципе, сесть-то можно и без билета. Никто не ограничивает доступ в транспорт - билеты проверяют внутри, да и то редко. Зато если попадешься без него, штраф 80 швейцарских франков.

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

Другими популярными видами транспорта являются мотоциклы и велосипеды. На велосипеде там, похоже, передвигается каждый третий или даже второй. В городе есть множество этаких гаражей, где можно за 25 франков взять велосипед до конца дня. При этом возвращая велосипед, человек получает свои деньги обратно.

***

В Цюрихе аэропорт находится не где-нибудь за чертой города, а довольно близко к центру, так что поездка в отель не заняла у нас много времени. Не знаю, насколько хорош отель Four Points by Sheraton Sihlcity по тамошним меркам, но я в таком ещё не жил :D



Первый день в Цюрихе я провёл в сладостной дремоте. Проснувшись лишь к шести часам вечера, я услышал жалобные стоны своего желудка и решил найти место, где можно было перекусить. Как оказалось, в воскресенье, да ещё и вечером, это было не так-то легко. Мы с Никой обошли за полтора часа окрестности отеля, нашли лишь один открытый бургер-бан, а потом обнаружили McDonalds и перекусили там. Особо интересного в тот день больше ничего не происходило, разве лишь что мы встретили нескольких других участников, в том числе ребят из Саратова.

Утром второго дня работники Google встречали нас в вестибюле отеля, чтобы отвести в местный офис.


После довольно затянувшейся регистрации мы заняли рабочие места по принципу "в тесноте, да не в обиде": каждому участнику была отведена полоска на столе шириной до 1 метра, где были расположены ноутбуки, external keyboard & mouse и где мы также должны были калякать свои мысли во время соревнования. Старт откладывался несколько раз, чтобы обеспечить сихронизированное начало контеста во всех офисах одновременно, но в итоге двухчасовая борьба наконец началась.

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

Сама итоговая таблица лежит здесь (надеюсь, ссылка не изменится).


После соревнования нам предложили перекусить (еда в Google потрясающая), а потом устроили office tours. К сожалению, фотографировать там было запрещено, но большинство того, что мы там видели, определённо лежит на youtube :)

Затем у нас был час, который каждый участник мог заполнить одной из презентаций или провести в комнате развлечений. Как и многие codejam'овцы, я избрал последнюю возможность, так что мы вдоволь наигрались в Air Hockey. Правда, шайба не клеилась к столу и часто летала по комнате, создавая угрозу здоровью участников.


Третий день нашего пребывания в Цюрихе был предназначен для собеседования. Моё было назначено на середину дня, поэтому с утра я, Василь и GeKa занялись туризмом в центре города.


Не знаю, как обстоит дело в других крупных компаниях, но собеседование в Google произвело на меня впечатление. В течение почти четырех часов четыре разных человека беседовали со мной о структурах баз данных, алгоритмах, моем опыте работы и т.д., и при этом я получал от этого большое удовольствие. Результаты обещали сообщить в течение двух недель, но вот на дворе уже декабрь, а ответа пока ни я, ни Ника, ни украинцы, приезжавшие сейчас на Чепмионат Южного Кавказа, не получили. Наверное, кризис :)

А нас следующий день мы умотали домой. Ах да, только сейчас вспомнил о печение в отеле - "Speckli". Его приносили после каждой уборки в комнате. Как выразился Вася, оно бессмертное - сколько ни ешь, возвращается снова :D