(no subject)
burunduk
burunduk1
У меня после Петрозаводских сборов появилось умение решать следующую задачу:
Есть K запросов вида
1) Добавить ребро в граф
2) Удалить ребро из графа
3) Сказать, сколько мостов в графе.
В графе N вершин.

Тогда я в Offline умею решать эту задачу за O((N+K)log(N+K)).

Кто-нибудь может дать ссылки на уже придуманные методы за такое же или лучшее время?)
Или рассказать историю своих отношений с этой задачей в стиле "слышал от такого-то, читал там-то"?

P.S. Интересно, стоит ли...

IOI. Конец.
burunduk
burunduk1
Сегодня будет награждение. И closing-party!!!
А позавчера был последний тур. А вчера мы ездили на Ниагару и вечером построили башенку из трех уровней!!! (И не только ;-)) Скоро будут фотки.

У нашей сборной ожидается 2 золота (Миша + Серега) и 2 серебра (Рома + Глеб). Упорядочились все так: Миша, Серега, Рома, Глеб. При этом разрыв от первого до последнего всего 12 баллов... 12 баллов!!! Если честно, мне в какой-то момент тех, кто придумал расценку задач, очень хотелось придушить. Да и сейчас, я так подумал, все еще хочется.

Про то, что наши делали на втором туре:
Read more...Collapse )
Tags: ,

IOI
burunduk
burunduk1
Начался 2-й тур 22-й IOI...
Начался он в 16:30 по московскому времени.
http://www.ioi2010.org/scoreboard2/scoreboard.html
Условия задач на русском: http://acm.spbgu.ru/ioi-2010-day2/
Со стандартной задачей-незадачей наша сборная справилась за первые 10-20 минут.
Read more...Collapse )
Tags: ,

IOI 2010
burunduk
burunduk1
В этом году (вроде бы первый раз за историю олимпиады!) результаты IOI доступны еще по ходу соревнования.
http://www.ioi2010.org/scoreboard/scoreboard.html
Участники результаты тоже знают, но только свои :-)

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

Условия задач тоже всем доступны. Ссылка сверху на http://www.ioi2010.org/scoreboard/scoreboard.html

Собственно про первый тур:
Read moreCollapse )
Tags: ,

Google CodeJam
burunduk
burunduk1
Аккуратно, очень длинный пост. Ибо много всего случилось, хотелось выговориться :)

Когда я планировал лето, получалось примерно так:

весна - 18 июня = сессия + работа
19 июня - 02 июля = школьные сборы
недельку в Питере с Анькой
09 июля - 29 июля = ЛКШ
работа + midas (до 13-го августа)
ну и ежегодный повод прогулять 1-е сентября - Петрозаводские сборы

Была еще мысль, что очень хорошо бы попасть на IOI в Канаде :) об этом оставалось только поговорить с Владимиром Михайловичем. Поговорить, конечно, на сборах.

Все было +- спланировано.

И вот, однажды, 12-го июня, в Google CodeJam Online Round 3... Неожиданно для себя я не увидел в задачах ничего сложного, не наделал черезмерное количество сложных багов и, получив последний АС на последней минуте, вернее за 12 секунд до конца (*dance-dance*), обошел немножко Славу (winger, 2-е место)... В частности, я прошел в финал :-)

Со Славой, кстати, мы сейчас вместе работаем в Яндексе :) Вместе - в смысле совсем вместе). У Славы с финалом своя история с гораздо менее удачным концом, но об этом позже...

Ну и вот он, CheckPoint №1. 18-е июня. Ночь не спал, готовился, с утра мне предложили отказаться от тройки по физике (выбор вида "закрыть сессию вовремя, или побороться за 4 в сентябре?"), я согласился на побороться :-) Вечером на работе Гоша Корнеев моему не выспавшемуся мозгу устроил "Level Next". Разбирал и правил при мне мой код, на что хватало сил - я правил сам, но шестеренки в голове уже часто прокручивались в холостую, без контакта с реальностью, организм требовал еды и сна, я его посылал, но, естественно, легче от этого не становилось.

19-го я проснулся в Малоярославце "бодрым и полным сил"! Потекла обычная сборовская жизнь (в этом году преподавателей на сборах было меньше, чем обычно = 5.5 человек вместо 9.5 в прошлом году, так что потекла она быстро... :-) И вот, примерно 22-го июня, после разговора с Владимиром Михайловичем, после которого оказалось, что (ДА!!!) в Канаду я еду, пришло ОСОЗНАНИЕ:
Google 30-го июля, IOI 14-го августа. Мне нужно делать 2 визы. Ирландскую делают 3 рабочих дня, Канадскую 3 недели :-) Обе визы нужно успеть сделать до 30-го июля. Паспорт только один, параллелить нельзя. Я сам лично в Москве появиться смогу только с очень большим трудом (см. расписание). Пригласительных писем еще нет... Короче, я весь вечер радовался перспективам :-)

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

