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

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

Странно, что никто еще не создал эту тему...
Предлагаю здесь обсудить задачи.

Свои результаты вносите сюда, не стесняйтесь.

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

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

Можно ссылку на задачи?

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

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

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

Да, было бы очень интересно узнать, как решается четвертая. Подозреваю, что там что то вроде N * M * log(N).

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

    Была идея на 60 с террнарником и бинпоиском. Это должно работать за O(N*N*M*log(M)). Из-за переполнения проверить идею не удалось :(

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

      Задача элементарно решается за N3 (два указателя) и довольно просто за N2log2N (2D фенвик)

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

        Спойлер.И вправду элементарно)

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

        За куб понятно. А за N^2 * log^2 N, я думаю, не влезет в TL.

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

          конечно, но баллов наберёт больше 60ти (возможно)

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

          Вообще имелся ввиду NMlog или аккуратный NM*log^2. Решение yeputons за NMlog^2 во всяком случае по плану, должно было получать 100.

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

            Так а как за NMlog решать?

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

              Бинпоиск по ответу. Теперь надо минимизировать длину при фиксированном количестве.

              Переберм i,j — два начала. Тогда есть отрезок валидных концов на правой половине — таких, что соответствующий левый конец с таким ответом где-то в адекватном месте. При фиксированных i,j чтобы была минимальная длина надо минимизировать x + y + \sqrt{(x-y)^2+d}. Это запрос минимума на диагональном отрезке в матричке.

              Если перебирать i,j сначала по сумме, то можно соответствующий такой сумме диагональ в матрице выписать и делать обычное дерево отрезков

              Получается NM*log^2.

              Дальше из этого делается NM*log либо SparceTable'ом либо аккуратным слежением за валидными и очередью с минимумом. Вроде без этого набирало 100.

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

        У нас один товарищ умудрился получить 96 баллов без структур данных. Понять его решение до конца мы не смогли :-)

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

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

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

        мне всегда нравились такие ответы, от вашей сложности проще не стало, и как ее решать тоже понятней не стало, ответ в стиле — я ахуен_й, смотрите, как могу

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

          так а смысл расписывать неполные решения для понимания решения?

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

      Вообще то эта асимптотика просто N*N*M*log() с бинпоиском без всякого тернарника: фиксируем три вершины и подбираем третью.

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

      На 60 сделали без проблем, как раз таки за N ^ 3 без лишних мучений :)

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

      Я так и делал, перебирал а1 и а2, b1 находил тернарником и b2 бинарным поиском, но видимо где-то набажил, набрал мало баллов. Но асимптотика должна быть O(N^2*log^2(M))

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

        По-моему, там функция имеет не один экстремум, чтобы запускать тернарный поиск по b1...

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

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

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

    Вообще 4-ю задачу можно решать за O(N ^ 2), но я сильно не уверен, что такое решение будет работать быстрее O(N ^ 2 log N). Но теоретически довольно интересно. Давайте зафиксируем число деревьев, которое мы хотим покрыть. Пусть это будет Х. Тогда если зафиксируем начало одного отрезка i, начало второго отрезка j, конец первого k, конец второго l. Тогда если d[i][j] — расстояние между i-м деревом одной части аллеи и j-м деревом другой части, то длина веревки для покрытия деревьев будет равна d[i][j] — a[i] — b[j] + d[k][l] + a[k] + b[l]. Также k — i + 1 + l — j + 1 = X, т.е. k + l = i + j + X — 2. Т.е. если мы возьмем матрицу C[i][j] = d[i][j] + a[i] + b[j], то k + l = i + j + X — 2 — это диагональ этой матрицы (не стоит забывать про то, что k >= i, l >= j). На этой диагонали нам нужно взять минимум. Если мы будем использовать Sparse Table или очередь, то получим решение O(N ^ 2 log N). А теперь подумаем и поймем, что бинпоиск нам не нужен. Давайте рассмотрим каждую диагональ как отдельный массив. В нем нужно уметь находить минимум. Для этого можем свести нахождение минимума к нахождению LCA, а находить LCA мы умеем за O(1) на запрос и O(N) на препроцесс. Теперь положим X = 1. Будем перебирать i и j, для каждой фиксированной пары (i, j) пробуем увеличить X на 1, проверяем за O(1) минимум на соответствующей диагонали. Если веревки хватает, то увеличиваем X на 1. Легко понять, что операций у нас в итоге будет O(N ^ 2). Для каждой пары (i, j) мы делаем проверку за O(1). И суммарно X у нас увеличится O(N) раз. Для каждого увеличения будет еще одна проверка. Итого получили решение за O(N ^ 2), но это на контесте не надо было писать ни в коем случае =) В решении активно пользуемся тем, что для фиксированной пары (i, j) если можем покрыть K деревьев, то K — 1 мы также можем покрыть.

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

