| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Прямо сейчас идет этап Открытого кубка, подготовленный силами СПбГУ. Этап стартанул с некоторым опозданием в 12:25. Текущие результаты доступны по ссылкам:
Что любопытно, задачи обоих дивизионов кажутся (на первый взгляд, по названиям) одинаковыми. Может в таком случае лучше иметь совмещенный ранклист?
Без обид, но это был один из худших раундов на моей памяти.
А мне понравился раунд. Правда задачки две еще точно должно было быть.
Как решать задачу С?
Как честно — не знаю, мы использовали то, что их "генератор" псевдослучайных чисел очень слабый. А именно, т.к. модуль всегда большой, то через n оно никогда не перескакивает, и разность iого и jого элементов ровно (i - j) * (
). Так что можно выписать первые несколько миллионов чисел и запустить некое подобие решета на них (для каждого p ищем делящиеся на него среди первых p чисел, и продолжаем этот паттерн с шагом p).
Мы делали так. Заметим, что до 2n у нас очень много вариантов i (более 400М), и как показала практика достаточно проверить первые 3М (доказывать не умею :().
Вот давайте выпишем эти 3М вариантов, и "прорешетим" их.
Делить на простое p будем только те числа, которые на это самое p делятся точно. Как же такие найти? Запишем сравнение (x + i) * (x + i) — n == 0 (mod p) ( тут n < (x+i)^2 < 2*n).
Получаем i*i + 2*i*x == n — x * x (mod p). Найдем перебором все решения данного сравнения j (0<=j<p, их не более 2, т.к. p -- простое), тогда подходящие i будут j+p*t (именно их и нужно делить на p). Если после обработки всех k первых простых какое-то "доделилось" до 1, то оно входит в ответ.
По трудоемкости: найти все j — сумма всех p (<= 2000 * 18000). Поделить все что делится, не более 3M * 60.
Как решать задачи D(гирлянды) и F(шестиугольники)? По D было бы очень интересно узнать и доказательство минимальности.
D: посмотрим на какой-то оптимальный ответ, пусть в нём выбран лист. Попробуем вместо этого листа выбрать его предка. Это может не получиться только в одном случае: какая-то из компонент состоит только из этого листа. Отсюда и решение: срезаем листья, и берём лист в ответ если мы обязаны это сделать.
F: вроде совсем стандартно, нужно посчитать кол-во минимальных путей и суммарную из стоимость из каждого угла в каждую клетку, а потом выбрать минимум суммы средних длин путей.
С double?
Да. Мы в double делали (может long double).
А каким образом там double проходит? Судя по русскому условию нужно вывести точку, чтобы абсолютная разница ответа в этой точке и минимального ответа была меньше 10^-6. Каким образом double это позволяет? Там же есть точки с количеством путей 1e50-1e100 и, возможно с такой же суммарной стоимостью пути. Как отношение двух таких даблов может дать нормальную погрешность ?
Непонятно, каким образом. У нас сначала был BigRational, но он заТЛился. Послали на удачу в double — почему-то прошло.
Мы не хранили число путей, а считали отношения. Количество путей — это цешка. А отношение двух близких цешек оно не большое поэтому считается точно (у нас совсем точно, потому что произведение отношений близких факторалов). Видимо тут эффект тот же. Сильно разные числа никогда не складываются, поэтому относительная погрешность хорошая. При делении так же.
Так видимо это всего 10 десятичных знаков. В чем проблема? Каждое МО <= 400 * 9 (ну и 6 знаков после запятой). В long double не должно быть проблемы.
Не проверяли сами, но укладывалось ли число кратчайших путей в 64битный инт? Мы перестраховались и нормализовали число путей прийти в какую-либо клетку, деля на общее число путей определенной длины.
P.S. Вижу, ответили выше.
Есть граф 1 — 2, 2 — 3, 2 — 4, 4 — 5. Вершины 2 3 4 являються ли поддеревом изначального графа?
Да, там поддеревом считалась любая связная часть дерева.
Насколько я понимаю, последние несколько СПбГУ-шных гран-при задачи div-2 делаются из div-1 с меньшими ограничениями.
Тогда хорошо бы "техническому координатору Открытого Кубка" именовать такие задачи по разному, например, дописывать в конец названия "(упрощенная версия)". Кроме того, в предыдущие этапы, кажется, задачи имели непересекающиеся буквы, а в этот раз они совпадают, что увеличивает путаницу.
Я много раз слышал от координатора Открытого Кубка о том, что писать раунды после официального старта нельзя. Почему же в этот раз есть такие участники (может и в предыдущих были)?! Ведь сразу после окончания начинаются обсуждения задач (да я верю, что команда XZ Team не читерила, но хочется ясности в этом вопросе)! И если в пользу какой-то команды принимается решение разрешить написать этап после окончания основного тура, то хотелось бы видеть эту информацию на главной странице, чтобы это всегда было открыто.
Тем более что таймзона — слабый аргумент; в нашей команде один из участников живёт в той же таймзоне, что и они.
Имхо, правильнее всего — разрешать писать таким командам ночью (MSK) до основного тура, а если к тому моменту ещё не готовы задачи, то только основной тур. Можно конечно ввести отдельный список "доверенных" команд, про которых известно, что они не будут заглядывать на codeforces (я верю, что эта команда к таким относится :) ), но это решение какое-то костылеобразное.
Я посмотрю, как Аким будет писать ночью в выходной через год :)
Вообще, хотелось бы иметь решение проблемы неподготовленного контеста. Правда у нас тут одна команда всего вроде бы, так что я даже не знаю.
я весь прошлый сезон писал по ночам — это было очень тяжело
Ну я например не могу писать ночью. Так вот организм устроен. Не учил перед экзаменом ночью. Вам и правда не завидую! Я бы просто не писал.
Ну и кроме самого обсуждения задач, даже наличие финального монитора сильно влияет на результат, можно надеяться, что все, кто пишут после и в него не смотрят, но обратить на это внимание считаю, что стоит.
Команда XZ Team собиралась писать ночью до основного тура (как она, собственно, и пишет обычно), но так как задачи не были готовы, то в качестве исключения пришлось пойти на такой вариант под честное слово, что они не будут смотреть на результаты и тем более читать обсуждение.
Что? А я не смог добиться разрешения писать туры дома! Ппц
А можно такую информацию вывешивать на главной странице: "мол в ГП ХХХ командам А,Б,С ... решено разрешить написать в такое-то время". Я думаю, что это было бы справедливо.
В случае повторения подобной ситуации так и будет сделано. Другой вопрос, что присылка авторами задач заранее решит куда больше проблем...
Мы очень строго соблюдали правила Кубка, так как нам пошли на уступки и разрешили писать после тура. Слава отказался от написания СРМ 600,5, чтобы писать контест с самого утра, как можно ближе к официальному туру. Плюс, задачи были несколько проще обычных и проблема была скорее в том, что двое сидели без дела, пока третий писал, то есть смотреть CF было бы просто не нужно. Монитор тоже бы не сильно помог, так как много команд с тоталом дало бы понять только, что надо быстро закрывать все. Это разумеется частный случай, контест мог быть сложный, и читерство бы могло помочь, но зачем нам это? Мы не пишем контесты для резюме (у нас с работой все ок), мы не готовимся к финалам, сборам, и т.д. (все свое отписали). Мы пишем, потому что нам нравится писать контесты.
Я надеюсь, что в будущем не возникнет ситуации, когда контест доделывается в ночь перед ним.
Я хотел бы извиниться перед Олегом за то, что мы с ребятами поставили его в положение "оправдывающегося". В следующий раз мы не будем писать раунды, если они не готовы в ночь перед контестом.
Я ничего плохого не хочу сказать и действительно думаю, что вы писали честно. Но почему все говорят как о чём-то вполне естественном, когда кто-то знает условия раньше остальных (в ночь перед онсайт контестом)? Опять же, не думаю, что вы станете сливать кому-то задачи, но мне кажется как бы то ни было это ненормально.
Ну и что нам теперь, не писать кубок, потому что Вам кажется это не нормальным? Мы помогаем между прочим, натыкаемся на баги, их фиксят и 200 команд не обламываются. И зачем кому-то сливать задачи? Чтобы они нас обошли? Смысл?
Ну и что нам теперь, не писать кубок, потому что Вам кажется это не нормальным?Меня просто сильно удивляет, что все об этом говорят, как о каком-то нормальном явлении. Вы у любого отстранённого человека спросите, он Вам скажет "что за бред, почему кто-то знает задачи раньше остальных". Задачи может быть нужно слить не для вас, а для участников онсайта.
Ещё раз говорю — я верю в вашу честность. Но просто почему бы тогда, например, не попросить писать некоторым людям топкодер не в 5 утра, а в полночь, ведь так удобнее. Ну или что-то подобное.
ОК. Я понял вашу позицию. Открою теперь маленький секрет. Когда я готовил свои контесты (а их было 4 штуки и на подходе пятый), то каждый раз, каждый, было несколько команд, которые их прорешивали до тура. Почему? Потому что я был спокоен, что багов нет, что мои решения верные, что условия понятные. Почему эти люди не сливали мои задачи? А зачем им?
Не сравнивайте кубок и ТС. Я был бы рад, если бы ТС можно было бы писать вместо 5 утра (у нас это 4 утра сейчас) скажем в 10 утра. Но тогда есть группа людей "снизу" (допустим синие, не люблю так говорить) которые подумают — а ведь можно считить. Будут регать 2 аккаунта, писать парой (кстати кто сказал что сейчас в ТС нет такого?) и т.д. Но я буду твердо уверен, что Петр, Слава, Гена и другие не читили. Почему? А зачем им?
Я не понимаю фразу: "Задачи может быть нужно слить не для вас, а для участников онсайта.". Какой нам резон кому-то сливать задачи? Если вы верите в нашу честность, вообще о чем разговор тогда? Его бы не было, если бы верили :)
Прорешивание задач для отлова багов и участие заранее это разные вещи. И жюри могут сливать условия.
Как бы Вам сказать о чём разговор. Когда появляются исключения, появляется бардак, хоть изначально исключения были сделаны вроде как честные.
а в чем отличие: прорешивание контеста "для отлова багов" и "участие заранее" ?
Привет, Родион!
В том, что есть чёткое разделение между участниками и жюри.
Ну ведь прорешивают контесты не только те, кто является жюри.
===================================
Кто прорешивает автоматически становится жюри. Мне представляется, что если, например, меня просят прорешать контест, то я не буду в рейтинге. И я не видел, чтобы на кодфорсе те, кто прорешивают, оказывались в итоге в рейтинге.
Не уверен, что это верно.
Ну это тоже справедливо.
Исключения итак уже есть. Я помню, как мы писали на сборах контест, который потом писался в кубке. Заранее писало 20-30 команд. Бардак? Вообще все сборы — это "бардак". Есть команды в ПТЗ, которые видели задачи, а потом на задачах пишут участники сборов в Ижевске и еще где-то. Причем за призы, то есть не в фан.
Судя по количеству минусов в моих комментариях, со мной многие несогласны. Я бы хотел сказать ещё пару слов.
Я обычно не пишу контесты, которые в силу своего расписания написать не получается. И, кажется, это не повод договариваться с организаторами писать в конкурсе раньше или позже основного контеста.
Коль появляются такие команды, то по какому критерию им будет разрешено так делать? По тому, что их все знают? Или потому что они умные? То есть хотелось бы знать, что нужно, чтобы можно было так принимать участие.
В своих комментариях я не ставлю целью не дать сильной команде участвовать в данных контестах, просто хочу понять почему так происходит и высказать свою точку зрения. Мне кажется если такое будет происходить, то в олимпиадном программировании появится бардак. И ещё я уверен, что подавляющее большинство даже не знало, что есть такие команды, мне кажется это не честно по отношению к ним.
Ещё хотелось бы сказать, что означенная команда, если уж действительно так интересно просто решать задачи, могла бы решать их вне конкурса в дорешке в любое удобное для них время.
Про "бардак" ответил выше. Я только не понимаю, о какой честности вы говорите? Вот допустим вы знаете, что есть команда, которая пишет заранее. Что изменится? Вы перестанете писать кубок, потому что он "вне закона"? Зачем Вам лично это знать? Это должен знать организатор. И он контролирует честность и т.д. Я думаю, что организаторы кубка могут следить за выполнением правил.
Просто решать задачи интересно, и их решаем. Но не командой. Чтобы собраться в выходные командой нужен стимул, монитор, где ты высоко... Вообще странно это объяснять участнику олимпиад.
Прошу прощения, видимо я был чересчур неадекватен. Пожалуй частично я с Вами согласен.
По-моему, Вы сильно обобщаете. При чем здесь "в олимпиадном программировании появится бардак"? Речь идет о совершенно конкретном соревновании — OpenCup, которое отличается от тех же SRM своей много-раундовостью.
Кроме просто порешать/не порешать, есть команды, которые решают вопросы выхода в онсайт или, вообще, победы в Кубке. И, если они по каким-то совершенно объективным причинам, не могут писать в этот день, так что, получать 0 в очередном раунде?
Так что, по-моему мнению, данная практика: по согласованию с Олегом Богдановичем писать раньше начала контеста в обоснованных случаях совершенно нормальна. Тем более, что, как выше писалось, такие команды ставят себя в очевидно невыгодное положение (баги в тестах, не знание результатов).
Вот писать после тура — это неправильно. Но как отмечалось, это был исключительный случай.
Я обратил внимание на участие после официального старта только из-за того, что это скрытая информация. Открытая "писать можно только до официального старта". И я ни разу не обвинял Олега в том, что он (возможно с другими координаторами) разрешил писать после, но при этом я убежден, что нужно оглашать решения на сайте. Олег сказал, что в будущем так и будет — посмотрим...
У меня есть такая мысль. Она может помочь избежать таких вот ситуаций в будущем. Так как я уже не раз говорил с командой Стенфорда о кубке и может еще пара универов подключится, хотелось бы иметь возможность писать.
Допустим контест готов заранее. Мы пишем в субботу без монитора (хотя я считаю, что тогда мы в проигрыше, что тоже нечестно, между прочим). Или есть время заранее написанное на главной странице кубка после которого стартует обсуждение (можно же потерпеть с вопросом "как?" недолго?). Олег при этом просто убирает финальный монитор сразу после контеста.
При втором подходе мы окажемся в том же положении, что и участники. То есть у нас виртуальный монитор (тот же, что видели вы) и у нас нет вашего монитора. Я бы просто оставил второй вариант, так как это уберет нечестность по отношению к нам (а она есть — пишем заранее — натыкаемся на баги и пишем без монитора вслепую, пишем с вами — у вас день, у нас ночь, пишем после — мы — читеры).
Насколько я знаю, уже несколько лет разные "trusted" команды писали опенкап до официального старта, если не могли писать вместе со всеми. Да, они напарываются на баги и пишут без монитора, но это вполне честно, тк никто не виноват, что они не могут писать в обычное время. Писать после уже не так очевидно, что честно, тк вы видите монитор, который видели все остальные, а они ваши сабмиты не видели, поэтому вы обладаете большей информацией (в случае топовых команд эта информация бывает существенной). Поэтому написание после контеста допустимо только если контест был не готов, как в этот раз, но в этом случае имхо опаздавшие должны писать с пустыми standings
В принципе я согласен. Пусть пустые. Нам важнее писать в нормальное время дня, чем видеть монитор.
Ну, во втором варианте ваше преимущество в том, что ваших результатов основной поток не увидит.
А результаты сильной команды могут рассказать про задачи достаточно, чтобы поменять результат "внизу", да и не только. Существует вот даже версия, что на Московском четвертьфинале 2013 года официальные команды не сдали задачу C только потому, что не видели команд, участвовавших в интернет-турнире (где SPb SU 4 сдали C достаточно рано). Не то, чтобы эта версия была бесспорной (мне так вообще кажется, что дело не в этом), но тем не менее...
UPD: Не заметил, что про это же уже написал Ренат.
Должен заметить еще, что писать после = не наткнуться на баги, на которые наткнулись в основном туре. Т.е. для удобства по времени еще и удобство по качеству. Так что, писать "до" ОК + список команд (что не обязательно, конечно), писать "после" !OK + в экстренных случаях список команд (обязательно).
По-моему, все верно, и хорошее резюме вопроса :)