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

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

Раунд кончится в понедельник, 12 августа, в 14-00. Можете считать это небольшой напоминалкой (вход в контест).

Но пост не об этом. Кто вычитывает тексты условий? Уже второй раунд подряд нам предлагают такую ересь from my heart (задача C из Round 1, задача F из Round 2), что ну просто вообще невозможно понять, что от тебя хотят. Может, стоит назначить отдельного человека или даже группу людей, которые будут читать условия и гарантировать, что они понятные?

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

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

С пониманием задачи F из раунда 2 у меня проблем не возникало, но вот с задачей C раунда согласен на все 200%.

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

Более того, в условии одной из задач третьего раунда, когда я его вчера писал, была откровенная опечатка, делающая условие некорректным. Пришлось на свой страх и риск угадать правильный вариант, но, тем не менее, на понимание ушло порядочно времени. Я сразу написал снарку, эта опечатка уже исправлена, но чтоб я ещё хоть раз писал так раунд в самом начале срока... Пусть грабли собирает кто-нибудь другой.

Я в целом согласен с тезисом, что среднее качество условия на этом контесте ниже, чем хотелось бы.

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

А кто-нибудь знает, где можно посмотреть окончательные результаты 1 раунда?

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

Скройте, пожалуйста, пост в черновики до окончания раунда: в комментах появились условия некоторых задач.

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

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

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

Расскажите, пожалуйста, о чём просят в В.

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

    Два игрока играют на дереве. Изначально в вершине 1 стоит фишка, и эта вершина покрашена в черный цвет.

    Первый игрок за ход красит любые k вершин, второй игрок передвигает фишку в любую из смежных вершин. Если второй ставит фишку в непокрашенную вершину, он выигрывает. Если все вершины покрашены, выигрывает первый.

    Во вводе дано дерево. При каком минимальном k первый имеет выигрышную стратегию?

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

      Кому интересно, переводы условий остальных задач:

      A. Есть строка из символов V и W, за одну операцию можно выбрать несколько непересекающихся пар соседних символов и одновременно поменять местами символы в каждой паре. За какое минимальное число операций можно получить из первой строки вторую?

      C. Есть два множества по n точек внутри квадрата со стороной 1. Найти минимум по всем паросочетаниям максимума (расстояние первой точки пары до границы) + 2 * (расстояние между точками в паре) + (расстояние от второй точки пары до границы).

      D. Есть множество плохих символов и прямоугольник из r*c символов. Найти максимум отношения (число плохих)/(число всего) по подпрямоугольникам, у которых каждая сторона >=m

      E. У нас есть число n. Изначально n = 1. За один ход можно выбрать d — делитель n, заплатить d рублей и заменить n на n + n/d. За какую минимальную стоимость можно получить число K?

      F. Есть доска n*m и клетка (x,y). Найти кратчайший путь, который начинается и заканчивается в (x,y), и проходит по всем клеткам хотя бы один раз, и вывести его длину минус 1.

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

        C. Есть два множества по n точек внутри квадрата со стороной 1. Найти минимум по всем паросочетаниям...

        Ааа, это многое объясняет... Теперь я понимаю, как моё решение смогло не зайти. Но как тогда понимать эту фразу из условия?

        При этом любое дерево из первой расстановки может оказаться на месте любого дерева из второй расстановки, кроме того, несколько деревьев в любой из расстановок может оказаться в одной точке.

        Казалось бы, это явно противоречит пониманию с паросочетаниями? Эх, видимо, тактика "не читать бредовые легенды" не всегда прокатывает :(

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

          Я получил OK, соединяя пару деревьев ребром если между ними околонулевое расстояние.

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

          Не противоречит. Если К деревьев находятся в одной точке, то их координаты будут написаны К раз.

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

            Ну это только если "правильно" интерпретировать написанное. Формально, одной только первой части фразы ("любое дерево из первой расстановки может оказаться на месте любого дерева из второй расстановки") достаточно для противоречия, т.к. в переводе на русский это означает "рассматриваются произвольные отображения" (и про то, что что-то должно быть сюръективным или инъективным, в контексте этой фразы ничего не написано).

            Оффтопик — очень жаль, что мало кто из авторов задач следует стратегии "писать любую ахинею в легенде, а потом нормальную математическую формулировку в конце легенды или в формате данных". Это бы существенно упростило парсинг жутких текстов.

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

        Как можно понять в F, что чувак начинает там же, где и должен закончить? Что за бездарные условия?

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

          А еще чтобы проверить 1 x 1 = 1 вариант рассадки, нужно 0 просмотров.

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

          и что последний просмотр он осуществит с того же места, которое занимал во время премьеры.

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

            где кончается путь — понятно, но где написано как соотносится премьера с началом пути? откуда следует, что не может быть такого: чувак посмотрел премьеру и через год только поговорил с владельцем и бла-бла-бла по легенде?

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

          Вот хз если честно. Тот факт, что в инпуте вообще присутствует позиция чувака, явно намекает на то, что спрашивают не про цикл. Видимо, не стоит искать логику в условиях SNSS.

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

      Эх, вот почему задачи не дают сразу в таком виде... После твоего комментария сразу сдал в дорешку:)

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

      Расскажите, как решается эта задача?

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

        Представим себе другую задачу: пусть k фиксировано, и есть дополнительный параметр m — первому игроку разрешается дополнительно закрасить m вершин на самом первом ходу.

        Тогда найти такое m, при котором первый будет выигрывать, можно динамикой по дереву. Остается лишь бинпоиском найти минимальное k, для которого m(k) = 0.

        код на Java

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

