| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
Здравствуйте Дамы и Господа! В 11-00 19 июня (т.е. в воскресенье;) состоится отборочный раунд на финальный раунд соревнования "Russian Code Cup 2011". (Извините за тавтологию;) В финал выйдет всего 50 человек, т.е. конкурс будет достаточно серьёзный. (50 из 600;)
Good luck and have fun!
P.S.: Сайт - russiancodecup.ru. Там же Вы можете найти правила.
Вчера было написано "заказ будет отправлен автоматически 18 июня"
Хотя теперь с ужасом думаю о том что придётся на почту тащиться, если футболка для жены всё же дойдёт... %)
http://codeforces.me/blog/entry/2161#comment-43968
А я со своей стороны думаю что IT-шнику жениться на IT-шнице тоже опасно... ;-)
А вообще, если IT-шникам вступать в брак, то я бы считал продуктивной идеей если это будет брак программиста и тестера... ;-)
Хороший тестировщик - это очень-очень ценно и иногда его очень-очень трудно найти... А тут он вот, под рукой... ;-)
UPD. Увидела новую тему, прощу прощения за комментарий сюда. =)
Просто иногда интересно общаться с профессионалами из других областей, а не из своей собственной, где в общем всё знаешь...
Вот мудрый Romka вообще не предъявляет никаких требований, и уже без 5 минут счастливый муж. Лучше начать с того, что сам можешь предложить ;)
==========================================
Ага, я так и представляю картину -- сидит себе девушка, думает, пора замуж. Заходит на CF и начинает выбирать... "Тааак, у этого что-то мало контестов выигранных, этот вообще в топ-10 не был, этот то красный, то нет, этот на <language1> пишет, а не на <language2> -- зачем мне такой муж... М-да, похоже, лучшая кандидатура -- tourist. Где тут личные сообщения..."
Ну конечно же я говорю не о контестах и рейтингах, для семейной жизни это как раз не так важно. Самые счастливые семьи - такие, где каждый думает прежде о супруге, а не о себе. Отсюда и "что я могу дать будущему мужу/жене" вместо "каким критериям должен соответствовать будущий супруг, чтобы угодить мне".
Хотя я ей порекомендовал для детских конкурсов заказывать футболки в качестве призов ;-)
Сейчас там ничего уже не написано
Скорее всего как обычно - кому-то хорошо, а кому-то плохо... :-(
Всё же надеюсь что как можно больше из прошедших в отбор смогут принять участие... Чтоб дух соревнования витал... %)
Однако поскольку RussianCodeCup не единственное соревнование, тут важно чтоб ещё время не слишком пересекалось с другими (в т.ч. международными) - или наоборот, чтобы было в один уикэнд с чем-то ещё - а у тех свои заботы, т.к. часовые пояса и время экзаменов в разных странах разное...
Ну, надеюсь, впрочем, что вам обоим (и всем достойным студентам) удастся себя отлично проявить и на соревновании и на экзамене!
cout << p[k] << "\n"; // WA 2
printf("%.12f\n", p[k]); // Accepted
Не понимаю, зачем так сделано...
Кстати, в D палево в 10 тесте (если, конечно, это не какая-то магия у меня).
Там как будто бы после самого теста идёт какой-то мусор - поэтому у меня был RE на 10 тесте (я обычно с мультитестом пишу решения).
Жюри я писал об этом давно, они никак не отреагировали.
Угу, только что.
ОК, понятно, в следующий раз клары к жюри надо писать сюда :-D
Такими темпами Petr не пройдет отбор...UPD. Хотя, пройдет, там 50 человек отбирают, а не 25.
D я решал тернаркой. Единственная фича – это разбить на отрезки, где ниточка переходит через вершину. Тогда утверждается, что функция выпуклая и можно тернарить.
Задача F – баян. Это задача C из Yandex.Algorithm 2011 Round 2 http://codeforces.me/contest/86/problem/C Решается динамикой по бору.
Вот. А по поводу D - можно как-нибудь доказать это утверждение, что ли? Тоже думал, что можно хитро разбить на отрезки, но так и не придумал как.
На интервалах, которые мы берем, как раз и складываем выпуклые вниз функции.
-\/--------
+
------\/--
=
-\/---\/--
или я чего-то не понимаю?
Выпуклая вниз функция должна лежать ниже любой своей хорды (можно принять это за определение, если не требовать гладкости).
"утверждается что функция выпуклая " - видимо потому что тогда у каждой отдельной гирлянды производная длины монотонна. Если визуально посмотреть - да, чем ближе к перпендикуляру, тем модуль меньше, притом с одной стороны она с минусом, с другой - с плюсом.
http://codeforces.me/blog/entry/2028 (задача С)
Какого лешего на двух турнирах с интервалом в 3 недели в решающей стадии отбора одна и та же задача?
К сожалению, всякое бывает.
Кстати, заметил тогда, что Вы прошли, но не участвовали...
А задачи (включая F ;) ) хорошие были, авторам спасибо.
D - очевидно. Рассматриваем все углы, в которых какая-то из гирлянд меняет сторону, на которую она прикрепляется. Их будет примерно 30*30 (число гирлянд на число сторон). Сортируем эти углы. Для каждого промежутка между соседними углами каждая гирлянда прикрепляется к одной и той же стороне. Обсуждаемая в задаче сумма расстояний есть сумма выпуклых функций, поэтому на каждом такой промежутке можно тернарным поиском найти минимум. Получается 30*30*(глубина поиска)*(время вычисления функции).
Мне не понравился TL =( Пришлось буквально подгонять число итераций терн. поиска и оптимизировать процесс вычисления функции.
Они все выпуклы вниз, значит, их сумма тоже выпукла вниз.
Если этот факт неочевиден, можно его переформулировать: у них у всех втрая производная положительна, значит и у суммы вторая производная положительна, поскольку производная суммы - это сумма производных.
а) тренировать, тренировать и ещё раз тренировать...
б) иметь под рукой наборчик оттестированных полезняшек для работы с углами, линиями и отрезками... ;-)
Я когда покорректирую своё решение, точно скажу, но вроде её можно было решать даже особо не разбираясь в глубоких методах вычмата: сумма длинн гирлянд это ж функция от угла поворота, количество минимумов у неё может быть конечно больше одного, но поскольку мы можем сделать о-о-очень много вычислений её за отведённые 2 секунды (даже на Java, хы-хы), то способов найти этот минимум можно придумать кучу... В том числе простых... Интересно не пробовал ли кто сужающийся случайный поиск... Вдруг удалось... ;-)
В геморной D у меня вообще тупой баг - забыл файлы отключить, так бы с первого раза сдал.
в первой задаче думал, что ранее необрушенный мост падает с вероятностью 1/2 при каждом проходе по нему, а не при первом.
после потраченного часа и +4 за это продолжать участие смысла уже не было.
В общем, расскажите, как решать А =_=
т.е. dn = dn - 1 + 1 + (N - n)
я промоделировал численно и получил
2 1.4998020000
3 3.6233720000
4 6.4848570000
5 10.1641200000
6 14.7143000000
7 20.2563320000
8 26.6997540000
9 34.2892800000
10 42.5786450000
11 51.8425590000
12 62.2131900000
13 73.8046050000
14 86.1391800000
15 99.6078180000
16 113.9635360000
17 129.1995770000
18 145.3372650000
19 162.4464510000
20 181.2334060000
мб, я конечно, в нем накосячил... или rand() настолько не случаен...
double sum=0.;
FOR(a,1,1000000)
{
CLR(sta);
double t=0.;
while(1)
{
bool flag=false;
FOR(b,1,n)
if (b==n) flag=true;
else if (sta[b]) t+=1.;
else if (rand()&1) t+=1.;
else
{
t+=1.;
sta[b]=true;
break;
}
if (flag) break;
}
sum += t;
}
WR("%d %.10lf\n", n, sum/1000000);
Ладно, спасибо всем, это было неверное понимание условия.
С таким пониманием она тоже решается - надо считать dij= матожидание числа ходов до i, если мы при попадании в i сразу телепортируемся в 1 и хотим повторить такой процесс j раз. Тогда ответ - это dn1, а dij = 0.5j(di - 1j + j) + (1 - 0.5j)(di - 1j + 1 + j + 1). Я очень удивился, когда оно не прокатило, и думал, что проблемы с точностью. К сожалению, я догадался перечитать условие далеко не сразу :(
А когда не зашло - забил на эту задачу.
кстати, моделирование при верном понимании условия выдает
2 1.4998020000
3 3.5000770000
4 5.9998750000
5 8.9999670000
6 12.5001420000
7 16.5003380000
8 20.9999780000
9 26.0002160000
10 31.4993180000
11 37.5005400000
12 43.9989720000
13 51.0013810000
14 58.4970710000
15 66.5009830000
16 75.0001140000
17 83.9999140000
18 93.4984590000
19 103.4991060000
20 114.0027000000
закономерность видна невооруженным глазом
UPD. но при верном понимании условия моделирование, конечно же, не нужно...
1) "... разваливается, если на него ступает участник"
2) "... количество мостов, которое понадобится пройти участнику..."
Получается, что по первому пункту мост рушится, если по нему только начать идти (путь нулевой длины), а по второму - мы проходим весь мост и лишь затем падаем (сопоставлено с примером из условия).
0.5*(f(n-1) + 1) /*прошли мост удачно*/
+ 0.5*(f(n-1) + n) /*упали, вернулись, прошли еще n-1 мостов*/
Я неверно понял условие и решал далеко не простую задачу. Поскольку все остальные сдавали задачу не задумываясь, данное слово можно списать на эмоции.
Кстати, мне либо кажется в силу недостатка знаний, либо так и есть - но по-моему задачи "на вероятности" на топкодере (и в данном тоже случае) обычно в общем-то к теор-веру не относятся по существу, а являются реально задачками на ДП в которых собственно вся суть в том чтобы уловить рекуррентное соотношение между матожиданиями или вероятностями... По крайней мере всё что я про лису Чиль встречал именно такое было...
Впрочем с ДП у меня плохо как и со всем остальным %)
А вот задач именно на какие-то вероятностные фокусы, нюансы, парадоксы, распределения, вариации - ни разу...
Параметры: текущее число, сколько единичек осталось, сколько максимум можно взять.
Если берем i единичек то число x меняем на (x-i)/10.
Отсечение заключается в том что i%10 == x%10.
но если использовать ленивую динамику и map то может пройдет, состояний то не так много
Состояние - префикс числа x и сколько единичек осталось, а храним в этом состоянии мин. число слогаемых
У Егора свой репозиторий mercurial , там всё есть :)
Ну потому что у эллипсоидов такой полином, что на практике никто им не пользуется и все пишут симплекс-метод.
На практике симплекс-метод пишут только авторы библиотек.
Но, кажется, эта задача не должна влиять на прошедшие в финал команды. Или всё же влияла?
Я имею в виду, что те команды, которые могут написать симплекс-метод, скорее всего смогут написать большинство остальных задач, достаточных для прохождения в следующий раунд.
В задачах на паросочетание или поток обычно дают достаточно большие ограничения, чтобы самописный симлекс-метод не успел. Но если в графе 50 вершин и рёбер - то можно и с его помощью сдать. Ну или на каких-нибудь gcj пользоваться библиотеками, в которых в симплекс-методе реализована куча отсечек.
Тогда уж сразу использовать специализированные solver'ы. Но у них внутри такой ад, что это решение тяжело назвать простым.
P.S. код
Мое решение по Е получает Wrong Answer test 35. Скачал тесты - моя программа проходит этот тест. Кто-нибудь может подсказать в чем дело?
Ссылка на решение:http://pastebin.com/tBh3PfRP
Даже short получал мемлим, легко посчитать почему.
Думаю, проблема не в типе, ведь возвращается всегда или 1, или -2.
Я не спорю, что тест подобрать можно(хотя ваш тест не соответствует, как минимум, условию задачи). Предположим, что авторы даже предугадали такой баг. Тема поднималась не из-за этого - на тесте 35 локально моя программа выдает верный результат. Я понимаю, что я ошибся. Меня просто интересует, в чем причина разных вердиктов на моей машине и на стороне сервера.
UPD. Тепрь ваш тест соответствует условию, но результат моей программы - Impossible.
С TCO вышло хуже, разговоры соседок по палате о том, кто у кого от чего умер, явно не способствуют мыслительной деятельности :)
Делаю так:
1) Строю Бор, считаю суффиксные ссылки для всех вершин.
2) Пускаю динамику по двум параметрам [текущая длина][вершина бора]
Переходы такие:
а) если вершина не является концом слова-вируса, перехожу во все смежные состояния, длину увеличиваю на 1
б) если вершина является концом слова-вируса, перебираю всю цепочку суффиксных ссылок и из каждой такой вершины пробую идти во все смежные, длина +1.
Правильная ли динамика?, а то падает на 8ом тесте, или же ошибка в подсчете суффиксных ссылок (на глаз вроде все ОК).
aba
bab
ab
Если я правильно понял вашу идею, то слово abab будет найдено дважды.
Не так надо.
Пожалуйста, если кому-то вдруг придут футболки или информация об онсайте - напишите здесь.
Помнится в одном из этапов МирПК удалось во втором диве занять какое-то призовое место, полагались деньги и футболка. Деньги честно перечислили (помнится деньгами Снарк занимался), а футболку так и не дождался...месяца через 2 пнул спонсора с вопросом "WTF!! Где моя одёёёжа??? Носить нечего!!!", на что получил ответ "в Вашем городе нет наших представителей, к сожалению. Возможно, Вы
планируете в ближайшее время быть в Москве или одном из городов, где
есть наше представительство." Потом, что-то "бла-бла...две таможни, не дойдет..." Короче я забил на них...мелочь, но осадок остался!!! :(
Поэтому таки пнул организаторов на то мыло, с которого приходили поздравления. ждем-с...
"600 участников отборочного раунда (19 июня) получат наши футболки http://t.co/3TYJJBc Мы уже начали рассылку подарков."
Опубликована эта новость 2 часа назад. Так что надежда есть)