renatm

Вчера закончился пятый раунд зимней серии соревнований по программированию от SnarkNews. Я занял одиннадцатое место, что дало мне седьмое место в итоговом рейтинге по всем пяти раундам. Я мог бы занять более высокое место, если бы сдал задачу F (условия задач), но у меня почему-то был Wrong Answer на четвёртом тесте. Я много раз перечитывал своё решение во время контеста и после него, но так и не смог найти ошибку. Может кто-нибудь подскажет?
( Проблема решена, спасибо kit1980ukrCollapse )

Написал простую игру по мотивам ТопКодера: http://tcxchange.appspot.com/ Что-то вроде биржы топкодеров, где стоимость акций пропорциональна exp(рейтинг/1000). Сегодня прошёл первый СРМ, и уже сформировался топ10 трейдеров. Багов пока замечено не было, за исключением того, что изредка при запросах к хранилищу данных выбрасывается DatastoreTimeoutException.

Я не дружу с английской грамматикой, так что если найдёте ошибки, то пишите. Также принимаются советы, как улучшить внешний вид сайта.

В данный момент проходит полуфинал чемпионата мира по программированию в Северо-Восточном регионе, куда входят почти все страны бывшего СССР. Текущие результаты здесь. Прошло 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 минуты? Может Дмитрий Жуков решил "пошутить" над организаторами, или он действительно решал честно, и у него не было готовых решений до начала контеста? Как вы думаете?