Время шло, канадская виза делалась, надежда на Иралндию медленно таяла. Числа 20-го июля она упала до нуля, я уверовал в то, что остаюсь на последний день + ночь, пригласил Аньку на конец смены, на 3 дня (26-28), выбрал ей билеты, купили...

Но надежду на то, что я таки поеду на финал не терял Андрей! =) (Сергеевич Лопатин)
Он меня потормашил, чтобы я позвонил и в PonyExpress, и в консульство (что интересно, ни туда, ни туда я не дозвонился), а в пятницу (23 июля) утром от Pony само по себе пришло письмо "Готово, прихидите, забирайте".

Тут нужно рассказать, как работают Pony и Ирландское консульство. Забрать документы из Pony, самое раннее, можно в день "Готово, прихидите, забирайте" в 12:00. Ирландское принимает по будням с 9:30 до 12:30.

Пришлось ждать до понедельника... А это 26-е, а визу делают 3 дня, а лететь нужно 29-го. А могут за 3 дня и не успеть... А еще на визу нужно передать документы в Москву из Судиславля, до 26-го... И договориться с кем-нибудь, кто 26-го мой паспорт заберет из канадского, отнесет в Ирландское... А может уже не быть билетов, или Google не успеет оперативно купить, а вообще как попасть в Москву из Судиславля к нужному времени? Последние вечер и ночь в ЛКШ (так сделал Серега Рогуленко) пропускать вообще ни капельки не хотелось :-)

Удача и добрые люди №1:
Андрей подсказал позвонить Пете Митричеву, Петя как оказалось улетал 26-го (в понедельник) днем, но перед этим успевал и согласился помочь забрать-подать документы :-) Такой приятной неожиданности я почему-то никак не ждал, дальше пошло бодрее) (Петя, спасибо тебе!)

Удача и добрые люди №2:
Рома из группы D уезжал из ЛКШ раньше (возможно именно поэтому в последний момент на сутки перенесли посвят :-D )... Как раз в воскресенье, как раз в Москву. Спросил, Рома согласился помочь, его родители по приезду в Москву отдали все мои бумажке Пете.

Я тем временем нашел билет (вернее я не нашел, нашел Андрей :), на 19:10, 29-го. Написал об этом Google-у, они ответили, что слишком дорого, есть вот такой (время вылета 16:10). На 16:10 я уже не успевал с автобусов, но как бы выбирать не приходилось...)

Удача и добрые люди №3:
Тем временем к нам в ЛКШ, в гости приехала Елена Владимировна... Приехала на машине... (Спасибо, Елена Владимировна!!!)

Из ЛКШ мы с Е.В. и Ромой Андреевым выезжали в 8:30, планировали в 14:10 у ст.м.Медведково встретиться с Ирой Митричевой, которая с утра успеет забрать документы из посольства (Спасибо, Ира, про шоколадку все помню =), забрать мой паспорт и прямиком в аэропорт (благо Google билет на 16:10 уже купил)...

Я забыл пройти электронную регистрацию на рейс... Позвонил Андрею, спросить что делать, через некоторое время Андрей перезвонил рассказать, что (Ахтунг!) Google аннулировал билет. Вот как оно бывает... Визу сделать успели, до Москвы чудом добраться - легко, Ира, Петя, Рома помогли по полной... А билетов уже нет.

О том, как Елена Владимировна по пробкам, ровно в 14:10 (как планировали) и к 15:15 (опять же, на это время и закладывались) привезла меня сперва к ст.м.Медведково, потом к Шереметьево-E рассказывать не буду... 2-3 раза Елена Владимировна (я даже не знаю, в шутку ли?) предлагала уже повернуть наконец к вокзалу и не мучиться :-)

А вот, конец феерического шоу 15:15, мы с Е.В. вбегаем в аэропорт покупать билеты (тем временем Андрей звонит или пишет Пете вопрос "Почему так?"), билетов таких нет, таких нет, в итоге оказалось, что есть на ровно тот рейс, что был у меня забронирован от Google-а :-) (девушка на кассе после слов "посмотрите такой же как в аннулированной брони" сказала, что так не умеет, я звонил Андрею, Андрей лазил из автобуса Судиславль-Москва в инет, с N-й попытки залез, продиктовал точные номера рейсов)...

