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

Автор snarknews, 4 года назад, По-русски,

Стартовала традиционная летняя серия индивидуальных соревнований SnarkNews Summer Series-2013. В этом году раунды серии также являются тренировочными раундами для участников турнира Яндекс.Алгоритм, а сама серия проводится на той же системе Яндекс.Контест. Доступно расписание серии.

Участвовать в серии могут все, кто имеет логин на Яндексе. Соответственно, для регистрации нужно зарегистрироваться на Яндексе и войти хотя бы в один из раундов серии. логин и пароль от почты и являются логином и паролем на вход в систему Яндекс.Контест.

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

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

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

Первый раунд закончился, как решать А и Е?

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

    До 15:20 подождать стоит, наверно

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

      Да, точно, не подумал, что закончить можно позже чем в 14:00.

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

      Кстати, неплохо бы вернуть фичу "показывать, кто сейчас пишет контест и сколько времени у него прошло".

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

        Такая фича есть, нужно зайти через contest.yandex.ru. Сейчас видно, что контест пишет eatmore и у него сейчас идет 59 минута.

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

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

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

    E — можно делать следующий образом (во время контеста не успел). Вначале найдем как соотносятся масштабы, это можно сделать используя соотношение длин кратчайших сторон каждой из ломаных. Пусть мы нашли это соотношение (т.е. при желании можно сделать одинаковый масштаб, но лучше просто потом использовать его, чтобы всё было в целых). Дальше надо сказать правда ли, что существует такой обход второй ломаной, что они совпадут с первой с точностью, до поворота или переноса. Это можно сделать следующим образом выпишием длины сторон (или например квадраты длин сторон), чередуя с углами (или можно например использовать векторное произведение или ещё какую-то функцию от угла) для каждой из ломаных. Получим 2 некоторых "строки", для которых надо сказать, правда ли, что существует циклический сдвиг второй, что они совпадут и найти этот минимальный сдвиг. А это можно сделать при помощи КМП или z-функции.

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

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

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

      А как насчет строки "WVWVVVWVWVVV"? Если я правильно понял решение, ответ будет содержать несвязные отрезки.
      UPD у Mex-Mans все правильно, я написал чушь.

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

        1ый отряд, который мы найдем будет 2,3,4, 2ой отряд будет 1,5,6, 3ий отряд 8,9,10, 4ый 7,11,12. Порядок же применения удалении этих солдат обратный. 1ое удаление 7,11,12, мы его можем произвести, т.к. между 7 и 11 солдатами нету пустых мест, 2ое удаление 8,9,10 они идут подряд все ок, 3ье удаление 1,5,6, между 1 и 5 нету пустых мест. И последнее удаление 2,3,4, тут тоже все ок. Надеюсь я ответил на твой вопрос.

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

          Извини, я неправильно прочитал условие (а понял вообще хуже некуда). Спасибо тебе за подробный ответ!

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

      Removed (под спойлером ошибочный тест).

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

        Удаляем по-порядку (1,2) (3,6) (4,5) (7,10) (8,9)

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

          Спасибо, кажется я смог до конца понять (тест который я приводил запутал меня после, того как нашел его).

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

    А какое это имеет отношение к раунду? Там вроде только про 4 числа похожая задача, но она настолько простая, что не вижу в этом ничего страшного.

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

        Мне кажется, что решение из этого архива неверное. http://acm.ashland.edu/2009/Problem-Set/Solutions/A.java Как он может учитывать случаи, когда промежуточный результат не делится нацело? Пример: 1 3 4 6 24 = 6/(1 — 3/4) и без дробей это никак не составить.

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

          Да, похоже тесты слабые. Но этот — не очень подходящий, я умею получать 21 = 1*(4*6-3).

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

          Так задача-то другая, в частности в условии написано Division can be used only if the divisor evenly divides the dividend.

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

      А вот это уже не круто, даже семплы такие же)

      На следующих раундах буду гуглить фразы из условия.

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

        Это, конечно, сарказм, но смысла гуглить в любом случае немного.
        Все раунды SN*S состоят из "баянистых" задач, уже где-то использованных, и это довольно известный факт, но контесты от этого хуже не становятся. Задачи уже кто-то прорешивал, багов мало. Эта серия соревнований — просто интересные тренировки. Никакого профита/удовольствия от читерства на соревновании, которое держится исключительно на честности участников (целая неделя виртуального контеста) испытать не получится.
        А еще некрасиво себя чувствую, отвечая на вопрос "Уверен ли я, что комментарий на английском языке". Было бы хорошо иметь возможность продублировать комментарий на двух языках или отправить русский коммент в английскую ветку отдельно.

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

          Возможно, сарказм связан с тем, что всё же обычно условия задач несколько перерабатываются, меняются сэмплы, часто дополняется набор тестов (и соответственно меняется решение).

          Но здесь дело в том, что была уверенность, что эта задача нигде больше, кроме первого сезона Открытого Кубка, не появлялась, и необходимости в переработке условий не потребуется (на сайте Кубка условий первого сезона пока нет — более-менее в адекватном виде архив был восстановлен менее месяца назад).

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

        Интересно, как эта задача попала на e-olymp. Вроде архивы первого опенкапа (а задача была взята с Гран-при Москвы 2005) не для этого раздавались. Вроде бы условия на ранние архивы были такие — задачи не должны без согласования с авторами использоваться в онлайн-архивах задач вне контестов (то есть там, где можно сдавать позадачно, а не в форме виртуального или реального контеста).

        Особых претензий нет, но вот хотя бы проинформировать координатора OpenCup о размещении задач Гран-При было бы неплохо — чтобы авторы знали о том, что задачи есть в архиве и нормально не реюзаются.

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

