TopCoder SRM #545 - Codeforces

12 лет назад, # ^ |

+42

Скорее публикация топика за 2 дня до

→ Ответить

12 лет назад, # ^ |

Она, я так понял, набрала отрицательный рейтинг, потому в прямом эфире и не отображается

→ Ответить

12 лет назад, # |

Правда, что в медиуме достаточно было предпосчитать вектора вида (x,y) 0<x<=L, 0<y<=H, gcd(x,y)=1, а потом для каждой стартовой вершины перебрать?

→ Ответить

PavelKunyavskiy

12 лет назад, # ^ |

+13

Врядли. Их порядка (HL)/2 казалось бы.

→ Ответить

12 лет назад, # ^ |

Ну, я не так делал — я фиксировал вектор до последней взятой точки

→ Ответить

12 лет назад, # ^ |

← Rev. 4 →

Да, потому что получится асимптотика не 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

→ Ответить

mmaxio

12 лет назад, # ^ |

← Rev. 2 →

Вроде бы даже N^2, потому что сумма обратных квадратов.

Но для каждой перебираемой пары придется считать gcd, то есть все-таки N^2 log N.

→ Ответить

12 лет назад, # ^ |

Ну не квадратов всё-таки. Сумма по $\text{[math]}$ .

→ Ответить

mmaxio

12 лет назад, # ^ |

Ах да, я просто считал количество прямых с не меньше, чем k точек на них, и для k есть (N/k) вариантов по dx и (N/k) вариантов по dy, а количество хороших стартовых позиций легко по k и dx вычисляется.

→ Ответить

PavelKunyavskiy

12 лет назад, # ^ |

Че? тут получается $\text{[math]}$ . Она казалось бы большая иногда. То что ты написал получится видимо, если перебрать минимум, а потом перебирать непонятно что.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

Не-а. Если вектор (x, y) со взаимно простыми координатами, то он принципиально бывает интересен в d = 1 + min(L / x, H / y) состояниях: когда на нём 1 точка, 2, ... d. Для каждого состояния мы положениям вектора на отрезке оно соответствует и прибавляем к коэффициенту при нужном биномиальном коэффициенте. Получается O(d) на вектор.

→ Ответить

PavelKunyavskiy

12 лет назад, # ^ |

А да. Можно и так. Чит. Я писал, примерно то что выше mmaxio написал.

→ Ответить

12 лет назад, # ^ |

А почему O(L / x + H / y) а не O(L / x)? Вроде как более сильная оценка неверна только если x = 0 и положить L / x = ∞ =)

→ Ответить

12 лет назад, # ^ |

Ну, в выражении выше я на автомате шлёпнул O(L / x + H / y), хотя там более корректно O(min(L / x, H / y)), сейчас поправлю.

→ Ответить

12 лет назад, # ^ |

Нет, я не об этом. По мне, так второе слагаемое/аргумент функции min можно опустить, если не брать в расчет случай x = 0.

→ Ответить

12 лет назад, # ^ |

А, в смысле, так тоже выйдет правильная оценка? Ну да, а так сразу видно, почему оно летает — во-первых, из минимума возьмётся коэффициент 1/4, из того, что вектора со взаимно простыми координатами — ещё 6 / π²...

→ Ответить

imslavko

12 лет назад, # ^ |

хм, я так сделал и работало очень долго. Даже не отправлял

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

-10

бред

→ Ответить

ilyakor

12 лет назад, # |

+38

Авторы молодцы, замечательные условия! Всегда бы так.

→ Ответить

subscriber

12 лет назад, # ^ |

← Rev. 3 →

+37

Очень приятно, не часто можно увидеть такие отзывы:D

P.S. Особенно, от того, кто залажал.

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

Красота а не контест! Может попробуем ввести традицию, что анонсирует SRM его автор, если он есть на CF? Так будет честно по меньшей мере с точки зрения вклада.

→ Ответить

subscriber

12 лет назад, # ^ |

Есть такая традиция, что автора до конца контеста не оглашают.

→ Ответить

12 лет назад, # ^ |

Правда? Я не знал. Ну тогда надо по меньшей мере отписываться в анонсе.

→ Ответить

mmaxio

12 лет назад, # ^ |

+15

Меня немного напрягло, что непосредственно из условия 275 никак не понять, что в данной и требуемой от нас строчках разное число символов.

→ Ответить

12 лет назад, # ^ |

-8

Чего?.. Разное в смысле иногда бывает пустая строка?

→ Ответить

12 лет назад, # ^ |

Всмысле иногда n=3 и просят длинную строку длины 3. А дали строку длины 1

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

Аааа!!! Что за треш? Я так и не заметил этого... Теперь лотерея — будет ли моё решение работать или нет :-\

UPD: Фак ееее, прошло. Я лакер! :-)

→ Ответить

12 лет назад, # ^ |

Ну семплы прошел, так что наверно будет. А вообще странно, да.

