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

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

Только что завершилась олимпиада. Предлагаю здесь обсуждать задачи. Интересуют решения задач G,J,H,E. Тыкни здесь!

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

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

В E(Футбольные поля) достаточно проверить, чтобы площади и множества длин ребер совпадали.

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

    ооп. А если множество одно, а последовательности длин разные?

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

      Считаем длины сторон первого многоугольника, сортируем их. Тоже самое делаем и для второго. Если массивы сортированных длин совпадают и площади одинаковые, то многоугольники совпадают.

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

        3 0 5 1 8 4 7 5 0 6 3 2 1

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

          Вроде бы тут YES.

          Сдвинул второй треугольник на вектор (-2,-1), получилась одна точка в (0,0). Потом отразил относительно y=x, затем относительно y=-x. Еще сделал параллельный перенос. Треугольники совпали.

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

            Возможно, но все равно построить многоугольники такие можно наверное.

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

        У нас зашла даже без проверки площади. Считаем длины ребер у одного, потом у другого. Если одну можно получить из другой циклическим сдвигом, то ответ YES, иначе NO. Тоже хотел бы узнать как делать G.

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

          Получается, если во входном файле вам дан квадрат и ромб с такой же стороной, не являющийся квадратом, у вас выведет YES?

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

            Видимо, да. А можете предложить тест такой, просто если они не совпадают, значит у одной фигуры (у ромба, если конкретнее) будет какой-то угол не 90гр. И тут уже вопрос стоит в том, можно ли подобрать такой тест, чтобы координаты при этом были целочисленные.

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится +2 Проголосовать: не нравится
              4
              0 0
              5 0
              5 5
              0 5
              0 6
              3 10
              0 14
              -3 10
              
              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Да, я вот тоже составил подобный тест только что(: Абсолютно с вами согласен. Если честно, то мы и сами были удивлены, когда она зашла. У нас была написана только часть задачи про ребра, но времени оставалось мало и мы решили хоть что-нибудь заслать.

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

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

                  UPD. Ну вот, ниже уже привели контрпример

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

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

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

                  На прошлом ВКОШПе в задаче А проходило неправильное решение, но в Барнауле против таких тесты подобрали.

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

                  Это очень вряд ли. Тесты на всех площадках идентичны.

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

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

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

    А кто-нибудь может это доказать (хотя бы нестрого)? Мы делали весьма хардкорно: перебирали перестановку из отражений, применяли их к многоугольнику и находили вектор, который соединяет центры масс, проверяли, что он подходит. Это еще и в лонг даблах не заходит, только целочисленно.

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

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

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

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

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

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

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

    пффф, тест:
    4
    0 4
    4 7
    7 3
    3 0
    8 1
    13 1
    13 6
    8 6
    ответ НО (если я не ошибся), насколько я понимаю, ваше решение выдаст YES? мне кажется, или он валит всякие площади, длины сторон, углы и периметры

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

H. У меня так какой-то баг, но она зашла после грязного хака. А так решение, вроде, правильное: Посчитаем бфсом уровень темноты в каждой клетке. Сделаем бинпоиск по ответу, т.е. по наибольшей темноте. Для фиксированной наибольшей темноты рассмотрим все клетки в которых темнота больше этого значения. Рассмотрим их диагональный boundig-box, если он покрывается ромбиком радиуса равного наибольшей темноте, то надо понижать уровень, иначе — повышать. Потому переберем центр ромбика и проверим.

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

    Одно из авторских решений — такое как у вас, другое за O(площадь прямоугольника). Оно основано на том, что "диагональный bounding-box" можно за быстро пересчитывать при добавлении некоторых клеток, которые нужно осветить, а также уменьшения допустимого ответа (можно пересчитывать за O(кол-во добавленных клеток)). А если начнем перебирать ответ с суммы длин сторон, и будем отнимать по единице каждый раз (до того момента, пока существуют клетка такая, что поставив в нее лампочку, осветим необходимые клетки), то всего будет обработано O(площадь) клеток.

    А что за "грязный хак"?

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

      У меня получался в бинпоиске какой-то ответ (радиус этого ромба). Я пытался его получить, перебирая центр ромба. На четвертом тесте я не выводил ничего, то есть, не находил нужный центр. Я решил увеличивать ответ на 1, пока что-то не найду. Зашло.

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

        На самом деле это вполне обоснованный хак... Если я правильно понимаю, то хватило бы увеличить ответ на 1 один раз — тогда точно найдется такая клетка. Просто в поиске bounding-box'a может получиться (если искать его вводя ограничения на сумму и разность координат), что вроде бы на нем клетка должна быть, но ее там нет из-за разной четности суммы и разности, например. Ну и очевидно, что если увеличить ответ на один, то такая клетка точно найдется.

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

Пожалуйста, залейте в тренировки, хотелось бы написать в виртуале. Желательно и базовую и усложненную.

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

G. Ленивая динамика [t2][t3][mask], где t2 — количество слоев из двух блоков, из которых можно удалить один блок, t3 — количество полностью заполненных слоев, mask — маска последнего слоя. Мы можем вытащить блок из t2 слоя, либо t3 слоя, либо последнего и поставить на последний слой, либо создать новый слой.

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

наше решение Е (казалось бы верное), на мой взгляд не особо сложное: заметим, что такими операциями можно получить многоугольник повернутый на 0, 90, 180 или 270 градусов относительно своего начального положения, который, возможно, будет отражен. сначала зададим стороны многоугольников набором векторов, затем, оринетируем оба многоугольника в одном направлении (можно, например, против часовой стрелки), переберем угол поворота второго многоугольника и проверим, что второй многоугольник (или его отражение) является циклическим сдвигом первого. циклический сдвиг можно проверить префикс функцией.

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

    Как-то сложновато. Верно, но сложновато. Можно просто перебрать все повороты второго многоугольника (их 8). Теперь для первого и рассматриваемого найти минимальные вершины (самые нижние левые), а дальше просто пройтись двумя форами, проверяя на соответствие координаты вершин, по часовой и против часовой стрелки. Хотя, может, профессионалу мой способ покажется менее рациональным и удобным, не знаю, не знаю :) UPD. Тьфу, выше уже было такое решение. Ну да ладно)

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

    Я эту задачу вообще случайно сдал: решаю по монитору, вижу, что все Ф сдают, читаю (потом оказалось, что это Е) понимаю, что может все не так уж и просто, но раз люди за 5-10 минут сдают, значит эвристики с площадью, периметром, углами должны работать. Пишу, сдаю, потом несколько секунд удивляюсь, что задачу Ф я так и не сдал, но зато получил первый успешный сабмит по Е :)

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