http://zalil.ru/34183767 вот условия

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

    НЕ все регионы провели 1 тур сегодня.

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

      Какие, например?

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

        Е-бург

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

          Е-бург провел РАНЬШЕ или еще не провел?

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

            Не провел

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

              Гм. Это вообще-то повод полностью дисквалифицировать результаты Екатеринбурга.

              Update: информация была проверена и не подтвердилась.

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

                Денис, успокойся. Андрею явно доверять можно, в отличии от какого-то непонятного анонимного тролля, зарегистрированного 37 минут назад.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  1. Ну это не совсем непонятный анонимный тролль, а вполне конкретный и знакомый мне человек.

                  2. Информация, впрочем, действительно не подтвердилась.

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

                  Я почему-то не верю, что это тот, кем он представился своим ником. Впрочем уже неважно значит.

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

                  Ну я когда прочитал сообщение за подписью L_Wolf про Екатеринбург подумал, что это Лёня Волков. Потом понял, что вряд ли Лёня такой ерундой сейчас будет заниматься.

                  Нет, это не Лёня Волков, но известный мне человек.

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

в том году делали табличку с результатами, может и в этом кто сделает?

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

что-то мне кажется, или в тестах D не было n = 2000, везде n ≤ 1000

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

    Нет не верно. Правда везде было n+m <= 2000, что почему-то не указано в условии. Странно.

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

А как решалась третья на 100 баллов?

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

    4ёх мерное ДП f[len][i][j][carry] — сколько существует подходящих пар длиной len, если первая цифра числа A=i, первая цифра B=j, carry=1, если i+j дают перенос в следующий разряд, иначе carry=0. Переходы расписать или выложить решение на Java ?

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

    Динамика: Состояние-предыдущие цифры в А и В и единица переноса. Переход-приписываем вправо цифры. Upd. Перепутал право и лево. Надо влево дописывать.

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

Как решать A? :)

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

    для двойки: понятно, минимум из 3х
    для единицы: найдем минимальное пересечение a и b (блондинов и высоких), это max(0, a + b - n), теперь найдем минимальное пересечение c с блондинами и высокими, это снова max(0, c + max(0, a + b - n) - n)

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

      Можно просто max(0, a + b + c - 2 * n) :)

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

        это было региональный этап — мы извращались как могли)

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

          Ахаха. На самом деле, мне почему-то весь контест чудилось, что у меня неправильное решение по ней, и я почти каждые 15 минут открывал код, чтобы удостовериться, что все верно :)

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

    -

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

    если n == 1, то max(n-(n-a)-(n-b)-(n-c), 0) если n == 2, то min(a, min(b, c))

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

Подскажите, пожалуйста, где бага в решении, никак не могу найти. http://pastie.org/5725885 Или просто идея неверна? Вкратце: фиксирую два начала, а затем двумя указателями "натягиваю" веревку на оставшиеся березы.

upd. Нашел — переполнение инта в вычислении расстояния между березами. Но неужели это все? Проходит очень мало тестов.

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

    Мой куб с переполнением в этом месте получает около 30.

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

      А нет идей, в чем бага? Или у меня кривой код, в котором лень копаться?)

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

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

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

          8 баллов. Ну, смотри. Я перебираю все пары деревьев, расположенных на разных сторонах аллеи. Для каждой пары сначала проверяю, что эту пару я могу взять. Если так, то тогда я одним указателем набираю, сколько можно, деревьев с левой стороны. А потом цикл: пока во множество ответа включается хотя бы одно дерево с левой стороны, набрать деревьев с правой стороны, обновить ответ и убрать одно дерево с левой. Так я для каждой пары перебираю все возможные варианты. По времени выходит O(N*M*(N+M)), 60 баллов должно набирать.

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

            Ну да. С переполнением 28 у меня набирает. Где-то бага. Но сходу не видно.

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

            Тоже использую два указателя и 8 баллов

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

    А что, уже есть тесты? Можешь поделиться?

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

    Можете ли выложить архив с тестами?

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

      У меня нет тестов. Есть лишь протокол тестирования.

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