Сдал задачу D поиском в ширину. Начинаем из тех вершин, где можно зайти во дворец, при этом не переходим по тем ребрам, которые можно заблочить с той стороны. Почему это верно? Кажется, что это не всегда бывает верно.

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

    Построим ориентированный граф (раздвоим каждый коридор) и удалим те дуги, которые можно закрыть (предположим, что они сразу закрыты). Тогда безопасными останутся только те вершины, которые недоступны из внешних вершин (в которые можно попасть снаружи). Понятно, что опасная вершина не сможет стать безопасной, также как и безопасная стать опасной (все пути в нее из опасных вершин можно перекрыть).

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

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

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

Тесты с первого раунда как-то можно посмотреть?

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +46 Проголосовать: не нравится
  1. Задача С. Почему во вводе локомотив считается вагоном, а в выводе нужно число вагонов без учета локомотива? Как до этого можно догадаться, кроме как придумывая разные варианты того, что могут спрашивать в задаче, и проверяя на соответствие примерам? Как после того, как догадался, быть достаточно уверенным, что правильно понял, чтобы заслать вслепую? Такое условие не кажется логичным, поскольку не отличает случаи, когда может проехать локомотив и не может проехать ничего.

  2. Задача E. Является ли следующий тест корректным?

4
0 0
1 0
2 0
0 2
0 0
2 0
1 1
0 2

Если да, то был ли подобный тест в наборе? Если не было, то почему?

Если нет, то почему об этом не сказано в условии?

Мое решение в дорешивании получает вердикт "не удалось протестировать".

  1. Задача B

Слабые тесты. Решение, в котором все промежуточные вычисления делаются в целых числах, получает AC, хотя должно падать на тесте

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

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

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

    вопрос снят

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

    Про C все было написано довольно четко, в том числе в описании ввода -

    В следующей строке задана масса локомотива w0 в тоннах, в i-й из последующих M-1 строк — масса i-го вагона wi в тоннах (все wi целые, 1 ≤ wi ≤ 10^6).
    
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, про задачу B удивило, что ее так активно чисто сдают, неужели все сразу сообразили, что в целых не получится...

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

Как посмотреть результаты раунда, которого я не писал?

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

Очки за разделённые места не делятся...

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

как решать D из третьего раунда?

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

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

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

      А задача A? динамика по профилю с какими-то хитростями?

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

        Зачем с хитростями? Там же TL 24 секунды. У меня на джаве предподсчет ответов для всех возможных (N, M, k) работает 9 секунд. Единственное, что может быть необычно: у нас много состоний и переходов, которые нам не подходят, поэтому можно вначале построить граф, где вершины — маска одной строчки поля, а ребро между вершинами, если одна строчка может находится рядом с другой. Ну а дальше обычная динамика по профилю.

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

          Кстати, никто не заметил, там изначально 24 секунды было? Просто, когда я думал как решать, мне показалось, что там около 6 секунд было.

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

            Когда я писал, точно было 24, но, самое обидное, я заметил это сразу после конца контеста, последние несколько минут которого я потратил на то, чтобы запустить предподсчет у себя на компе и сохранить в виде готового массива с ответами (и в итоге нехватило совсем чуть-чуть времени, чтобы получить АС) :(

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

          Ага, то есть даже не по изломанному. Спасибо.

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

      А если бы в телескопе нужно было 4 линзы, то задача бы решалась? А если k?

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

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

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

Отличное условие в C!

"Первая строка входа содержит целое число T — количество тестовых примеров." -- в условии

С нулями в семпле, причём правильно с нулями. А можно ли как-то попытку снять за это?

UPD: Сняли, спасибо :)

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

    По просьбам участников петрозаводских сборов раунд продлён до 2 сентября 15-00, так что просьба воздержаться от обсуждения до окончания раунда.