Состоится сегодня в 15:00 по Москве
Имеется призовой фонд в $5000, так что поспешите с регистрацией, кап может быть достигнут досрочно
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
15:32:42
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
15:32:42
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 02:02:19 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
И все же кап не набрался.
на редкость дерьмовый SRM
разбери-100500-гадостных-случаев в 250-ке, недооцененной авторами раза в полтора по количеству баллов за неё; стандартная-хрень-с-дополнительным-хитрым-ограничением в 550-ке (интересно, почему я не увидел фраз типа: "в каждой пятой доске количество красного не должно превышать корня из произведения зелёного и синего" или "16-ая доска не должна содержать синий компонент, если Марс находится под влиянием Сатурна")
да, вот 950-ку не осилил, сказать про неё ничего не могу хорошего
Раунд еще не закончился.
+1. По 250-ке у меня вообще идей нет. а 550 зафейлил где-то, у меня очень много кода вышло, не успел отдебажить. Интересно посмотреть как написать это быстро, и чтобы в ТЛ вписалось, ведь RSQ за Log^3N должен всяко ТЛ получать.
А чем обычные частичные суммы плохи?
Я подумал об этом, подумал, но не педставилось мне как это работает не в одномерном случае, потому начал писать другую штуку, которая по сути делает то-же самое
Обидный СРМ. Частичные суммы написал, но нашел баг через 1 после конца :( 250 сперва не увидел ограничения на 10^9 и написал втупую, потом пришлось срочно переписывать и ресабмитить :) так что я недалеко от тебя тут.
Это как же должен был не понравиться матч, чтобы вот так, еще до его окончания, высказать все хорошее и не очень о задачах)
На самом деле, 250 не такая уж страшная (посмотрим, пройдет ли у меня... Но идея вроде бы нормальная... и никаких случаев особых нету), по крайней мере, до начала челленджей. Буду надеяться, что через минуту ничего не измениться)))
А в 550 это дополнительное хитрое ограничение действительно портит всю малину:)
это должен очень сильно не понравиться :)
возможно, я просто избалован нормальными СРМами с хорошими и интересными задачами, но в этом не хотелось даже ничего писать
А что за ограничение имеется в виду?
1 случай, не? l>r
(тут было число 550, но маркап думает, что 1). Коряво написанное но 2 условия по факту: Входит в большой куб, не входит в маленький.
Уважаемый, MikeMirzayanov! Реквестируем фичу сказать Codeforces, что он не умнее пишущего, и что-то надо парсить так как написали, а не так как хочется эвристикам.
странно, в 250-ке как минимум ещё трава с +/- и аккуратные +1 везде по коду
а если ты думаешь, что 550-ка — нормальная задача, то полистай код Петра ;)
550я нормальная задача без случаев. А 250ка мне не понравилась видимо потому что она у меня упадет и я сделал по ней 2 неудачных челенджа
250-я простая и без случаев.
У тебя есть система из n-1 уравнений и n неизвестных. Причем уже в треугольном виде. Пусть a[0] = x. Тогда a[i] = A[i]*x + B[i]. A*x + B — прямая. Значит есть 2 случае. Прямая положительна от (-INF, -B / A) или от (-B / A, +INF). Пересекаем все полученные отрезки — ??? — PROFIT.
Я сдал её на 150 баллов потому что долго тупил. Так норм задача.
А по-моему, нормальные 250 и 550, ну чуть техничные. Про 950 не знаю, не читал, потому что даже 550 не додебажил, но это проблема не задачи, а моя.
А когда в решении возникает слишком много случаев, это ещё не значит, что все возможные решения задачи разбирают слишком много случаев.
это не значит, что решения, разбирающие меньше случаев, оказываются проще для понимания и написания
а вообще мне надоело спорить; моё мнение останется со мной, и я безмерно рад за вас, если вам понравились задачи
Я не согласен ни по одному из пунктов (обе задачи вполне нормальные, как и относительная сложность), ни с публикацией комментов до окончания СРМа
Ну почему нельзя почеленджить себя, когда нашел багу за 10 секунд до конца и не успел отправить. упавшая 250-ка совсем бы окупилась челенджами.
На самом деле, понятно почему же.
Спасибо, кэп. Ну можно же по ныть?
Ну можно ж подоставать нытиков, когда ты нормально написал рануд;)
Паш мне не хватило пары секунд, чтобы тебя почеленджить. Я долго сомневался челенджить или нет. Кстати у меня easy тоже упадет
А у меня стойкое ощущение, что моя 250 на чем-нибудь упадет.
Не может быть так просто:)
Ощущение было не зря
upd2 Да, надо еще и нижнюю границу держать, а не только верхнюю.
взломы по int overflow? говнораунд детектед
И еще по отсутствию max(0,ans);
Придумала решение по 950, не успела. Посмотрите, похоже ли на правду.
Идея основана на китайской теореме об остатках. Будем решать задачу отдельно по модулям 2 и 5, потом перемножим ответы. Разобьем числа в позициях от 0 до N-1 на две группы: которые попадают в хотя бы один запрос с ненулевым произведением и которые ни в один такой запрос не попадают. Некоторые из чисел второй группы должны быть нулями, чтобы удовлетворить все нулевые запросы. Остальные числа из второй группы могут быть чем угодно, это ни на что не влияет.
Количество вариантов для второй группы считаем динамикой d[i][j] — количество способов расставить числа до i-го, чтобы последний ноль стоял в позиции j. Если у нас не удовлетворяется какой-то нулевой запрос, заканчивающийся в текущем i — перехода не делаем.
Что касается первой группы, то в случае модуля 2 все тривиально — мы должны поставить во все такие позиции 1. В случае модуля 5 записываем систему равенств, которую получаем из ненулевых запросов. Берем дискретный логарифм -> приходим к СЛАУ, количество решений которой определяем Гауссом.
Ответы для первой и второй групп перемножаем.
Когда мы взяли дискретный логарифм мы перешли к
, в котором не хорошо делить на 2. Как там делать Гаусса?
Вот из-за этой проблемы я и не успела. Но вроде бы, Гаусса делать можно.
На очередном шаге выбираем, какую строчку поставить первой. Если есть строчка с коэффициентом 1 или 3 — отдаем предпочтение ей. Если есть строчки только с двойкой — их можно вычитать друг из друга, ни на что не деля. Прямой ход сделать получилось.
Что касается обратного хода, то там уравнения с первый коэффициентом два накладывают ограничения, что вся остальная часть уравнения должна быть четной. Это приводит к некоторой СЛАУ по модулю два, для которой можно найти количество решений. Еще нужно учитывать, что при делении на два получаются два корня.
Чтобы посчитать количество решений по модулю 4, можно просто предположить что это система по модулю 2 (просто взять все коэффициенты по модулю 2). После этого найти количество решений системы и возвести полученное число в квадрат.
Я правда, не совсем понял почему это верно, но зашло в дорешивании, на контесте подбирал нужную степень двойки на которую нужно домножить, но так и не подобрал, потому как набажил в коде нахождения ранга матрицы :)
Пример: x1 + x2 = 2, x1 + x2 = 0. По модулю 4 система не имеет решений, по модулю 2 у нее два решения. Что-то не так(
Я вообще сильно удивился, когда прошло :) Действительно идея неверна, сам себя счелленжил в дорешивании тестом: N=2, Qfrom[] = {0,0}, Qto[] = {1,1}, output = {9,1}.
Получается, что тесты на ТС совсем неполные.
(Палево) По-видимому, правильно искать количество решений системы по модулю 2 и количество решений тоже по модулю 2 системы, у которой коэффициенты матрицы такие же, а от свободных коэффициентов берутся старшие биты. И перемножать.
Так тоже пробовал, но на одном из семплов это не работает. Вторая система получается несовместна, хотя первая имеет решение.
Да, поняла, что это тоже палево.
Вообще довольно интересно, как искать количество решений системы, если эта система не по простому модулю. Может кто-то знает как это делать в общем случае?
Вроде стало понятно, как посчитать количество решений системы по произвольному модулю вида pk. Будем делать Гаусса с выбором главного элемента по всей матрице. В качестве главного элемента выбираем такой, который делится на наименьшую степень p. Получаем, что каждая правая-нижняя квадратная подматрица делится на ту же степень p, что и главный элемент. Если в столбце свободных коэффициентов что-то не делится — ответ 0. Иначе после завершения прямого хода Гаусса при необходимости дополняем матрицу до квадратной нулевыми строками и перемножаем элементы на главной диагонали (заменяя нули на pk). Это и будет количество решений системы.
У меня в общих чертах такое же решение, только с одним нюансом — если рассмотреть частичные произведения в каждой группе из не-нулей то можно решение СЛАУ заменить на dfs, т.к. в каждой строке матрицы будет по 2 ненулевых элемента
Судя по систестам это даже правильно :)
Да, так гораздо проще. И поздравляю с рандомными 50$ :)
Спасибо :)
Такой вопрос: куда денутся деньги, которые должны бы по идее достаться мне (за 1 место в комнате), но не достанутся из-за того, что нет 18?
Тебе предложат выбрать благотворительную организацию, в которую отправят деньги
А можно конкретней узнать, где можно совершить выбор? А то прошлый раз мне ничего не пришло, и сам я ничего такого не нашел. В этот раз хотелось бы использовать эту возможность.
Запись моего слива :)
"_Prize winners will be notified via e-mail within 10 days of the completion of the tournament that they have won a prize_"
Кто-нибудь уже получил email?
Да я и после первого их срма не получил, не говоря уже о втором.