Скачав архив тестов, обнаружил что в задаче G были тесты где N = 1000, в то время как по условию N не превосходит 700. На моем решении не сильно отразилось, но неприятно узнавать вот такие сюрпризы. Если бы сразу не забил бы массив с запасом, очень долго бы искал почему RE/WA.

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

кто-нибудь из авторов контеста или таргетов может сказать, как решать J?

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

    Разбить треугольное поле на n диагоналек.

       . 
      X..
     XXX..
    XXXXX..
    

    Посчитать динамику dp[i][j] — количество способов покрыть поле, таких что мы уже покрыли последние i диагоналей (три на предыдущей картинке), причем мы уже пробовали ставить на первые j побочных диагоналей. N^2 состояний, каждое считается за O(N) (надо перебрать сколько мы покрыли до этого). Можно заметить, что нам нужно сумму по всем переходам посчитать, это можно с помощью частичных сумм на одной из диагоналей или ее же считать прямо при итерации по второй размерности динамики. Итого получится O(N^2)

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

А как задачу B решать?

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

    Подвесим дерево за какую-нибудь вершину. Посчитаем динамику: downSq[v] сумма квадратов путей до всех вершин вниз, чтобы ее пересчитывать понадобится down[v] сумма путей до всех вершин вниз. Тогда просто

    down[v] = sum(c is children of v, down[c] + count(c) * w(vc))
    

    где w(vc) — вес ребра, count(c) — количество вершин в поддереве c

    downSq[v] = sum(c is children of v, downSq[c] + 2 * down[c] * w(vc) + count(c) * (w(vc)^2))
    

    Формула может быть немного неправильная, если что исправьте, главная идея, что если к элементу прибавить d, то квадрат изменится на 2 * d * val + d ^ 2.

    Потом пройти вторым поиском в глубину и пересчитать те же самые динамики наверх. И сложить.

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

Как А и Д решаются?

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

    D. Сортировка, но чуть-чуть необычная. Рассмотрим две произвольные строки s1 и s2. a1=s1+s2, a2=s2+s1. Если a1<a2, то строка s1 будет раньше чем строка s2, иначе позже.

    A. f[i][j][k] = можно ли дойти до клетки (i,j) и не показаться на всех снимках с 1 по k. Если можно, то храним откуда пришли. Ну а потом восстановление ответа.

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

      Спасибо! Сейчас решаю виртуал, сдам в дорешке.

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

Кто нибудь решал задачу ф с базовой? Засылаю на сервер, RE5, но локально проходит все тесты. Да, наверняка мой косяк, потому что проблемы подобные возникают у многих и они находят баг, но я уже бессилен. Если кто-то сдаст ее именно на сервере кф, напишите пожалуйста, буде еще раз смотреть код тогда. Спасибо. UPD Всё, спасибо, сдал, используя dsu.