renatm

В данный момент проходит полуфинал чемпионата мира по программированию в Северо-Восточном регионе, куда входят почти все страны бывшего СССР. Текущие результаты здесь. Прошло 2 часа 20 минут из пяти часов, т.е. примерно половина контеста.

Лидируют одни из фаворитов - команда МГУ 1, с шестью сданными задачами. Наша команда ПГУ пока с тремя задачами на 53 месте. Сдают грязно, обе простые задачи B и H сдали со второй попытки, сейчас не могут сдать F - три неверных попытки. Но будем надеяться на лучшее. В прошлом году в финал проходили 12 команд.

UPD
2:32 В лидерах три команды с шестью задачами: Moscow SU 1, SPb IFMO 2, SPb IFMO 1. IFMO 1 - действующие чемпионы мира, долго возившиеся с задачей I (5 неверных попыток, до сих не сдана), за очень короткий промежуток сдали F, A и J.
2:39 Perm SU наконец-то сдали F, сейчас на 26 месте с 4 задачами.
2:46 Petrozavodsk SU 1 сдали J с первой попытки и вышли на 2 место.
3:07 Petrozavodsk SU 1 сдали I со второй попытки и вышли на 1 место. Сейчас 1 команда с семью задачами, 3 - с шестью, 12 - с пятью. Наши пермяки на 31-м месте с четырьмя.
3:30 полчаса до заморозки монитора. Тройка лидеров: Petrozavodsk SU 1, Moscow SU 1, SPb IFMO 1, все с семью задачами. Далее 6 команд с шестью задачами, и десять - с пятью. Perm SU до сих пор на 31-м месте с четырьмя. И даже не пытаются ничего сдать. Com'on, надо ещё хотя бы 3 задачи, чтобы пройти в финал!
4:00 монитор заморожен, но уже ясно, что ПГУ в финал не пройдёт.

У меня вопрос к моим френдам, разбирающимся в CS.

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

Стандартный метод решения состоит в следующем. Мы строим новый граф. В нём все рёбра имеют единичную длину. Вершины нового графа делятся на старые - соответствующие вершинам исходного графа, и новые - дополнительные. Если мы рассмотрим все возможные пути в новом графе, идущие из старой вершины в старую, и проходящие через 0 или более новых вершин, то эти пути должны взаимно однозначно соответствовать рёбрам исходного графа. Тогда для нахождения количества путей достаточно возвести матрицу смежности нового графа в степень, равную длине искомых путей.

Вопрос в том, как найти граф, содержащий минимальное количество дополнительных вершин? Есть ли какой-то эффективный алгоритм, или это NP-полная задача? Может у неё есть какое-то стандартное название?

Кто-нибудь знает, какая команда (или человек) победила сегодня в контесте на юве? Рейтинг. Просто интересно. Странное у них название. Обычно так нубы называются, а тут топовый игрок.

Мда, ну и качество услуг у провайдера УралСвязьИнформ. Больше суток не было доступа в Интернет! И судя по обсуждениям в теме Интернет на teron.ru - это массовая проблема.

Эх, совсем неграмотный стал :)

Что-то меня в последнее время прёт на ТопКодере. Несколько раз побивал свой старый рекорд, и наконец сегодня стал 1-м в div1 и впервые вошёл в топ5. К чему бы это? :)

Вопрос: как написать на C++ функцию int add(int a, int b) { ... }, которая будет возвращать сумму двух чисел (в том числе и отрицательных), не используя арифметические операторы, циклы, рекурсию и ассемблерные вставки?

Решение: http://forums.topcoder.com/?module=Message&messageID=1088156 :)

Вчера на снаркньюс прошёл первоапрельский контест "X-files". Необычность его была в том, что в условиях задач были указаны только имена входных и выходных параметров, ограничения на них, и самплы. Все остальные слова из условий были стёрты.

Поскольку задачи довольно прямолинейны, то проблем с пониманием как правило не возникало, но были и некоторые трудности. В задаче D как минимум двое моих знакомых запутались с тем, когда в ответ выводить 0, а когда -1. Надо было выводить 0, если нет решений, и -1 - если их бесконечно много.

У меня возникли трудности с задачей C. Минут 10-15 думал, что это за функция, пока не понял, что это НОК чисел от 1 до n. Потом засабмитил, и WA #1. Логичнее всего было бы предположить, что раз первый тест (почти) всегда совпадает с самплом, и у меня моё решение на сампле работает нормально => у них оно не работает на сампле => я не прописал входные и выходные файлы (как в итоге и оказалось). Но я почему-то решил, что первый тест - не сампл, и стал делать какие-то бессмысленные исправления и ресабмитить :) В итоге так и не сдал.

Ещё была ошибка в задаче A. Я начал писать её в самом начале, но получил WA, перечитал пару раз решение, и перешёл к следующим задачам. Но в конце контеста вернулся к ней, и нашёл ошибку в вычислении количества високосных лет, прошедших до данного года.

После окончания контеста меня сильно удивили результаты. Неужели возможно решить 5 задач за 9 минут (!), причём первую (самую сложную) за 4 минуты? Может Дмитрий Жуков решил "пошутить" над организаторами, или он действительно решал честно, и у него не было готовых решений до начала контеста? Как вы думаете?

Увидев у dfyz-а этот пост, тоже решил составить рейтинг по дуэлям со взаимными френдами в ЖЖ.
( Read more... )
Надеюсь, никого ни с кем не перепутал, и никого не обидел. Если кого-то забыл, то пишите.