Действие K+1-ое "Денег нет!"
Билет стоит 37 000, у нас на руках всего 30 000 налом, с карточки Е.В. деньги принять не могут... Е.В. сперва узнала, что 2 ближайших не работают (не с ходу, конечно, минуты за 2), потом мне были выданы карточки с кодом, я побежал в соседний терминал, нашел банкомат, вернулся с деньгами :-) Регистрация на 16:10 уже закончилось, но их предупредили, что "Я уже бегу!", в общем кончилось все хорошо, я попрощался с Еленой Владимировной, задолжал ей не помню сколько (надо бы вспомнить :-[) денег, сел в самолет. Перед вылетом успел позвонить Петя, спросить "Получилось?" Получилось! :-)))

Петя договорился о том, что меня встретят, проверил, что с отелем той же баги (аннулировали ли?) нет.

Дальше был долгожданный сон в самолете.
Потом долгожданный сон в Париже в аэропорту.
Потом опять долгожданный сон в самолете.
Потом долгожданный сон в машине того, кто меня встретил.
Потом долгожданный сон уже в отеле...

И вот оно, утро перед соревнованием, я, почти выспавшийся (-2 прошлых ночи в ЛКШ, зато почти всю дорогу :), прихожу и... и не успеваю за последние 40 минут отдебажить простейший геом (Аня Кашкина уже подтврдила, что простейший :-). Поэтому всего лишь 3-е место ;-)

Хочется сказать "Спасибо!!!" всем людям (вас очень много!), кто помогал мне все-таки попасть на финал и, если не победить, то зажечь... На 4+, по-моему, я справился ;-)

Final Scoreboard: http://code.google.com/codejam/contest/scoreboard?c=801485#

Но на этом еще не все!
Эпилог:
Отель (я не догадался проверить) был у меня до 31-го июля, а рейс 1-го (рейс именно тот, который предлагал Google, так что ХМ... :) Отель я продлил (-79EURO). Lisandra сказала, что эти деньги можно записать на Google, но в отеле объяснили, что без бумаг, с устного согласия, ничего не смогут, ну и пусть. Зато согласились 1-го августа в 6:00 сделать завтрак и заказали такси в аэропорт :-)

Я всем написал (в частности Гоше Корнееву, который сразу предложил в понедельник в 12:00 встретиться в офисе), что 1-го августа вечером уже в Питере... И вот, в Париже (я с пересадкой в Париже летел) я прихожу к своему gate-у и вижу "Рейс Париж-Москва". МОСКВА! (Куда я смотрел до этого? :-) Делать нечего, купил местного инета, залез на rzd.ru

[begin Про rzd]
Это АЦКИЙ ОТСТОЙ!!! Бесит. Сколько раз не пользовался, бесит.
Могу предложить всем, кто не пробовал, попробовать http://transport.marshruty.ru/
Там хотя бы нет аццких тормозов, аццки удобного интерфейса и того, что смотреть стоимости билетов на "все поезда МОСКВА-ПИТЕР" можно только по очереди. Для меня пока есть один минус сайта - найти билеты я на нем могу, а вот купить не получается :(
А еще на rzd.ru есть (об этом я узнал в Париже) две фичи. (1) КУПЕ, тип вагона И - что это? почему я не могу купить на него билет? (2) КУПЕ, тип вагона МЖ rzd.ru говорит "Ошибка, неправильно указан МЖ".
[end Про rzd]

Итого через 20 минут я узнал, что в Питер из Москвы в воскресенье вечером остались билеты всего на один поезд дешевле 4 000 рублей. (С чего бы это?)
Поезд отправляется в 23:00, самолет прибывает в 21:45, почему бы не попробовать? :-D
(Сейчас я уже в Питере, через 15 минут встреча с Гошей ;-)

Купил билет на 23:00 (с Ленинградского), купил билет на аэроэкспресс из аэропорта на 22:00 - 22:35 (Шереметьево - Белорусский вокзал). Отличный план? А то!

Часть последняя, после которой мне было Х-О-Р-О-Ш-О...
Шереметьево, 21:45, самолет прилетел вовремя. Я бегом впереди всех выбегаю оттуда, бегу к паспортному контролю... Добегаю.
Там пусто.
Вообще никого нет.
Прошел паспортный аккуратненько так.
Дальше тоже никого нет.
Прошел через металлоискатель.
А вот дальше есть. Закрытая дверь. Постучался, ноль эмоций. Сзади уже собралась толпа, все спрашиваю "Как оно? Шансы есть?", через пару минут решив, что шансов таки нет, ушли искать в другое место. Нашли! "О Шереметьево! Fuck мой мозг... Ну кто так делает? :-D" Нужно было свернуть не по первой стрелочке "Паспортный контроль", а по такой же через 20 метров.
На часах 21:55, думаю "№;%№;%!!!". Попросил очередь, меня пропустили, пожелали удачи :-) Далее сцена "Никого". Бегу по указателям "Аэроэкспресс", думаю о том, что "Пол скользкий, а на мне шлепки, может снять? У меня электронный билет на Аэроэкспресс не распечатан, пустят ли? А может быть я все-таки успею?"
Далее я сделал стратегически верный ход, когда указатели кончились, вместо того, чтобы по инерции побежать вперед спросил у (единственный человек встреченный мной в аэропорту Шереметьево, признаюсь, очень вовремя) сидящей и чего-то ждущей девушке "А где?". Девушка сказала, "Вам выше нужно подняться". Сам бы не догадался :-(
Далее смотрю на часы "22:00". Ускорение вылетаю на платформу, турникетов, которых я боялся нет. Двери поезда закрыты. На платформе стоит дядя в форме, спрашиваю "А как?" говорит "Провести рукой :)". Провожу, двери закрываются, поезд трогается через 3 секунды. ФУХ!!!

Через 5 минут пришла контролерша, спросила билет, я рассказал свою историю, она объяснила, что достаточно чудо-знака (который дают после покупки билета, обычно печатают). Открыл ноут, там оставалось 10 минут зарядки, на экране был тот самый чудо-знак, просканила прямо с экрана :-) Всё good.

