Сегодня состоится финал VK Cup 2012, Финал! Мы желаем удачи всем участникам, а болельщикам — насладится интересным соревнованием. На открытии финала кубка в своей приветственной речи генеральный директор "В Контакте" Павел Дуров анонсировал апгрейд призового фонда. Я начинаю по-настоящему жалеть, что я не участник! Финалисты поборются за:
- 1 место — $30000
- 2 место — $20000
- 3 место — $10000
- 4-5 места — $2000
- 6-10 места — $1000
Удачи! Желаем только положительных эмоций. На старт! Внимание! ...
UPD: Соревнования завершено! О его ходе и церемонии закрытия, я полагаю, совсем скоро напишет Alex_KPR. Всем спасибо за участие и интерес! Вот полные результаты.
Поздравляем победителей. Тройка лидеров:
- sevenkplus (Yuzhou Gu) Китай
- s-quark (Qinshi Wang) Китай
- tourist (Геннадий Короткевич) Беларусь
UPD: Как вы уже успели заметить, 16-го июля в 19:00 стартует неофициальная онлайн-версия финала VK Cup 2012. Любой желающий может принять участие и почувствовать себя на месте финалиста. Раунд будет нерейтинговым. Если вы решали или в какой-то степени знакомы с задачами, пожалуйста, воздержитесь от участия. Все задачи появятся в архиве и будут доступны всем желающим.
Да, а болельщикам задачи посмотреть-то не дали...
Хотелось бы посмотреть задачи с VK Cup 2012 Финал, пробный тур
Уверен, будет проведена трансляция. Ну или будет доступен виртуальный контест.
Можешь посмотреть, если хочешь.
А когда результаты ?
А белорусы возьмут выигрыш газом?
Откуда у Дурова газ ?
Вообще будет обидно, если такие деньжищи "уедут" за рубеж.
Какая разница в какой стране? Главное если человек заслужил, то он их получит.
Почему так затягиваются сис.тесты?
можете сказать через сколько начнется фин тестирование?
Оно уже давно закончилось. Просто результаты не оглашают до официального закрытия.
Простые болельщики этого не знали =/
А я тоже простой болельщик. Я только CodeGameChallange тестил и с техникой помогал. К финальному раунду я не имею вообще никакого отношения.
можете сказать во сколько оф закрытие?
Если верить yeputons то в 8. Да и лучше на ты.
Надеюсь, администрация найдёт возможность при проведении следующего онсайта оставить доступной остальную функциональность Codeforces.
Ведь, во-первых, далеко не все посетители Codeforces интересуются VK Cup, и делать довольно большую социальную и тренировочную площадку фактически недоступной в выходные кажется неправильным.
А во-вторых, даже те, кто интересуется, не имеют возможности сделать элементарные вещи — например, прочитать правила, относящиеся к динамической стоимости задач, использованной на контесте.
Ну и ещё пожелание: вывешивайте, пожалуйста, расписание мероприятий онсайта (для интересующихся) и расписание ограниченной доступности Codeforces (для всех).
Я могу понять, почему блоги закрыли — чтобы код оттуда не копировали (хотя, кто этим будет заниматься? там все приличные люди). Но вот почему задачи нельзя было посмотреть, так и не понятно. На финале ICPC вон даже разбор проводился прямо во время контеста, а тут просто почитать условия нельзя.
MikeMirzayanov решил перестраховаться настолько, насколько это возможно. В принципе это дало результаты. Сбоев за время контеста замечено вроде не было никаких. Только видимо все считают, что это перебор.
Вряд ли блоги и комментарии закрыли из-за кода, скорее чтобы избежать нагрузки на сервер. Сейчас, например, недоступны страницы типа http://codeforces.me/contests/with/username — видимо, их просто забыли открыть. Вроде бы никакого кода в них не содержится.
Я думаю, что задачи закрыли чтобы потом устроить раунд по ним. И на мой взгляд это интереснее, чем если бы их открыли сейчас.
А что касается остальной функциональности — ну да, видимо перестраховались. Ну вам жалко что ли потерпеть пару часов? :-)
Если об ограниченной доступности будут предупреждать заранее — совершенно не жалко.
Кстати по такому поводу хочется отметить, недостатки динамической системы задач.
Во время контеста можно было несколько раз заметить, как какое-то незначительное событие, вроде сабмита, не прошедшего претесты внизу таблицы, сильно перемешивало топ. Просто потому, что увеличивалось количество людей, и одна из задач стала стоить больше. Или наоборот, кто-то сдал первую задачу, и перемешал тех у кого по 3.
Кроме того, сейчас результаты контеста сильно зависят от падений внизу таблицы. Засчет того, что буквально нескольких упавших решений хватит для того, чтобы одна из примерно одинаковых(судя по текущим результатам) по сложности задач стала стоить больше, давая преимущество тем, кто решал ее раньше. В результате получается, что тактика на контесте сводится к угадать в каком порядке решать задачи. Причем именно угадать, потому что как-то догадаться, где люди много упадут, а где мало не знаю насколько хорошие претесты в задачах невозможно.
пфф, есть другая тактика — решить все
Да? А если несколько человек решат все? В каком порядке это нужно делать?
ага, а самая лучшая тактика — решить все и мгновенно.
Вы можете решить все? Ну а к чему разговоры? :)
UPD. Зеленые и синие: уберите руки от поста...
Вот кстати если бы стоимость была непрерывной, то такого бы не было. Сейчас стоимость может резко подскочить с 500 до 1000, а при непрерывной подскочила бы где-нибудь с 650 до 700 или что-то вроде этого.
и ещё пару камней в огород динамической системы:
только в этой динамической системе возможна ситуация, когда человек, находящийся выше тебя, заваливает задачу на финальных тестах, а ты вместо того, чтобы подняться, опускаешься ещё глубже
я своими глазами видел, как люди делали не проходящие претесты сабмиты, из-за этого появлялись в таблице и этим влияли на стоимость задач, т.е. фактически это означает, что добавление пары-тройки человек, получивших WA на первом претесте, влияет на стоимость задач
В обычной разбаловке в отличии от динамической был случай, когда примерно одинаковое число людей решило B и C, а их стомость разная. Выходит, что они одинаковые по сложности, но повезло тем, кто решил более дорогую, что на мой взгляд не совсем правильно ( я сам такое видел ). При динамической стоимости такого бы не случилось.
Если участник видит, что есть две одинаковые по сложности задачи (с его точки зрения) с разной стоимостью, то вполне логично, что он начнет решать более дорогую. И тут все зависит только от самого участника, когда же используется динамическая сложность, то однозначно правильно выбрать, что решать, нельзя.
Ну да. А если они будут стоить стабильно одинаково, то выйдет вот так .
Да , странно наблюдать было как vlad89 опустился на 8 мест приблизитильно ничего не изменив в своем положении)
Боюсь я уже когда-то это предсказывал.
Вроде как любые промежуточные результаты не имеют вообще никакого значения, так какой смысл их сравнивать? Никто же не спорит, что изначально А+Б будет стоить 3000.
Ну а финальные довольно объективно расставляют участников по местам.
Возможно, разве что, имеет смысл делать динамическую стоимость взломов, иначе на реальном контесте может произойти что-нибудь типа вчерашнего пробного тура.
ИМХО, это спецэффект такого малого количества участников. На обычных раундах всё смотрится вполне адекватно. Сам смотрел на эти прыжки в таблице, в итоге смешно, что (пока что) три 500ки.
Это спецэффект нерелевантности первых N минут к финальному результату.
Система оценивания делается не для того, чтобы было приятно следить за ходом контеста, а для того, чтобы получить финальный результат.
Кто-нибудь знает результаты? Хотя бы до систестов?
таблица была но ее убрали http://codeforces.me/contest/211/standings
Блин. Я же не просто так спрашиваю, там 404. Я просто во время контеста не видел, а щас её нет, а хочется посмотреть. Может у кого осталась открытая, можно запринтскринить например.
Скриншота нет, но до сис. тестов tourist был на первом месте, за ним шли два китайца. yeputons, если не ошибаюсь пятый или шестой. И еще SergeyRogulenko шестой или седьмой. Извиняюсь, если что-то неправильно вспомнил.
https://get.google.com/albumarchive/pwa/115317317397602031319/Temporary?authkey=Gv1sRgCMnkzd6PjMD6Xg
tourist был первый и единственный сдавший все задачи. Затем китайские и тайваньские товарищи.6 yeputons 7 SergeyRogulenko.
Картинки в прошлой правке, т.к спойлера не нашел.
Уберите картинки под спойлер...
это и есть CFstyle спойлер)
1) tourist (все 5 задач) 2) sevenkplus (4 задачи + 2 успешных взлома) 3) s-quark (4 задачи) 4) ... (Китай или Тайвань) 5) ... (Китай или Тайвань) 6) yeputons (4 задачи) 7) SergeyRogulenko (4 задачи) 8) ... 9) ... 10) ... 11) dzhulgakov (3 задачи) 11) WJMZBMR (4 задачи)
Если соответствующий скрипт не заглючил, то вот копия
А какие результаты то?
Фотография yeputons с результатами: link
Congratulations to 7k+ and s-quark! Thanks to VK, a very nice contest!
Ура кф возобновил нормальную работу.
А нет не все, нельзя смотреть зарегистрированных на контест участников.
Вроде и это пофиксили.
Ура, трансляция будет нормальной! Просмотр кодов участников закрыли!
А значит ли это, что она может быть рейтинговой?
thought that tourist would have first place,congrats to winners and organizers for the great contest
VK Cup 2012, Финал (неофициальная онлайн-версия) — она будет рейтинговой? И если будет, то для обоих дивизионов, или только для первого?
Очевидно что не рейтинговый и вряд ли для див2!
Присоединяюсь к вопросу. Думаю, что будет нерейтинговой, но про это нигде явно не написано.
Congratulate to winners! This competition is really nice!I enjoyed it very much ^_^ And I'm very happy to take home a cool laptop.
Мне вот давно интересно — Alex_KPR стал уже официальным блоггером Codeforces или просто всегда оказывается в нужном месте в нужное время ? :-)
Я не могу утверждать, но этим можно объяснить, почему он не пишет контесты после cf#100.
А причём тут контесты?
Alex_KPR — официальный секс-символ Codeforces.
^3^Alex_KPR — независимое СМИ
The same problem set will be given in the unofficial VK final?
Of course, yes.
I think there are some problems with Codeforces system after the contest. When I submit an AC solution with time 0.4s, it turn to about 1s now :-s Anybody has the same situation ?
Самая быстрая отправка верного решения – 20 минут. Теперь я отчетливей представляю, на сколько читерят те, что в онлайн-соревнованиии отправляют за 2 и 3 минуты )
Я пробежал 1 км за 5 минут. Теперь я ясно представляю, как читерят те, кто бегут 100 метров за 10 секунд.
Я один не вижу аналогии между Я и полсотни чемпионов?
100 метров за 10 секунд бегут те самые полсотни чемпионов, только чуточку в другой дисциплине. Согласен, метафора не идеальна — но суть же ясна, правда?
А еще там задачи сильно сложнее, чем на среднем раунде.
Кэп, участники тоже не из второго дивизиона.
Еще раз: задачи сильно сложнее, чем на среднем (div.1) раунде. Поэтому нет совсем тупостей вида A-B (div2 A-D), да и рассортированы по сложности были случайно, поэтому сначала все читали более-менее все задачи.
Про коварную сортировку заданий – хорошее замечание, согласен. За что минусуют, не знаю. Наверное целились в меня, но промазали )
Вам будет интересно посмотреть результаты решения этих задач участниками второго дивизиона. Очень интересно, в каком читерстве вы обвиняете участников, которые сдают быстро легкие задачи? Прямо-таки напомнили.
Я внимательно смотрел отправки некоторых лидеров в тех codeforces-матчах, в которых участвовал. Бывали такие случаи, что код за эти три минуты можно было успеть только под диктовку напечатать. А если еще учесть факт использования 14 переменных...
Вы даже живьем ни одного из лидеров не видели, а уже так глубокомысленно рассуждаете... Вот Вам в компенсацию этого видео для ознакомления с тем, как они кодят (обратите внимание на направление взгляда и звуки клавиш).
P.S. Из-за компа ушел meret, сел и начал кодить другую задачу tomekkulczynski.
Примеры в студию. И да. По поводу успеть напечатать. Многие люди печатают очень быстро. Скажем yeputons печетает значительно быстрее меня. А tourist пишет QSort за 26(28?) секунд :)
Чтобы обсуждение было предметным — приведите конкретные номера посылок, которые вызывают у вас подозрение.
Если подозрительны они не только вам, вполне можно добиться штрафных санкций.
Если же нет — вероятно, вам объяснят, как именно можно придумать и написать такое решение за такое время.
В любом случае, будет какая-то польза.
А еще первая отправка верного решение — на 15й минуте. Но это все мелочи ;)
A very nice competition! I can't believe every finalist can have a laptop! Thanks to VK and congratulations to the winners!
А будут ли взломы?
Sorry to Interrupt, but will it have an editoral after the unoffical contest?
А будут ли смердженные результаты? Интересно было бы посмотреть на свое место в таблице онсайта. Можно, например, взять стоимости задач такие, какими они были на официальном раунде, чтобы из-за динамической разбалловки ничего не изменилось.
Ну ти можеш посчитать, сколько у тебя было б при стоимости задач, как на онсайте.
Что-то типа такого устроит?
Стоимости задач оставлены такими же, как на официальном раунде (каждый может считать, что эта таблица показывает его место в официальном раунде при условии, что он участвовал 50-м; так как ни по какой задаче нет 24 решений, то подобные построения корректны).
Крутые задачи, но все-же обидно что в Б не зашло |S|*26*log(N).
У меня на плюсах в дорешке зашло за ~3700
На java зашло
не могу придумать решения, где был бы множитель log(n). Даже интересно стало...
У меня нужно было проверить: есть-ли такая маска во входных данных. Делал бинпоиском по отсортированному массиву, поэтому и лог.
1904874
Ах да, у меня аналогично, только map, я уж забыл про этот log()... у меня прошло с большим запасом...
Ради интереса переписал за чистые O(|S| * 26 + 226) — работает за 520 мс. Но на контесте, конечно, такими оптимизациями заниматься — изврат.
Посылка
Там же должно получаться O(|S| * 26 + Q * (26 + log(|S|))), не?
Ну у меня еще сорт внутри того |S|*26 то есть |S|*26*log(26). А Q * (26 + log(|S|)) у меня нету, просто О(Q).
Кстати, а кто как делал Е?
Очевидно, что сумма a + b всегда равна n - 1. Перебираем вершину, которая не войдет в ответ, мысленно выкинем ее из графа, для каждой получившейся компоненты подсчитаем количество вершин в ней. Очевидно, что она целиком должна принадлежит одной компании, делить невыгодно.
Дальше простая квадратичная динамика. Суммарно решение за O(n2).
Заметим, что всегда можно сделать пару (1, N — 2). Т.е. всегда только одна вершина не будет содержать ресторана. Перебираем вершину, при удалении этой вершины граф разбивается на deg[v] компонент связности. Где deg[v] — степень вершины. Теперь посчитаем can[a] — можно ли выбрать из этих компонент некоторые так, чтобы суммарный размер был a. После этого can для каждого разбиения объединим. Это все посчитаем за O(N^2). Теперь для всех i, таких что can[i] = True в ответ добавляем пару (i, N — i — 1)
А с битсетами это вообще за 50мс проходит. Там бы, наверное, и 40000 успело.
Ну и какого черта я слил round3? :)
А разбор устраиваем здесь?)
У меня есть идея по А. Давайте будем отделять от каждой вершины вершину с любыми t ребрами, пока степени всех вершин не будут <= t. После этого для каждой вершины, степень которой deg(v) < t, добавим в другую долю фиктивную вершину и проведем в нее оставшиеся t-deg(v) ребер. После этого добавим в меньшую долю фиктивные вершины так, чтобы количество вершин в обеих долях было одинаково, и соединим фиктивные вершины ребрами так, чтобы степень всех вершин в графе стала равной t. После этого разобьем граф на t паросочей, "настоящие" ребра i-го паросоча назначаем i-ой компании.
а кто как решал D? особенно интересует решение Dmitry_Egorov, потому что оно короче моего в два раза.
Я сдал решение с деревом отрезков с прибавлением на отрезке арифметической прогрессии, это слишком задротно, да? :)
Можно за линию. Если перейти к массиву конечных разностей, а потом еще раз перейти к массиву конечных разностей, то арифм. прогрессию за О(1) можно прибавлять. А потом 2 раза перейдем к частичным суммам и получим настоящие значения.
Хм, даблпостов сейчас уже нет, зато появились даблправки при многократном нажатии на "Сохранить".
Я знаю решение этой проблемы — нажать на сохранить только раз. Ваш К.О.
Тестирую.
Маленькая проблема. Иногда ответ с сервера не приходит. Ваш -//-
При нажатии на "Cохранить" у меня за 3 секунды оно обновило.
Ну а у меня за 15 не обновило.
Thanks for the really great event. This was definitely one of the best onsite competitions I've been to.
Me too, VK is really the winner of the contest of contests. VK really make everyone happy in the event, including the participant like me that not performed well at the final round.
By the way, I found my name-card with red handle, but in fact I'm yellow. So I want to become red by the final round. But unfortunately I become more 'yellow' caused by mistakes in different problems. So it gives me a lesson: coding/thinking carefully (and maybe checking twice) is more important to the speed of coding.
Based on feedback about final I can only hope that next year VK would waive age restriction
Pavel Durov told us that they are not interested in giving first prizes to known hardened people like Petr, because it's not so interesting.
Well, currently it leaves tourist as huge favorit (althrough we can see, from this contest as well, that luck is a big factor in onsite tournaments). Now competitors are randomly divided by age: some tops are eligible, some not, and I see no real reason behind this
I don't understand what people's age has to do with their fame and "hardness" in terms of programming contests. If organizers don't want well known and strong people at the finals, why not to cut them off based on their skills? We have ratings here and at TopCoder, so let's ban all people who's rating (or its maximum value) is higher than some threshold?
IMO age correlation with "hardness" is far from 1. They can make the rule similar to ACM ICPC's (i.e. <=const VK CUP finals per person), or just allow participation only to the ones who never participated in any onsite (i.e. IOI, ACM ICPC finals, GCJ finals, topcoder oncite, facebook finals, etc.). This way is much more effective for getting rid of hardened people :) Though I doubt this (getting rid of hardened people) is a very good idea.
Anyway, this competition is a way for VK to look for new employees, and VK is interested in young (<=23yo) developers only. Don't ask me why: I cannot answer this question :)
Is there gonna be editorial for this contest or should I post solution for problem A here?
I also get accepted (without seeing your solution), and it turns out that our methods are similar. I just wonder how to prove the correctness.
OK, here you go.
It’s obvious that the answer can’t be smaller than the number of nodes with degree not divisible by t. To achieve this value, every node v must have between floor(deg[v]/t) and ceil(deg[v]/t) outgoing edges of each of t colors (deg[v] is the degree of node v). Let’s construct such coloring and prove its existence by induction alongside.
For t = 1 the result is obvious. For bigger t we find the set of edges to be painted with color t, delete this edges from the graph and continue the process for t-1. It’s easy to see that the final result will meet all the conditions. So why such set of edges for color t always exists?
To find it, we add edges from source to the nodes of the first part and from nodes of the second part to the sink with capacity ceil(deg[v]/t) and find max flow. Now we need to ensure that lower bound condition for the flow from (or to) each node is satisfied.
Let’s take a node v0 with flow less than [deg[v0]/t]. To increase the flow in that node, we need to find a path v0 -> u1 -> v1 -> … -> un -> vn, where nodes vi are from first part and ui from second, the edges in this path are in turn not-filled and filled with flow, and flow in node vn can be decreased (> [deg[vn]/t]). After that we just swap the flow between neighbouring edges.
To complete the proof, we need to show that such path always exists. Assume the opposite. Let V and U be the sets of nodes from respective parts reachable from v0 by given method (from vi we take all not-filled edges, from ui all filled). Flow in each node from U equals ceil(deg[ui]/t), otherwise we could increase the total flow. By assumption, flow in each vi is <= [deg[vi]/t] and at least for one node the inequality is strict.
Now if we count the total number of edges filled with flow between V and U in two ways — as edges starting from V, and as edges starting from U, then use inequalities listed above and the fact that [x] = floor(x) <= x <= ceil(x), we’ll get deg[V] > deg[U] for total degree of nodes. If we count the total number of edges not-filled with flow in the same manner, we’ll get deg[V] < deg[U]. This contradiction ends the proof.
Good job!
During the contest I coded the same solution without ensuring the lower bound conditions, and it failed as expected.
Actually every iteration can be viewed as the circulation problem since we have lower bounds on flow for some edges, I've got AC this way. It doesn't give any proof that the solution always exists, though.
I know a slightly different solution, which reduces the problem to Bipartite Graph Edge Coloring.
The problem is, given a Bipartite Graph, color every edge such that if two edges meet at a vertex, they are colored different. It can be proved that the minimum number of color required is ∆, the maximum degree of a vertex. The coloring can be found in O(VE).
For each vertex v in the original graph, we split it into ceil(deg(v) / t) vertex. The first trunc(deg(v) / t) vertex has degree t, while the last one has degree deg(v) mod t. The edges can be distribute to them arbitrary. The new graph has a maximum degree t, which means we can color the edges using t colors. The coloring on the new graph is the coloring we want.
http://www.siliconrus.com/2012/07/vk-cup/ я думаю что сообществу будет интересно прочитать эту статью, особенно ответ в конце
Раз уж поднялась тема — интересно узнать, когда планируется разослать футболки для топ200?
Пришла футболка:)