Good news everyone!
Так как предыдущая тема съехала из прямого эфира придется заводить новую
Сегодня в 19:10 по Москве состоится очередной СРМ
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Но ведь можно было просто поднять старую.
Её заминусовали полностью и теперь сложно поднять...
Двойные стандарты, не иначе
>.<Скорее публикация топика за 2 дня до
Она, я так понял, набрала отрицательный рейтинг, потому в прямом эфире и не отображается
Правда, что в медиуме достаточно было предпосчитать вектора вида (x,y) 0<x<=L, 0<y<=H, gcd(x,y)=1, а потом для каждой стартовой вершины перебрать?
Врядли. Их порядка (HL)/2 казалось бы.
Ну, я не так делал — я фиксировал вектор до последней взятой точки
Да, потому что получится асимптотика не N^3, а N^2 log N, так как вылезет какая-то сумма по всем n (1 + 1/2 + 1/3 + ... + 1/n).
UPD: А, стоп. Конечно не перебрать из каждой стартовой вершины. Для фиксированного вектора (x, y) мы умеем за O(min(L / x, H / y)) рассовывать из него всё, на что он влияет. И тогда получится N^2 log N
Вроде бы даже N^2, потому что сумма обратных квадратов.
Но для каждой перебираемой пары придется считать gcd, то есть все-таки N^2 log N.
Ну не квадратов всё-таки. Сумма по
.
Ах да, я просто считал количество прямых с не меньше, чем k точек на них, и для k есть (N/k) вариантов по dx и (N/k) вариантов по dy, а количество хороших стартовых позиций легко по k и dx вычисляется.
Че? тут получается
. Она казалось бы большая иногда. То что ты написал получится видимо, если перебрать минимум, а потом перебирать непонятно что.
Не-а. Если вектор (x, y) со взаимно простыми координатами, то он принципиально бывает интересен в d = 1 + min(L / x, H / y) состояниях: когда на нём 1 точка, 2, ... d. Для каждого состояния мы положениям вектора на отрезке оно соответствует и прибавляем к коэффициенту при нужном биномиальном коэффициенте. Получается O(d) на вектор.
А да. Можно и так. Чит. Я писал, примерно то что выше mmaxio написал.
А почему O(L / x + H / y) а не O(L / x)? Вроде как более сильная оценка неверна только если x = 0 и положить L / x = ∞ =)
Ну, в выражении выше я на автомате шлёпнул O(L / x + H / y), хотя там более корректно O(min(L / x, H / y)), сейчас поправлю.
Нет, я не об этом. По мне, так второе слагаемое/аргумент функции min можно опустить, если не брать в расчет случай x = 0.
А, в смысле, так тоже выйдет правильная оценка? Ну да, а так сразу видно, почему оно летает — во-первых, из минимума возьмётся коэффициент 1/4, из того, что вектора со взаимно простыми координатами — ещё 6 / π2...
хм, я так сделал и работало очень долго. Даже не отправлял
бред
Авторы молодцы, замечательные условия! Всегда бы так.
Очень приятно, не часто можно увидеть такие отзывы:D
P.S. Особенно, от того, кто залажал.
Красота а не контест! Может попробуем ввести традицию, что анонсирует SRM его автор, если он есть на CF? Так будет честно по меньшей мере с точки зрения вклада.
Есть такая традиция, что автора до конца контеста не оглашают.
Правда? Я не знал. Ну тогда надо по меньшей мере отписываться в анонсе.
Меня немного напрягло, что непосредственно из условия 275 никак не понять, что в данной и требуемой от нас строчках разное число символов.
Чего?.. Разное в смысле иногда бывает пустая строка?
Всмысле иногда n=3 и просят длинную строку длины 3. А дали строку длины 1
Аааа!!! Что за треш? Я так и не заметил этого... Теперь лотерея — будет ли моё решение работать или нет :-\
UPD: Фак ееее, прошло. Я лакер! :-)
Ну семплы прошел, так что наверно будет. А вообще странно, да.
Ну вроде из семплов понятно, что они бывают разной длины. Так что ничего странного.
Будем мне уроком, что стоит вглядываться в сэмплы по 275, даже если они проходят с компила.
а почему разное? может же быть и одинаковое.
да, тоже немало времени потратил, чтоб понять это. Ну впрочем, никто и не говорил, что одинаковое.
Как решать 975?
Ну, во-первых, эти 2 энда равны энду всех чисел. Вычтем этот энд из всех чисел, тогда нам надо разбить на 2, энд которых 0. Будем решать рекурсивно по битам. Посмотрим сколько у нас в данном бите нулей. Если их меньше 2х, то ответ, очевидно, 0. Если больше, то сначала просто вызовем для i — 1 бита, убрав i-й. Какие варианты мы посчитали, хотя не должны были? Ровно те, где все нулевые биты лежат внутри одного цвета. Тогда поэндаем все числа с нулевым битом, добавим получившееся число к массиву из тех, к которых в i-м бите единица (убрав этот бит), вызовем рекурсию и вычтем результат из ответа.
задачи отличные, особенно мне понравилась 500
Я определённо тупой, но как решать 250?
Для каждой позиции(с 1) перебираем символ, берем наименьший подходящий.
А чтобы проверить, подходит ли префикс, приписываем все оставшиеся символы в порядке убывания и считаем ответ в лоб.
Не один такой :)
Видел какие-то адские dfs'ы, но ломать побоялся. Ещё в комнате были совсем коротенькие решения (пара циклов), но какие-то они подозрительно простые.
Кстати, раз уж автор темы — Егор, несколько пожеланий по плагину:
1) Почему он импортит все функции с данным именем, а не только нужную? Если есть много перегруженных функций, то так можно случайно нарушить UCR. Это реально поправить, и будет ли это правиться в ближайшее время? :)
2) В окошке тестов очень не хватает hotkey-ев — без них на компе без мыши дебагать очень сложно.
3) В случае успешного прохождения тестов пишется, что они пройдены успешно, но таблички с временем по каждому тесту нет (а она была бы полезна, особенно учитывая, что это java, а не c++)
А вообще — замечательный плагин, с ним писать очень удобно. Спасибо за его разработку :)
Он импортирует все, а потом удаляет неиспользуемое. Должен по идее удалять перегруженные (но не переопределнные) с тем же именем (если только это не имя самой целевой функции для TopCoder или не main для обычных тасок)
Надо будет стырить где-нибудь приличный редактор текстовый.
Показывается максимальное время (а не сумма, как можно было бы подумать). Не уверен, что нужно прям по каждому тесту
Кстати, проект опенсорс, шлите полезные патчи. У меня на этот проект есть лицензия на Idea от JetBrains, кто будет контрибутить — поделюсь. Сам я в последнее время был занят очень, но постараюсь сделать то, что уже запланировал
По поводу п.1 — он не удалил импортированные gcd(int, int) и gcd(long, long), а также pow(int, int, int) и pow(long, long, long). При этом в первом случае idea почему-то не понимает, что gcd(long, long) unused, но для pow понимает. Надо будет подробнее посмотреть.
Будет время — постараюсь что-нибудь поcotribютить.
проходило ли в 275 дп за O(n2 * 2n)?
Смотря какая динамика. Я, по своей глупости, написал динамику за O(n * 2n), а не простое решение. Есть гипотеза, что у вас такое же — откуда взялся квадрат в оценке?
UPD. Прошло
Объясни, плз, как ты считал динамику в этой задаче?
dp[mask][f] — наибольшее количество инверсий, которое можно сделать буквами из множества mask, f — нужно ли, чтобы при этом строчка была не меньше оставшихся символов в minStr.
Хотите прикол. Ответ на такую динамику будет cnt*(cnt-1)/2. где cnt свободные элементы в маске. Так что это по сути жадный, но вы этого не подозреваете.
Во-первых, cnt * (cnt - 1) / 2 будет только в том случае, когда оставшиеся символы, расположенные в порядке убывания, не меньше остатка строки, если мы до этого все время выбирали ее префикс. Во-вторых, все в курсе. Бывает, что во время контеста начинаешь писать первое, что пришло в голову и проходит по времени, не подумав о более легких решениях.
у меня было d[mask][eq] — максимальное число инверсий, которые можно получить буквами из множества mask, eq — равен ли построенный уже префикс префиксу строки minStr. при этом в дп мы следим, чтобы наша строка всега была не меньше minStr, для этого собственно и нужен второй параметр.
А арена сейчас только у меня не работает?
У меня работает.
Не только, не даёт перезайти.
У меня наполовину загружается. Верхняя колонка появляется, но не более.