Блог пользователя agul

Автор agul, 10 лет назад, По-русски

Прошёл очередной opencup, давайте обсуждать задачи.

  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

В I никто в спираль не поверил?

.#........     .#.......#     .#.......#     .#.......#     .#.......#     .#.......#     .#.......#
#@........     #.......#@     #.......#.     #.......#.     #.......#.     #.......#.     #.......#.
.#........     .#........     .#........     .#........     @#........     .........@     ..........
.......... --> .......... --> .......... --> .......... --> .......... --> .......... --> ..........
..........     ..........     ..........     ..........     ..........     ..........     .........@
..........     ..........     .........#     .........#     .........#     .........#     .........#
..........     ..........     .........@     @#........     .#........     .#........     .#........
»
10 лет назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

Мне задачи показались немного издевательскими.

»
10 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Расскажите C и E.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    E: Можно для каждого требуемого количества столов посчитать топ-200 клеток по целевому функционалу. После этого просто запустить поток на объединении этих клеток — понятно, что больше ничего нас не интересует.

    Проблема в 1ом шаге, 25000000 сортировок 18 элементов даже близко не лезут в ТЛ. Поэтому надо использовать тот факт, что расстояния не сильно меняются при переходе в соседние клетки, т.е. если где-то сумма расстояний большая, то она большая и в какой-то окрестности. Впрочем, на java7 в ТЛ не лезет даже с этим (и ещё с кучей оптимизаций).

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      А, у тебя эта часть тормозит. Я делал так: переберем 2**18 подмножеств, для каждого найдём минимум суммы — это медиана по обеим координатам. Дальше для каждого размера n+k раз делаем следующее: берем минимальное расстояние, и добавляем в рассмотрение четыре соседние клетки. Ну и множество клеток в очереди на рассмотрении не имеет смысла делать больше n+k, так что храним их в куче по максимуму.

      Другими словами, от 5000 моё решение не зависит (well, на самом деле зависит — я использовал битовый квадратный массив чтобы помнить, какие клетки я уже рассмотрел, но можно было бы и хешмэп).

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +34 Проголосовать: не нравится

        А я вместо 2**18 подмножеств взял 18 * 18 точек, каждая медиана всегда в одной из этих точек, и их уже клал в очередь.

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        А после поиска медианы для каждого подмножества что именно мы делаем? То есть как запустить поток и что он должен считать?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Если смотреть по каждому x отдельно, то на самом деле сортировок можно сделать 5000 * 18 * 18, ибо сортировать имеет смысл, только в точках где значения для пары точек одинаковые. А еще можно заметить, что этими точками все разбилось на 182 отрезков и внутри функция монотонна, т.е. мы можем в каждом отрезке взять по 200 точек. В итоге вроде что-то гуманное получается.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    В С если решать искать вероятность проигрыша вместо выигрыша, то получится простая динамика (сколько набрали, сколько шагов). Потом ответ просто 1 — p.

»
10 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

Выражаю особую признательность авторам задачи E и ТЛя к ней. Стандартный вопрос — есть ли решение на джаве? Я потратил полконтеста на упихивание (и последующее переписывание на плюсах). Особо доставило то, что плюсовое решение работало не быстрее джавовского на Java8, но на серверах кубка java8 недоступна (а у меня локально недоступна java7 — зачем держать старье у себя на компе), так что сравнить шансов не было.

Ну и ещё один традиционный вопрос — какие неправильные решения вы пытались отсечь таким ТЛем? Единственная приходящая в голову лажа — тупой стоимостной поток, но он бы и за день на таких ограничениях не доработал.

(после такого рода задач у меня появляются садистские мысли вроде подготовки контекста, в котором ничего не заходит без low level оптимизацией с использованием SSE и AVX. При этом желательно, чтобы на каком-нибудь левом языке вроде питона заходило без проблем с использованием читерских библиотек. После такого, наверное, авторы будут думать прежде чем ставить жёсткий ТЛ)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Решение на Java было. Около секунды работает. Обычное решение за 2^n * n + дейкстра на nk вершинах + поток на n + nk вершинах.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    У меня зашло на Java без единого TLя, но я скопипастил из какого-то старого контеста минкост с поиском кратчайшего пути дейкстрой без кучи за O(E+max_distance) (храня списки вершин на каждом расстоянии), может дело в этом.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    в котором ничего не заходит без low level оптимизацией с использованием SSE и AVX.

    А что, реально существенно обогнать в каких-то местах (ну, кроме умножения матриц) оптимизации gcc с правильными флагами под архитектуру? Конечно, флаги немного где ставят, но всё же.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я, кстати, не знаю, насколько у нас на грани ТЛя зашло, но у меня был написан обычный поток со стоимостями с дейкстрой с TreeSet.

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Обсуждаю задачи: они были не очень. Не было даже ярко выраженных халяв, все какое-то упихивательное, чтобы участники вдоволь наобмазывались случаями.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Мне вот интересно, а заслать решений с разными вердиктами в яконтест можно было вчера? Все же знают, что в прошлый раз интерактивки тоже не работали.

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    В прошлый раз не запускался чекер. Сейчас проблема совсем другая. Система каким-то странным образом выдает вердикты.

    По J всегда правильно выдавала WA. По H/I если интерактор возвращал WA, считала это за OK. Изменили код возврата интерактора с WA на CF, и правили вердикты ручками. Но на вашем решении вердикт интерактора полностью игнорировался. У ИТМО 1 было RE в J, но система выдавала WA.

    В ejudge никаких пробелем с вердиктами я не заметил

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А то. что мы сдали — это в итоге похоже на правду?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Сам код я не смотрел, но он проходит все тесты.

        Забавно, что я в Я.контесте могу видеть stderr интерактора, в котором пишется ok/wa. Чтобы определить правильность решения, я открывал отчет, ctrl+f "ok ", далее если найдено 152 строк, значит се тесты пройдены.

        Когда я вам убрал OK, у вас не работал только 1 тест, а в остальных было меньше 5000 запросов.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Может кто знает, что в 8-м тесте задачи G?
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    3 9 -1 10 5 10

    Ждем 0.2 сек. Далее необходимо двигаться, так как грузовик будет накрывать точку (-1, 10). Освободит ее только через 1.8 сек. Это и есть ответ. Здесь скорость точки в 2 раза больше скорости грузовика, и она успевает сделать все: быстро отойти и пристроится сзади.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Как решать G? Тернарник в бинарнике у нас не прошёл.

