→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | adamant | 157 |
| 6 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | djm03178 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 13.11.2024 05:26:01 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
И сразу вопрос: можно ли сменить настройки часовой зоны в FB, так чтобы во event'ах отражалось местное время
ссылку можно?
Пока нельзя:)
Добавил
"You will only be able to access the round if you were in the top 500 from Round 1" — а условия можно будет смотреть?
Думаю, да.
Три задачи будет?
Еще ни разу не было не трех задач)
Меня вообще печалит что в Facebook'е на футболки скупятся. У них же огромный запас ещё с 2011 года должен был остаться, когда обещали 300, а раздали 150, потому что никто больше ничего не решил...
На футболках год написан?
В 2011 вроде не было (перед, зад).
мне кажется, что если бы они подарили участникам позапрошлогодние футболки, то ты бы еще громче возмущался, что они скупятся :)
Они же вроде каждый год одни и те же?
На прошлогодней на рукаве написано "2012".
А почему пост написан 12.12.2012?
Наблюдателен)
Это был черновик другого поста, который написал другой человек. Чтобы в списке постов не валялся, решил использовать:)
А как узнать точную дату поста? Я умею только "2 месяца назад"
навести курсор на надпись "2 месяца назад" :)
Интуитивная понятность такая понятная :D
Сейчас по ссылке "Запрашиваемая вами страница не найдена." Это из-за того, что я не допущен до 2-ого раунда ?
UPD: Ссылка на таблицу работает.
LOL, видимо так facebook борется с нагрузкой на их сайт... fail. Выложите кто-нибудь условия посмотреть, пожалуйста.
Если это не является нарушением правил, может ли кто-нибудь объяснить почему в пятом тесте второй задачи (про роботов) аж 60 туров, если роботы такие умные? По мне так кажется, что только 15 роботов, которым не грозит утилизация могут откосить, остальные, обладая сообразительностью, могут догадаться, какая их ждёт судьба, тем более, что второй пример как раз об их догадливости. То есть раунд должен бы состояться всего один.
Ну вот я уже всё решил... И чего это раунд такой длинный?
не, у меня другой вопрос... почему еще не все всё сдали?
У кого-то time expired по третьей((
turi muti
кому твои яйца надо было сдать.
Codeforces, такой codeforces. Тут всегда минсуют заявления оранжевых и красных о том, что всё было тупо, или даже если содержится хоть малейший намёк на то, что всё было тупо. Просто потому, что сине-зелёных гораздо больше.
И, в общем-то, правильно. Конечно, зависть — плохое чувство, но, всё же надо понимать эмоции людей, для которых пройти во второй раунд было уже достижение, и которые с трудом сдали 1 задачу, и это для них прогресс — многие просто потому, что опыта мало, или просто регион такой, что учить толком некому. Таких людей надо поддерживать и вдохновлять, а не демотивировать...
Заявления синих и зелёных о том, как всё сложно, минусуются так же усердно :)
Я могу назвать N > 1 красных участников Codeforces, которые не сдали все три задачи на этом контесте.
Конечно, ведь три задачи сдали только 52 человека, а красных на кодфорсесе ~200 человек. Ну и что?
Расскажите, пожалуйста, как решать третью.
UPD: не зашло
Ясно, что дано дерево. Решим задачу для поддерева для каждого числа, стоящего в корне (от 1 до размера поддерева).
Будем добавлять по 1 ребенку, перебирая, какое текущее значение у корня. Рассмотрим 2 случая — больше мы или меньше. Помутим преф.суммы для быстрого добавления всего отрезка.
Итого какой-то куб.
Код
Решение правильное, ищи баг
Не подскажешь верный ответ на input?Туплю, можно же чужой код использовать
На самом деле это квадрат =) потому что все пары вершин ровно один рахз мерджатся
Ага, прочитал уже ниже, спасибо
В инпуте нам дано дерево, на каждом ребре которого записан порядок следования его концов в конечной перестановке. Будем делать динамику по поддеревьям. Пусть f(v, pos) — количество способов разместить поддерево вершины v так, чтобы она стояла на позиции pos. Научимся ее пересчитывать через детей. Для этого заведем динамику g(k, m1, m2), которая говорит, сколько способов расставить первые k детей так, чтобы среди тех, которые должны стоять перед нашей, самый правый стоял на позиции m1. Аналогично, среди тех, которые должны стоять после нашей, самый левый стоит на позиции m2. На самом деле, эту трехмерную динамику можно разбить на 2 двухмерных (для двух типов детей) и в конце посчитать ответ через них. Если переход в двухмерной динамике делать за линию, то в сумме выйдет решение за куб. На всех 20 тестах отрабатывает меньше, чем за секунду.
Легче сделать так: сначала добавляем ребро к ребёнку, берём частичные суммы сначала или с конца смотря больше он или меньше, а уже потом объединяем его с поддеревом. Тогда формула получается симметричной. Если надо объединить таблицы A[pos] и B[pos] в таблицу D[pos] то формула выходит:
Первая C-шка это расстановка элементов меньших корня поддерева между собой, а вторая — больших.
Это, как нетрудно догадаться, квадрат :)
Ну в общем-то у меня примерно так и реализовано. Только я всегда считал, что это куб.
Каждое объединение делается за O(N1 * N2) где Ni это количество вершин в поддереве. Можно считать что ты объединяешь каждые две вершины в них. Объединение двух вершин происходит только один раз — в их LCA. Всего пар вершин N * N. Отсюда квадрат :)
Я раньше слышал что в таких случаях сложность выходит квадрат, но мне казалось, что это применимо к несколько другим задачам. А сейчас попытался вспомнить, к каким именно и пришел к выводу, что наша от них ничем не отличается. Но доказательства того, что это будет квадрат я не знал, спасибо.
Ага, а если там за O(min(N1, N2)) то вообще линия выходит. Я до недавнего времени над этим не думал. А потом дошло :)
А разве не n*log(n)? Например, для полного бинарного дерева.
Сорри, я имел ввиду случай min(h1,h2), по высоте :)
А никто исходники не выложит сравнить результаты?
1 2 3
Уже даже протестили.
А в 3, небось, подразумевалось n^2*log(n) с БПФ =)
Фурье вряд ли, т.к. по модулю он не считает, там максимум Карацуба. Хотя и куб меньше чем за секунду на всех 20 тестах отработал.
А, да. У меня 5 сек, но тем не менее)
NTT (http://en.wikipedia.org/wiki/Discrete_Fourier_transform_(general)#Number-theoretic_transform) еще как считает
Не, ну то что по специальному модулю он считает — это я знаю. Я имел в виду, что по модулю 109 + 7 Фурье не будет работать. Хотя мне интересно, может у __float128 точности хватит, чтобы посчитать в тупую, а в конце округлить и взять остатки по модулю? Даже для ограничения 100000 нужны будут числа порядка 1023.
проще сделать NTT по двум модулям, а потом КТО и взять по нужному модулю
А почему Фурье не будет работать по модулю 10^9+7?
Upd. Факторизовал p-1, осознал.
Не, куб, БПФ я не рискнул давать :)
Но ведь большинство сдавали чистый квадрат
У меня были решения за квадрат и за n*log(n) (с модулем 1051721729) Для второго раунда ограничение в n<=1000 показалось вполне разумным :)
Если честно, мне кажется, что weak tests. Я не верю, что мое решение правильное :)
Такой вопрос, какой код правильнее:
Или
Дело в том, что вторая задача с первым вариантом с одной погрешность падает, с другой все ок. С первым вариантом тоже все хорошо. Но вот можно ли всегда так обходить использование eps (просто перейти к нестрогому неравенству)?
Правильнее делать в целых числах:)
ну это само собой. :)
но порой в целых числах придумать сложнее, и обидно когда замена одного символа в eps решает проблему...
Где там бинпоиск во второй?
Ну можно было длину блока (по k роботов), которые будут голосовать вместе за спасение своих железок, а так же кол-во блоков одинаковой длины бинпоиском.
Я тоже длину одного блока искал бинпоиском. А вот количество одинаковых блоков можно было и не искать. Там их все можно было пройти в цикле. У меня вышло, что всего блоков было порядка нескольки тысяч на максимальном тесте.
Можно было решать с другой стороны и не делить, а умножать. В конце останется N%K роботов (или K если остаток 0), все они не голосуют. Пусть на каком-то шаге есть X неголосующих роботов. Считаем сколько блоков голосующих роботов надо добавить чтобы выборы состоялись, пусть при этом роботов станет Y. Если Y > N то ответ (N - X) / K + 1 . Если нет — считаем X=Y, так как все эти роботы теперь в безопасности. При P=100 считаем Y очень большим.
Ну я про это и говорю. Просто количество блоков голосующих роботов можно было искать формулой, а можно и бинпоиском. Ну а количество раз, которое мы берем текущее число за новое X получается несколько тысяч. Если бы было много, то нужно было бы делать еще один бинпоиск или более извращенную формулу выдумывать.