Кто-нибудь из френдов-олимпиадников хочет поучаствовать со мной в контесте? Желательно, человек с достаточно высоким рейтингом :) На топкодерском форуме есть описание. Контест будет 18 января (завтра) с 11:30 до 15:30 по московскому времени, на spoj. Правила стандартные ACM, за исключением того, что команды состоят из двух человек, и можно решать параллельно с разных компьютеров. Общаться и распределять задачи будем через ICQ. Организаторы обещают приз 1000$ первой команде и 500$ второй. В прошлые годы были проблемы с падающей проверяющей системой и ошибками в условиях и тестах. Но в этом году все должно лучше, потому что контест будет на spoj, так что проверяющая система должна работать нормально, и объявление о контесте на топкодере дал желтый кодер, в отличие от зеленых в прошлые годы, так что качество задач должно быть лучше :)

Пару дней назад получил brown belt на JavaBlackBelt. Хороший сайт для изучения технологий, связанных с Java. Во-первых, изучать что-то новое интереснее, если ты можешь сразу проверить свои знания, сдав экзамен. Во-вторых, список тем в экзаменах помогает систематизировать знания. В-третьих, в самих вопросах часто содержатся полезные сведения.

А какие еще вы знаете хорошие сайты online сертификации, кроме brainbench.com и sql-ex.ru?

Из-за одной смешной ошибки в решении к 1000 я сегодня упал с 4-го места на 149. А ошибка была в следующей строке

if (onBoard(i+2*di[dir], j+2*dj[dir] && a[i+2*di[dir]][j+2*dj[dir]] == '.')) { 

Попробуйте найти :) Что самое странное, так это то что решение тем не менее прошло все сампл-тесты.
Наверное, надо на Java или C# переходить, там бы такое не скомпилировалось...

Вчера завершился третий и последний онлайн раунд Google Code Jam. Я занял 25 место, и вошел в число 500 человек, которые проходят в онсайт раунды. Полуфиналы будут отдельно проходить для трех регионов: Europe, Middle East, and Africa (EMEA); the Americas; и Asia Pacific. Пока нет официальной информации о том, сколько человек прошло из каждого региона, но по некоторым данным в наш полуфинал прошло 208 человек. В финал проходят 100 человек, по 20% из каждого региона. Таким образом, чтобы попасть в финал надо будет войти примерно в top 40. Полуфинал будет в октябре. Пока неизвестно, в какой офис Гугла меня отправят, но скорее всего в московский.

По поводу задач. В очередной раз убедился, что количество баллов за задачу слабо коррелирует со сложностью. По моему субъективному мнению, самой простой была задача C, за которую давалось больше всего баллов. В ней было дано поле размера M на N, состоящее из свободных и занятых клеток. Надо выбрать множество из свободных клеток, так, чтобы никакие две не были соседними по горизонтали или диагонали, и найти максимальный размер этого множества. В small input-е M и N были не более 10, в large - не более 80. Представим каждую свободную клетку в виде вершины графа, и проведем ребра между соседними по горизонтали и диагонали клетками. Теперь наша задача свелась к поиску максимального независимого множества вершин. В общем случае это NP-полная задача, но у нас граф двудольный (доля вершины зависит от четности столбца), и поэтому ответ по известной теореме равен количеству вершин минус размер максимального паросочетания. В итоге, решение свелось к построению графа, и поиску максимального паросочетания, что в реализации проще остальных задач. Правда, во время контеста я из-за какого-то странного помутнения рассудка не заметил это сведение к графу, и поэтому решил только small input (экспоненциальной динамикой). Так что на полуфинале надо будет читать условия, начиная с самых дорогих задач, чтобы было больше времени на придумывание решения.

Тут статистика по странам: http://www.go-hero.net/jam/regions
Здесь рейтинг с топкодерскими никами: http://zibada.xgm.ru/gcj/round3.html

Три или четыре раза пытался пройти, и всякий раз набирал набирал 8 из 10. Потом выпил пива и прошел с 1 раза :)

Занял 87 место и прошел в следующий раунд.
Интересно, у меня не могут снять задачу C small за прекалк вручную с помощью Windows-калькулятора? :)

Квалификационный раунд Google Code Jam начался сегодня в 5 утра по пермскому времени и идет 24 часа. Если вдруг кто-нибудь забыл о нем, то у вас еще есть время поучаствовать.
Я начал решать с самого начала, чтобы побороться за места на верхушке рейтинга, что у меня вполне получилось. Я даже сделал первый акцепнутый сабмит :) Чтобы пройти в следующий раунд, нужно чтобы хотя бы один из трех large output-ов оказался верным.
Заодно я узнал, как чувствуют себя москвичи и питерцы, участвуя в утренних SRM-ах. Вполне нормально они себя чувствуют, даже спать не хотелось :) Рано утром даже лучше соображается, потому что голова еще ничем посторонним не забита.

Чуть-чуть до 500 не хватило...


Update. Уже не актуально, теперь надо 600 :)

Итоги:
- 17 место, 3-й SRM подряд удается защитить свой значок таргета.
- За счет неудачного выступления marek.cygan, я переместился с 10 на 9 место в общем рейтинге.
- Впервые с июля прошлого года сделал удачный challenge.
Осталось узнать, что такое min-cost flow и с чем его едят, а также как к нему свести сегодняшнюю 1000. Но это после футбола :)

via andrew_belkin

80 words

Русский

79 words

English

http://researcher.net78.net/math/


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

Вывод: математику я позабыл... :)

PS Сегодня еще поучаствовал в Kazakhstan Contest 2 от Артема Игликова. Задачи были интересные, но плохо, что участников было очень мало.