Кажется, Снарк нанял ребят с Тимуса писать ему условия.

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

Интересно, мне одному кажется, что на SNSS/SNWS условия всегда были такими? Как и сам стиль задач, который по сути является блицом на стандартные алгоритмы, а не нормальным контестом. И задачи всегда брались из каких-то левых, но вполне себе открытых источников и потому время от времени для некоторых участников задачи оказывались известными. Ничего особенного, как мне кажется, не произошло.

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

    Ну просто количество непонятных условий за эти два раунда уже превысило их количество за предыдущие два года, а так ничего особенного не произошло.

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

    Я не против баянов, тем более, что, к сожалению, для меня задачи редко такими являются. А вот эти легенды... Иногда они даже нужны, как в задаче В на этом раунде, но в большинстве случаев это похоже на попытку усложнить жизнь участникам. Можно ведь и совмещать легенду и формальные объяснения, как это делают практически везде.

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

А как решать А?

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

    Втупую проэмулируем:
    0. Будем ставить на место Vшки, остальные встанут сами. Пусть их N штук. Очевидно, что k-ая в первой строке Vшка станет k-ой во второй строке.
    1. Сформируем N пар (from, to), каждая обозначает, что Vшку, которая сейчас в позиции from надо довести до позиции to.
    2. Тогда пошагово будем сдвигать всё, что можем на один шаг ближе к цели. Понятно, что порядок не важен — всё равно никто никому не помешает, если этого можно избежать (мешать можно только вовремя не сходив).
    Выходит грубо куб, на деле быстрее — залетает за .2 на джаве.

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

Слава полным наборам тестов! По F АС получает и решение, которое на 1 10 1 5 выводит 18, и решение, которое на 1 10 1 5 выводит 10.

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

    Разные тесты для разных трактовок условия! Пройди хотя бы один из двух и получи плюсик

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

Объясните пожалуйста. Есть вот такой код. На компиляторе : GNU c++ x32 (4.6), получает ва2. На компиляторе: GNU c++ (4.6), ОК. Скажите что дает такую разницу на примере этого кода? Не хотелось бы снова с таким столкнуться. Спасибо.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится
    x.cpp: В функции «int query(int, int, int, int)»:
    x.cpp:56:21: предупреждение: неиспользуемая переменная «r» [-Wunused-variable]
                     int r = 2;
                         ^
    x.cpp: В функции «int main()»:
    x.cpp:104:57: предупреждение: сравнение плавающих значений при помощи == или != ненадежно [-Wfloat-equal]
                                             } else if (t == maxx && (x * y) > sz) {
                                                             ^
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Спасибо, первое предупреждение не повлияло ж? Надеюсь. А второе, оно не перегружено на сравнение с погрешностью? Получается что в GNU c++ (4.6) перегружено на проверку с погрешностью? Или мне просто повезло второй раз и впреть нужно даблы сравнивать только самописной функцией?

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

        Первое предупреждение я привёл потому, что это похоже на логическую ошибку. Насчёт второго — да, повезло, числа с плавающей точкой на равенство лучше проверять с эпсилоном.

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

А как доказывать решение задачи Е?

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

Почему-то в дорешке нельзя послать задачу, выдаёт "Bad request :) ".