→ Ответить

kraskevich

12 лет назад, # ^ |

Ну вроде из семплов понятно, что они бывают разной длины. Так что ничего странного.

→ Ответить

12 лет назад, # ^ |

Будем мне уроком, что стоит вглядываться в сэмплы по 275, даже если они проходят с компила.

→ Ответить

12 лет назад, # ^ |

а почему разное? может же быть и одинаковое.

→ Ответить

12 лет назад, # ^ |

да, тоже немало времени потратил, чтоб понять это. Ну впрочем, никто и не говорил, что одинаковое.

→ Ответить

al13n

12 лет назад, # |

Как решать 975?

→ Ответить

12 лет назад, # ^ |

+37

Ну, во-первых, эти 2 энда равны энду всех чисел. Вычтем этот энд из всех чисел, тогда нам надо разбить на 2, энд которых 0. Будем решать рекурсивно по битам. Посмотрим сколько у нас в данном бите нулей. Если их меньше 2х, то ответ, очевидно, 0. Если больше, то сначала просто вызовем для i — 1 бита, убрав i-й. Какие варианты мы посчитали, хотя не должны были? Ровно те, где все нулевые биты лежат внутри одного цвета. Тогда поэндаем все числа с нулевым битом, добавим получившееся число к массиву из тех, к которых в i-м бите единица (убрав этот бит), вызовем рекурсию и вычтем результат из ответа.

→ Ответить

12 лет назад, # |

задачи отличные, особенно мне понравилась 500

→ Ответить

SkyHawk

12 лет назад, # |

Я определённо тупой, но как решать 250?

→ Ответить

kraskevich

12 лет назад, # ^ |

Для каждой позиции(с 1) перебираем символ, берем наименьший подходящий.

→ Ответить

al13n

12 лет назад, # ^ |

А чтобы проверить, подходит ли префикс, приписываем все оставшиеся символы в порядке убывания и считаем ответ в лоб.

→ Ответить

agul

12 лет назад, # ^ |

Не один такой :)

Видел какие-то адские dfs'ы, но ломать побоялся. Ещё в комнате были совсем коротенькие решения (пара циклов), но какие-то они подозрительно простые.

→ Ответить

ilyakor

12 лет назад, # |

← Rev. 3 →

Кстати, раз уж автор темы — Егор, несколько пожеланий по плагину:

1) Почему он импортит все функции с данным именем, а не только нужную? Если есть много перегруженных функций, то так можно случайно нарушить UCR. Это реально поправить, и будет ли это правиться в ближайшее время? :)

2) В окошке тестов очень не хватает hotkey-ев — без них на компе без мыши дебагать очень сложно.

3) В случае успешного прохождения тестов пишется, что они пройдены успешно, но таблички с временем по каждому тесту нет (а она была бы полезна, особенно учитывая, что это java, а не c++)

А вообще — замечательный плагин, с ним писать очень удобно. Спасибо за его разработку :)

→ Ответить

12 лет назад, # ^ |

Он импортирует все, а потом удаляет неиспользуемое. Должен по идее удалять перегруженные (но не переопределнные) с тем же именем (если только это не имя самой целевой функции для TopCoder или не main для обычных тасок)
Надо будет стырить где-нибудь приличный редактор текстовый.
Показывается максимальное время (а не сумма, как можно было бы подумать). Не уверен, что нужно прям по каждому тесту

Кстати, проект опенсорс, шлите полезные патчи. У меня на этот проект есть лицензия на Idea от JetBrains, кто будет контрибутить — поделюсь. Сам я в последнее время был занят очень, но постараюсь сделать то, что уже запланировал

→ Ответить

ilyakor

12 лет назад, # ^ |

По поводу п.1 — он не удалил импортированные gcd(int, int) и gcd(long, long), а также pow(int, int, int) и pow(long, long, long). При этом в первом случае idea почему-то не понимает, что gcd(long, long) unused, но для pow понимает. Надо будет подробнее посмотреть.

Будет время — постараюсь что-нибудь поcotribютить.

→ Ответить

12 лет назад, # |

проходило ли в 275 дп за O(n² * 2ⁿ)?

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

Смотря какая динамика. Я, по своей глупости, написал динамику за O(n * 2ⁿ), а не простое решение. Есть гипотеза, что у вас такое же — откуда взялся квадрат в оценке?

UPD. Прошло

→ Ответить

kolya37

12 лет назад, # ^ |

Объясни, плз, как ты считал динамику в этой задаче?

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

dp[mask][f] — наибольшее количество инверсий, которое можно сделать буквами из множества mask, f — нужно ли, чтобы при этом строчка была не меньше оставшихся символов в minStr.

→ Ответить

baukaman

12 лет назад, # ^ |

Хотите прикол. Ответ на такую динамику будет cnt*(cnt-1)/2. где cnt свободные элементы в маске. Так что это по сути жадный, но вы этого не подозреваете.

→ Ответить