У меня по D — 0. Решение следующее представим все в виде полного графа (посчитав расстояние между всеми парами берёз) и найдём цикл не больше заданной длины. TL по всем тестам (на тестах из условия + на моих, в т.ч. больших, но рандомных работает) — Почему?

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

    Обратитесь к вашему региональному жюри. Возможно вы не так назвали файлы или что-то подобное.

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

      Нет, файлы были названы правильно — это было первое предположение.

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

        Ну по такой информации сложно что-либо сказать. Вы не сказали примерно ничего — ни сложности решения, ни даже региона на худой конец. Если будет код — я могу попробовать разобраться. Если нет, то что я сделаю? На 30 баллов вроде должно что угодно почти проходить.

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

          Ну я не знал нормального способа искать циклы кроме перебора(знаю что асимптотика ужасна, но не на ВСЕ же TL).

          Код не помню. Решение такое: запишем все координаты в массив x[n+m] — посчитаем все расстояния (с учётом w). Запустим поиск в глубину из a[1..n]. Будем идти во все непосещённые вершины, пока лента не закончится и поддерживать максимум.

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

            Там все тесты с суммой n+m хотя бы 50. Правда есть тесты, где одно из двуз очень маленькое.

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

Кто-нибудь собирается делать общую таблицу, как в прошлом году?

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

https://docs.google.com/spreadsheet/viewform?formkey=dC0yNUlQTDhlTkk1TDlmUlRpc0FSb1E6MQ Можете пока что заполнять эту форму, через некоторое время появится сводная таблица.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Комментарий удален администрацией по причине несоблюдения правил сайта.
»
12 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