upd. проходит.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Кто может объяснить B?

Есть ли решение C, более умное чем рандомно одним кубиком на малые градусы, вторым для поворотов и бегать на близком расстоянии от точки?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ты про H видимо, а не про C?

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Да, про H.

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        Утверждение: раскраска из sample input получает ОК

        Доказательство: сабмит :) Ну то есть я взял это решение, промоделировал интерактор, на парочке случайных тестов убедлился, что такая стратегия работает и отсабмитил.

        А, ну и еще — на каждой итерации используем тот кубик, который минимизирует матожидание расстояния до (0; 0)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    В можно попробовать решить честно, перебрав много случаев, однако этого делать очень не хочется. Но если все-таки отважишься, то сперва лучше написать стресс, чтобы не искать баги до следующего ГП. Я написал стресс, который для каждой фигуры со сторонами от 3 до 50 и каждого вектора (пары точек) обновлял ответ. Ну вот если теперь выписать что у нас получилось в таблицу (для вектора), то можно увидеть закономерность. Получается очень хорошее решение в несколько строк, для которого у нас уже написан стресс :)

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Придумали в D такое решение: для каждой клетки, содержащей отражатель, рассмотрим крест из строки и столбца, в которых эта клетка находится. Введем для каждого креста буловскую переменную, которая true если отражатель расположен одним способом, и false — если другим. Каждый шарик теперь, попадая в таблицу, оказывается в каком-то из крестов, притом никогда из него не уходит. Теперь для любой пары крестов определяем, в каком виде они могут сосуществовать (то есть, перебираем возможные расположения отражателей в них и смотрим, будет ли когда-нибудь столкновение шариков). Таким образом, мы свели задачу к 2-SAT. Но шариков до 10000. Каким образом можно быстро построить этот граф?

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    Заметим, что для зафиксированной пары отражателей есть всего две клетки, в которых могли столкнуться их шарики — это пересечение вертикалей и горизонталей, на которых эти отражатели лежат. Для шарика мы за O(1) можем узнать время, в которое он будет находиться в заданной клетке. Узнаем для каждого из шариков обоих отражателей, в какое время он будет в каждой из двух клеток пересечения, а потом проверим, что эти времени не совпадают. В итоге получается O(NM).

    Также надо не забыть проверить, все ли хорошо для одного отражателя: не пересекаются ли шарики, летящие с вертикали и горизонтали: это так же делается за O(1) простой формулой.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Мы строили граф за квадрат от числа шариков.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Может кто-нибудь рассказать решение F?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Будем поддерживать такие числа, кроме двух чисел из ответа: для каждого типа помним, сколько его осталось за вычетом тех, которые мы уже точно знаем что проданы, а также для каждого значения t помним, сколько могло быть куплено игрушек с таким t, из тех, которые ещё не перешли в категорию "точно проданы", плюс для каждого значения t и количества помним, сколько есть типов с таким t и оставшимся количеством.

    Каждый новый день появляется по 1 новой "могло быть куплено" для каждого t, плюс вычитается по одной "могло быть куплено" из тех, которые еще точно не определены, могли быть выкинуты в этот день, но не выкинуты. Из "могло быть" в "точно проданы" есть два перехода: либо когда игрушка физически исчезает из магазина, либо когда для какого-то суффикса значений t общее количество оставшихся игрушек с таким t равно количеству ещё не определённых дней, в которых обязательно продаются игрушки из этого суффикса.

    В итоге получается решение за 10**5 * 100.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А расскажите, пожалуйста, решение J.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Найдем стратегию жюри. Стратегия — это перестановка. Рассмотрим пространство перестановок. Введем расстояние (pi, pj) = x, где pi — наша стратегия, pj — стратегия жюри, x — доля побед.

    Ну и самая главная часть задачи: по данным перестановкам p1, p2, ... pk и расстояниям (p1, p * ), (p2, p * ), ..., (pk, p * ) найти наилучшее приближение p * . Я, например, это делал генетическим алгоритмом.

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Интересно узнать решение задачи J из второго дивизиона.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Расскажите пожалуйста как нужно было решать задачу L. Performance (Div. 2).

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Переберём все параболы. Найдём максимальное значение которое она достигает. Это происходит в точке . Выведем номер параболы с наибольшим максимумом.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Здравствуйте. Кто решал второй дивизион, не подскажите, как решалась задача М (про крестики-нолики)? Вроде бы она изишная была, но, к сожалению даже с 16 раза не зашла(( Если решали, можете кодом поделиться?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is B, all about case analysis? Any easier way?

  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    After some analysis, it comes up that there are actually only three significant cases:
    1) Δ x or Δ y is equal to zero;
    2) Δ x and Δ y have the same sign (both greater than 0 or both less than 0);
    3) Δ x and Δ y have different signs.

»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Can't find upsolving again.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The letter-indexes of the problems in upsolving differs from letter-indexes in statements.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А в чем секрет последней задачи второго дивизиона?

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Given that, there will be qualification round of deadline24, will there be opencup next week?