Оставалось только купить карточку в Московское метро. Опять повезло, я смог обогнать всех пассажирова аэроэкспресса и пройти первым, т.е. без очереди.
И доехать-добежать-доехать-добежать до своего поезда 23:00. Добежал. Запас = 2 минуты.

С утра пришел в офис... встретил Ваню Метельского, оказалось, пока я был "в отпуске" Ваня устроился в Питере в Яндекс, работает с нами (Гоша, Слава, я). Сейчас сидит рядом, что-то кодит :-) Да, живой Ваня Метельский, в Питере, в Яндексе, со мной в одном офисе :) А я думал, после такой дороги удивляться уже не придется... А вот )

КОНЕЦ.

P.P.S. ЛКШ... Как там хорошо :-) Только мало... И меня, и ЛКШ.
Tags:

Ночное
burunduk
burunduk1
Есть такая вот задача:
http://acmp.ru/?main=task&id_task=336
Одна из фишек сайта - можно минимизировать длину кода и получать удовольствие :)
http://acmp.ru/index.asp?main=bstatus&id_t=336
Мне сейчас не хватает 5 байт... Может, вы умеете лучше? ;-)


#include <fstream>
std::ifstream I("input.txt");
int x, a, c;
main()
{
  while (c = I.get() + 1)
    c & 1 ? a += ++x > a : x ? x-- : a++;
  std::ofstream("output.txt") << a + 1;
}

(no subject)
burunduk
burunduk1
Недавно начал (не прошло и N лет :) разбираться в теории сложности, возник мучающий меня уже пару дней вопрос:

Есть понятия NP-полноты.
http://ru.wikipedia.org/wiki/NP-полная_задача
Формально оно везде дано через "сводимость по Карпу".

Но хочется пользоваться другим определением:
Задача A из класса NP NP-полна iff {если она разрешима за полином, то любая задача из NP тоже разрешима за полином}.

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

Тем не менее это, конечно, не есть сведение по Карпу.

А вопрос - равносильны ли эти два определения и как это доказывается :) Подскажите, плиз.

(no subject)
burunduk
burunduk1
Сегодня присутствовал на лекции по биоинформатике... Давно звали сходить, посмотреть, что же там рассказывают =) Посмотреть, определенно нужно было, чтобы потом зря не переживать, что пропустил в жизни что-то очень важное.

На перерыве, не выдержал, ушел. Когда уходил, посоветовали посмотреть вот это: http://www.youtube.com/watch?v=DZsWKM3KUxA
Какая-то схожесть таки имеется :)

P.S. Странно так долго не писать и вдруг породить такой пост :)

ACM World Finals
burunduk
burunduk1
Завтра финал... )
Tags:

Сессия
burunduk
burunduk1
Вот и счастье наступило. Можно жить дальше :)
Уже не в первый раз повезло + большое спасибо Сергею Витальевичу )
Ощущение, как будто наконец вытащили из под воды и дали подышать =)
До этого как-то плохо было. Последние часы перед экзаменом проводил себе шокотерапию мозга) Час гулял по холоду, слушая зацикленную "Сибирь" Пилота. Ооочень кульная песня :-D

Я еще не закрылся. Остается английский. Но с ним вопрос уже почти решился...

Я так понимаю, теперь на два месяца вперед со мной всё ясно Япония-Питер-Москва-Питер-Шотозеро-Питер-Новосибирск-Питер-Швеция-Финал-Золото))) =)
Это если географически.
Зато по жизни вопросов уйма, все интересные. Где жить? Как перевестись на матобес? Чему, как и когда учиться? Чему, как и когда учить детей? Где же танцевать? и с кем? и еще несколько ????

?

Log in

No account? Create an account