У меня вот вопрос к авторам задач Для четвертой задачи предполагалось, что решение n*m*log^2(n+m) — полное? Просто у нас на сервере жюрисол с деревьями решений не заходит в две секунды, а в разборах написано, что это нормальное решение Мы приняли решение поднять TL до 3с

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

      Хмм, а можете сказать мне, почему мое решение за NMlog^2 падает по времени на 31 тесте?:( Неужели такая неаккуратная реализация?

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

        Выглядит очень хорошо. Но мне совершенно не нравятся вычисления корня в самом вложенном месте. А может и моё решение не проходит на серверах Вашего региона.

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

          Спасибо большое! На самом деле на регионе я получил 6 баллов из-за переполнения...Интересно то, что ТЛЕ у меня на сервере кодефорсес. Попробую предпосчитать длины всех ребер. UPD: не помогло:( вот

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

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

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

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

    Да, предполагалось. А сколько работало мое решение за NMlogN?

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

      Ваше за NMlogN — 1.508

      es с NMlog^2N — 2.656

      процессор: Intel(R) Celeron(R) D CPU 430 @ 1.80GHz

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

        Ну конечно тогда 3 секунды надо было. В рекомендациях вроде же как раз прописан двухкратный от main?

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

Из чего в третьей задаче следует, что оба слагаемых должны иметь ту же разрядность, что и сумма?

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

    Из условия. Второе предложение третьего абзаца.

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

    Из условия?

    "Теперь он хочет подобрать такие целые положительные числа A и B, чтобы их сумма была равна C, и запись каждого из них также состояла из n десятичных цифр и не начиналась с нуля."
»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Теперь можно обсуждать второй тур?

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

    Он должен был начать во всех регионах уже 6 часов назад. Даже если были задержки, то учитывая то, что участники не должны иметь доступа на CF, тут уже должно быть безопасно обсуждать. Так что пожалуйста!

    Для начала — резы Питера!

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

Кто-нибудь вообще решил последнюю (кроме составителей)?!!

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

    Ответ: да, Петрозаводск — Воронецкий Егор

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

    Да, поделитесь кто-нибудь решением/идеями. На контесте придумал только очевидное решение за O(n^3). Когда вышел из здания ИТМО, придумал решение за O(nd), что есть O(n^2). Хотя и не уверен, что оно бы зашло. А как там можно за O(nlogn), ума не приложу. Какая-нибудь хеви-лайт декомпозиция, которую мне так и не довелось пока изучить?

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

      А не мог бы кто-нибудь выложить условия? Ну или рассказать вкратце условия двух последних задач.

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

      Мне кажется, что в этой задаче нужно для каждой вершины хранить некоторые величины(количество вершин на расстоянии d от текущей + ещё что нибудь). Тогда для пересчета этой величины нам нужно слить информацию от потомков этой вершины. И, если я не ошибаюсь, если все время сливать массивы в наиболее большой, то можно добиться линейной асимптотики алгоритма.. (кажется на Петрозаводских сборах не редко всплывают задачи, в которых применяется подобная идея)

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

      Насколько я понимаю, основная идея такая же, как и на задаче K прошлого ВКОШПа. Нужно знать, сколько у данной вершины в поддеревьях вершин расположено на нужном нам расстоянии. Это можно узнать так: запомним времена входа и выхода в DFS. Отсортируем все точки сначала по возрастанию расстояния до них, потом по временам входа и выхода. Теперь, заходя в данную точку, мы перебираем все ребра, исходящие из нее. С помощью бинпоиска в полученном отсортированном массиве мы выделяем множество вершин, расположенных на нужном нам расстоянии, путь до которых от данной вершины лежит через через выделенное нами ребро. Тут возникает одна проблема — как посчитать множество вершин, не находящихся в поддереве данной вершины? Собственно, об этом нам очень долго и не особо понятно рассказывали на разборе :) Далее нам нужно за линию научиться искать произведения всех троек, что не особо трудно математически вывести. Итого получается N log N, плюс недосказанный мною кусок задачи. А вообще, очень скоро будет видеоразбор, советую его посмотреть :)

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

      Я видел авторское решение (у нас разбор проводил I_love_natalia, спасибо ему за это). Там такое шаманство: если у нас есть множества с полезной информацией о детях, а ответ для вершины — это объединение этих множеств (в данном случае не объединение, но смысл такой же), то будем добавлять в большее множество меньшее. Так мы испортим информацию в детях, но она нам уже не нужна. Все это выполнится за NlogN. Доказательство проскакивало где-то на кф и вроде бы есть на e-maxx (насчет последнего не уверен).

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

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

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

          Никакого шаманства

          Это образно. Кстати Костя использовал именно этот термин. Упихать правда квадрат в 10^5 он уже не смог, как в 1 дне на последнюю задачу. Зато я запихал куб для N <= 5000 сегодня.

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

      При составлении задач я рассчитывал, что большинство сильных участников придумает следующее решение за квадрат:

      1. Переберем каждую вершину как центр.
      2. Найдем в каждом поддереве количество вершин на расстоянии d/2 (тупым dfs'ом)
      3. Посчитаем сумму произведений по три (берем по вершине в 3 различных поддеревьях) — отдельная хорошая задача, формула для которой выводится из выражения для (a_1 + ... + a_i + ... + a_n)^3 = ...

      Возможно, существуют более простые решения за квадрат. Но такое решение ведет к верному — осталось научиться делать пункт 2 быстро!

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

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

        upd. Посмотрев разбор Дениса Павловича, понял, что не то придумал. Но была похожая идея. За O(n^2) можно было написать. Жаль, что не написал.

        Что, в общем, хочется сказать по поводу региона. Из-за невнимательности пролетаю мимо всероса (потерял на этом 61 балл в 3 задачах). Что ж, это справедливо, я считаю :)

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

        http://codeforces.net/problemset/problem/161/D — не?

        Кстати давать баяны не хорошо, т.к. если не решил задачу + не понял разбор — не решишь, а у кого-то наоборот будет преимущество.

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

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

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

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

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

            Идея что задачи должны уже скоро закончиться по рассказам ходят еще с начала 2000-ых годов. Я думаю еще раньше. Как видим, пока не закончились.

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

Когда примерно будет известен проходной балл на всеросс? И какой примерно он будет?

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

    В разборе Денис Павлович сказал, что примерно в начале марта. Не знаю, на сколько это правда. А проходной балл, думаю, будет высокий, потому что набрать баллов 500 было совсем не сложно.

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

      Надеюсь не больше 590

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

        Для какого класса?

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

          Для 10

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

            Вряд ли будет больше 590 для 10 класса. Для справки в 2012 году были следующие проходные баллы: 9 — 495 10 — 535 11 — 573

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

              Пишите в этой ветке, какие баллы ожидаете проходные. По классам.

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

По задаче 6 квадрат на сколько должен был проходить?

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

    40 баллов. Можно открыть условия, которые выше скинул Михаил, и там самому посмотреть.

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

Ребят, помогите разобраться, почему такое решение валится на WA на первой группе (n <= 50) тестов. http://pastebin.com/FxtAdftS. У нас в области тестирования ещё не было, поэтому решил сам посмотреть, чего ждать) Пока в тренировках WA-5. Идея примерно такая: зафиксируем три точки (две переберем, одна — номер 1). Построим окружность, отметим точки, которые на ней лежат. Найдём первую неотмеченную точку. Пусть теперь она первая, опять переберем две точки, построим ещё окружность и посмотрим, захватывает ли новая окружность все неотмеченные точки. Если так, то выходим. Спасибо

Upd. Как вариант — когда три точки лежат на одной прямой, а я пытаюсь искать центр опис. окр.

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

Кто-нибудь ещё кроме меня писал выпуклую оболочку в 7?

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

    У меня появилась такая идея, но потом я понял, что дальше с этой выпуклой оболочкой каши не сваришь. Вот ты, например, что делал?

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

      Перебирал все тройки соседних точек, лежащих на оболочке, строил по ним окружность и помечал из оставшихся точек те, которые лежат на этой окружности.
      Если все непомеченные точки лежат на одной окружности, то есть ответ (в конце проверяю точки первой окружности на принадлежность ко второй).
      Случаи для n <= 4 рассматривал отдельно.

      PS. Прошло на 100.

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

        Ну и зачем тут выпуклая оболочка?

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

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

          Зачем минусовать? Я написал своё решение, которое может быть не оптимально, но проходит на 100 баллов.

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

            Я тоже об этом думал, но меня вот такой тест завел в тупик.

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

Почему-то никто не спросил про C первого дня, чувствую себя совсем тормозом, но... Как решать?

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

Если кому нибудь нужен архив с авторскими решениями, тестами и разбором — то вот он.

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

Кто нибудь знает, где и в какие сроки будет проводится всеросс,

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

Не уверен, что у нас здесь присутствуют авторы решений и разборов задач, которые входили в материалы олимпиады, но хотелось бы отметить следующее:

Уважаемые авторы исходников и авторы разборов — не могли бы Вы в будущем стараться

  1. Максимально синхронизировать разборы сложных технических задач с исходниками. В этом году материалы по решению задач 4 и 8 были подготовлены так, что понимание этих решений и воспроизведение без копипаста требует крайне серьёзных умственных затрат. Не надо стараться писать разбор как поэму, чтобы её потом можно было зачитать по бумажке. Лучше описать всё так, чтобы после сравнения исходника и разбора даже у менее продвинутых людей не оставалось вопросов, не было опечаток в индексах. Каждая такая нестыковка сильно давит по нервам, особенно когда задачи приходят за пару дней до туров. Для проверки качества разбора можно применить старый способ — дать его кому то прочитать (например автору других задач) и спросить — всё ли он понял.

  2. Оформлять исходные коды максимально подробно. Давать переменным человеческие имена. Чтобы исходник не выглядел как будто писался автором на каком-то соревновании. Комментарии приветствуются.

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

Извините, наболело за эти дни.

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

    Не только присутствуют, но и занимают весьма высокие места в рейтинге CF (я не про себя). Можете, кстати, по суффиксам решений погадать, кто там есть :)

    Я согласен с замечаниями и понимаю, что разбор получился не лучший :( К сожалению, тут проблема в том, как готовится региональный этап. Скажу лишь, что все материалы от нас требовали к 15 ноября, кажется... В итоге кто умел — писал решения, другой — разборы, кто-то приводил это хоть к какому-то адекватному виду. Скажем, есть человек, который хорошо решает и пишет код, но не умеет формулировать (особенно, на бумаге) решение...