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

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

Обсуждаем, интересует решение J.

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

13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
J - втупую. Пусть мы хотим разбить дерево на куски размера X. Тогда нетрудно заметить, что ребро соединяет разные куски тогда и только тогда, когда размеры поддеревьев, на которые оно разбивает всё дерево, кратны X. Для каждого ребра найдём размеры поддеревьев, которые оно соединяет и проверим, делятся ли они на X. Если хороших рёбер ровно n/X - 1, то разбить на куски по X можно, иначе - нет. Ну и заметим, что обход по дереву нужен только один, потом уже по этой информации пересчитываем ответ для всех X.
  • 13 лет назад, # ^ |
    Rev. 7   Проголосовать: нравится +3 Проголосовать: не нравится

    Кому втупую, а кто сначала долго не мог победить ML2, хотя по всем расчётам выходило не более 100 Мб, а потом - TL3, когда на вроде бы худшем тесте (цепочка длиной 2042040) работало 4 с.
    OpenCup - хитрый турнир, тут что ни контест, то чудеса :)

    UPD. Короче, с пояснениями ниже всё стало более-менее понятно. Но если такие проблемы возникали у пишущих на C (уже даже не на C++!), то я боюсь представить, как пришлось оптимизировать решения командам, пишущим на Java.

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      вроде бы худший - 2882880
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      На варшавских контестах неасимптотические оптимизации можно не упоминать - они чуть ли не в каждой задаче нужны. Здесь, чтобы сэкономить память, можно было писать простой динамикой вместо рекурсивного dfs'а, поскольку дерево сразу отсортировано. И чтобы упихать по времени, пришлось полностью избавиться от делений. Это вроде всё стандартные приёмы.
      • 13 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Ну, в справедливость TL ещё как-то можно поверить. Но непроход по памяти таки остаётся загадкой. Собственно, вот, например, код. Откуда там 256 Мб?
        Или я неправильно понимаю, что при вызове функции на стеке выделяется память только под локальные переменные и адрес возврата?

        UPD. Короче, с пояснениями ниже всё стало более-менее понятно. Но если такие проблемы возникали у пишущих на C (уже даже не на C++!), то я боюсь представить, как пришлось оптимизировать решения командам, пишущим на Java.

        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Ещё как минимум там будет адрес текущей команды. Плюс возможно наличие промежуточных переменных, которые явно не объявлены. Плюс я не уверен в том, что на проверяющем сервере адреса 4-битные. В сумме может и накопиться на 256мб.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Считали с поправкой на возможную восьмибайтовость адресов. Но вот промежуточные переменные - они, видимо, всё и испортили.
            Интересно, кстати, а можно ли было бы отключить их создание посредством каких-нибудь директив препроцессору? И сильно ли это ухудшило бы время работы?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Решение будет получать TLE, даже если избавиться от dfs'а. Там вся веселуха с кэшем во время обхода дерева. Если делать обход на каждый делитель (хоть dfs'ом, хоть обычным проходом по массиву, как у меня) - TLE. Stigius не зря отметил, что в его решении обход дерева выполняется единожды. И если принять во внимание кэш, то худший тест - это совсем не цепочка. При обходе цепочки 1->2->3... обращения к памяти как раз последовательны. А вот если перенумеровать ее вершины случайным образом, то время заметно возрастет.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Три миллиона вызовов malloc отберут около 50 мегабайт под свои нужды.
    • 13 лет назад, # ^ |
      Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится
      дубль
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не знаю. У нас проблем не было. Просто мне кажется, у кого-то не оптимальное решение. Насколько я понял обсуждается решение за N*количество делителей. А можно за N + сумма числа делителей у чисел от 1 до N. И это вроде бы даже просто N. Заходит спокойно. 
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я сдал за O(N + D2), где D - число делителей N
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ну видимо это тоже самое, только мы много лишнего считали.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +20 Проголосовать: не нравится
            Для того, чтобы удовлетворить любопытных читателей, я всё-таки напишу здесь решение за O(N+D2):

            1) Сгенерим N чисел: a[i] = 1 + количество узлов во всех потомках i-го узла (совсем все, а не только непосредственные)

            Заметим, что для каждого делителя n нас интересует количество чисел среди a[i], делящихся на этот делитель.
            2) Рассмотрим b[i] = gcd(a[i], N). Как ни странно, он является делителем N. И что самое главное - для любого общего делителя N и a[i] (назовём его k) выполнено условие b[i] % k = 0

            3) Посчитаем все различные b[i] (совсем по тупому - будем хранить, сколько раз встретился каждый элемент). Заметим, что различных чисел b[i] не больше, чем делителей N.

            4) Научимся для фиксированного делителя N находить описанную перед п. 2 величину. Для этого просто переберём все различные значения b[i] и для тех, которые делятся на выбранный делитель возьмём посчитанное количество их вхождений в b.

            Первые три шага - за O(N), последний - за O(D^2).
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Еще один вопрос, может ли получиться так, что количество "хороших" ребер будет больше чем n / X - 1?
              Можно ли в таком случае разбить дерево на куски размера X?
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +5 Проголосовать: не нравится
                Если мы разрежем дерево по хорошему ребру на два, то нетрудно заметить, что в полученных поддеревьях все хорошие рёбра также останутся хорошими. Таким образом, если мы разрежем по всем хорошим рёбрам, то у нас получатся компоненты, каждая размера, кратного X. Поскольку всего вершин n, то таких компонент может быть не более n/X, т.е. хороших рёбер n/X - 1. Собственно, поэтому при равенстве и есть разбиение ровно по X.
            • 13 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      На яве в человеческом решении проблема было только в трёх миллионах = new ArrrayList<Integer>(); На списках вошло без проблем.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Может кто рассказать решения интересных задач? Т.е. A, B, I.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    Любую последовательность целых чисел можно разбить на последовательные куски, числа внутри каждого из которых  образуют свою арифметическую прогрессию. Причем каждый такой кусок будет пересекаться с соседними ровно одним крайним числом. Разве этого не достаточно чтобы свести задачу к баяну "найдите наибольший прямоугольник состоящий из единичек на 01-матрице" за O(NM)?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это сведение сразу провёл. А вот с этим баяном ни разу не встречался, потому чего с ним дальше делать, с ходу не придумал.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    А могу.

    будем считать клетку матрицы хорошей, если она находится строго внутри некоторой прогрессии как по горизонтали, так и по вертикали. Т.е. a[i][j] == (a[i-1][j] + a[i+1][j]) / 2 == (a[i][j-1] + a[i][j+1]) / 2. Составим матрицу в которой еденичками будут помечены все хорошие клетки и ноликами плохие. Решим стандартную задачу о поиске максимальной подматрицы только из едениц перебирая все нерасширяемые подматрицы из единиц. Очевидно, что все перебраные в процессе матрицы нам подходят. Но помимо них нам возможно подходят и несколько более расширенные матрицы. А именно мы к каждой матрице из единиц возможно можем с каждой стороны дописать ещё по строке(столбцу). Но не более одной. Иначе нашу матрицу из единиц можно расширить. Проверим для каждой нерасширяемой матрицы 2^4 вариантов дописывания строк по бокам. Из всех выберем максимальный.

    По крайней мере это наше решение.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    В. Рассмотрим 2 крайних пути из первой вершины запроса в вершину N - то есть по самый левый и самый правый. В силу условий достижимости из и до крайних вершин (1 и N) делаем вывод, что вторая вершина должна быть достижима из первой, а для этого достаточно чтобы вторая вершина лежала внутри многоугольника с границами-путями, которые мы рассмотрели. А для этого достаточно посмотреть, что поднявшись на сколько-то вверх и сдвинувшись на сколько-то вправо из второй вершины мы пересечем наши пути. Мы это делали аналогом двоичного подъема из первой вершины. Как-то так.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    I. По инвертируем ребра. Задача стала такой: найти анти-клику максимального веса.
    Построим сеть: из истока ребра в первую долю пропускной способностью IQ, ребра которые есть в инветированном графе пропускной способностью +inf, ребра из второй доли в сток пропускной способностью IQ. Найдем в графе макс поток. Утверждается, что если посмотреть на мин. разрез то станет очевидно, что он - минимальная сумма людей которых мы не возьмем.
    Кстати, простые потоки проходили или я Диница не зря сразу писал?

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      прошло масштабированием
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Прошёл простой поток с bfs. Пробовать совсем простой с dfs у нас наглости не хватило :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Еще одна вариация на тему А.

    Будем считать клетку хорошей, если она левый верхний угол маттрицы 3*3, которая хорошая.
    Надо найти квадрат из единиц максимизируя (w+2)*(h+2). Переберем верх. Будем перебирать низ, параллельно насчитываю битовую маску тех, которые единички во всей полоске. Осталось найти самую длинную подстроку из 1 в полоске, что делается предподсчетом всего для масок от 0 до 2: 16 - 1. Это получает ТЛ14. Заметим, что длина которую мы считаем только уменьшается при добавлении новых строк. Значит если она слишком маленькая даже если останется такой же до конца, то надо сделать break. С таким отсечением по ответу зашлою
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Как решать задачу E, написал корневую декомпозицию, получаю WA4?

UPD В дорешке зашло.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если коротко: нам нужно находить изменения при удалении/добавлении плеера. Эти изменения - это те норы, до которых он достаёт за вычетом тех, которые достают соседи. Соседей находить легко, если держать все плееры в сете. Находить количество сусликов, которые попадают в отрезок - бинпоиском.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Пусть хотим удалить плеер стоящий в x, найдем ближайщий от него плеер слева и справа, пусть их координаты x1, x2, тогда наш плеер затронет норы на отрезке

    [max(x1+L+1, x-L), min(x2-L-1,x+L)]

    Номер норы по X, можно искать бинпоиском. Добавление аналогично.

  • 13 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    а мы писали дерево отрезков с прибавлением на отрезке, с минимумом и количеством минимумов. Нужно просто уметь считать кол-во нулей во всем дереве. Будем в дереве поддерживать, сколько плееров покрывают нору.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      Еще проще решать ее SQRT - декомпозицией. В каждом блоке храним ответ - кол-во сусликов, а также кол-во плееров которые полностью покрывают данный блок. Также для каждого суслика храним кол-во плееров которые его покрывают. Границы находятся бинпоисками, а дальше я думаю все очевидно.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        я бы не рискнул такое решение писать, большой шанс получить ТЛ, а потом заниматься неассимптотической оптимизацией
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Красивое решение

UPD не туда.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать F и G ?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    G.
    Посчитать динамику d[i][j] - куда придем из сида i, если сделать 2^j шагов и h[i][j] - хэш битовой последовательности, которую мы получим, если начнем в сиде i и выпишем 2^j битов.
    Дальше, для каждого сида посчитать хэш, если сделать n шагов и сравнить с данным.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Надо заметить, что лучше поменять индексы местами: массивы 17 × 106 и 106 × 17 весьма отличаются друг от друга. Особенно если это массивы массивов в яве >.<
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Можно заметить, что двумерный массив необязателен и обойтись только O(M) памяти
  • 13 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится
    F. Жадность. Посортируем команды по убыванию di. По очереди сначала попробуем запихнуть куда-то di, если не получилось то di и di. Каждый раз выбираем прищепки которых меньше всего, но достаточно для этих вещей. Это можно делать так: когда поюзали цвет объеденили его со следующим снмом. Тогда найти цвет = бин.поиск + максимум в множестве.
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Кто нибудь знает 8 тест в задаче K?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Может быть все точки лежат на одной прямой?
    • 13 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      Ох блин, я понял ошибку, это снова опечатка в одном символе
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    у нас был ВА, когда не учитывали, что два коллинеарных вектора компланарны с любым другим. из-за этого иногда был YES вместо NO
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите, плз, как решать Q.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Я затолкал обычный bfs с таким отсечением: не включаем фонарь, если слева и справа от него фонари выключены. 
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Можно по-подробнее?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Ну делаем поиск в ширину. Сначала в очередь кладём битмаску начального состояния. Потом все битмаски, которые получаются из неё за один ход, и т.д. Ну и с учётом отсечения, о котором написано выше.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      странно, с такой же оптимизацие не зашло... поставил отсечение по итерациям-прошло
      • 13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Что такое отсечение по итерациям?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          ну просто считаю итерации и смотрю, если количество итераций стало больше какой-то константы(в этой задаче например 108) то прекращаю выполнение, несмотря на то, что алгоритм еще должен поработать
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            У меня была мысль отсекать по клоку, но я постеснялся. Видимо, зря:)
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              ф-я clock()  вроде на ejudge'e 0 всегда возращает
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Ты неправ. сlock() на ejudge'e работает вполне нормально.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится -14 Проголосовать: не нравится
                Я не раз пихал с помощью клока. Например, вместо Гаусса какого-нибудь Зейделя.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            Хм, а ответ-то ты какой тогда выводишь?
            • 13 лет назад, # ^ |
                Проголосовать: нравится -14 Проголосовать: не нравится
              Утверждается, что ноль хотя бы один раз поапдейтится за это время.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                А что, bfs несколько раз обходит одну и ту же вершину???
                • 13 лет назад, # ^ |
                    Проголосовать: нравится -14 Проголосовать: не нравится
                  Я лично писал bfs с апдейтами
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Можешь объяснить, что это значит, на примере задачи Q?
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится -13 Проголосовать: не нравится
                      Вот как он у меня был написан. Я прибавлял единицу в маске и делал этот переход равным единице. После этого я отнимал все лишние единице в маске и делал этот переход равным нулю. 
                      • 13 лет назад, # ^ |
                          Проголосовать: нравится 0 Проголосовать: не нравится
                        ================================
                        А почему бы просто сразу не делать единичный переход в итоговое состояние фонарей?

                        Но даже если так, всё равно не понимаю, зачем тебе ноль обходить несколько раз. Встретил ноль - и сделал break.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я долго подбирал константу, не идем в те состояния в которых количество включенных лампочек больше чем изначальное количество включенных лампочек + 8
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    У нас вообще тупой бфс зашел. Просто написали свою очередь и битсет.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Простой бфс у меня получил ТЛ. Тогда я придумал следующую оптимизацию.

    При больших N где-то в середине наверняка будет хотя бы один нолик, который при некоторой оптимальной последовательности действий ни разу не будет включен. Тогда можно разбить исходную строку этим ноликом на две, и решить задачу для них по-отдельности. Перебираем в качестве таких разбивающих ноликов несколько средних ноликов, и это сдается.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Мне очень интересно, что за тактика была у команды Moscow SU Chapelnik: Shteiner, Panin, Blinov (div. 2), что в середине первого часа контеста они сделали три посылки по трём разным задачам в 0:41, 0:42 и 0:43.

Последняя успешная посылка была в 0:16. Затем во сколько-то одно бревно по Q, и три синхронные (но неудачные) посылки по разным задачам через 25 минут после предыдущего АС.

Может, конечно, два раза задачей ошиблись)

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

    Мой сокомандник писал H. Я его прервал, на 41й заслал простой фикс по Q. Потом он заслал Н не туда. Потом туда.

    Стоит ли говорить, что все три сабмита были неудачными. 
    • 13 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      Ну да, об этом тоже думал. Но код чужих сабмитов (вроде?) никак не посмотреть.

      Думал ещё, что может инет отвалился.

      Поздравляю с победой в 2 диве! :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Вообще, по-моему, любое количество неудачных сабмитов даже в течение одной минуты не подозрительно.

        Чужой код смотреть нельзя, но можно подать апелляцию, если что. Да, ещё стоит заметить, что мы писали из официального сектора, где уж точно по одному компу на команду. Ну и к тому же у нас код пишут только двое. 

        Спасибо)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну вот я примерно так и подумал, и решил, что нечего Снарку тут апелляцию писать)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто-нибудь может рассказать как решать O и P?
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Решение задачи O разобрана выше, P решается в лоб, проверка на простоту для чисел до миллиона проверял решетом, а больших чисел в лоб.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Или блочное решето для вообще всех чисел. Кстати, интересно, как проверка в лоб могла заходить по времени.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А где O разобрана?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      это задача J для див1 только у них ограничения по жестче.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    влоб: просто перебираем отрезок, сумму на котором будем брать и смотрим: простая ли сумма?

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      да
      • 13 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится
        вот дерьмо, а не задача(
        • 13 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится
          Ну сумму мы конечно за константу при этом считаем.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            ну это то само собой, просто мы просидели весь контест и думали, что там что то более умное, так как мы думали в лоб не успеет, а это оказалось обычное безидейное хрень, которую просто надо было написать
            • 13 лет назад, # ^ |
                Проголосовать: нравится +6 Проголосовать: не нравится
              Ну, миллиард за 7 секунд - относительно правдоподобно.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +13 Проголосовать: не нравится

                ==============

                просто я не понимаю зачем такие огромные ограничения ставить 109 итераций, неужели нельзя обойтись 108 и ограничения на время 1сек

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как подать апелляцию?

Я захожу в раздел Appeals, делаю попытку, а потом пишу сообщение жюри, но мое сообщение все еще не прочитано. 

Все ли я делаю правильно?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    Вы не поверите, но то сообщение не прочитано, означает, что его еще не прочитали! Думаю если оно отображается, то рано или поздно жюри его увидит.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я понимаю, что его не прочитали.
      Может быть, надо как-то не так отправлять сообщение, вот я  к чему.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
кто-нибудь может объяснить, что за беда: сдаю этот код на О-МЛЕ2
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ты функцию can вызываешь если та вершина куда идешь не предок текущей и возможно бесконечно много ходишь...
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      да ничего подобного, оказывается там временные переменные или че то такое: выше написано...

  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    если запомнить дерево списком смежности то должно пройти МЛ
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      дело не в этом, там вообще куда меньше 256мб в этом коде(видимой памяти) и вообще я уже избавился от МЛЕ2, теперь ТЛЕ19 - наверное N*кол-во делителей числа не проходит в принципе(
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
какого черта у меня дома работает Р за секунду, а на сервере ТЛ1 О_о
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      нене, уменьшая константу - WA5 становится. сейчас протестил один из кодов другой команды, прошедший на контесте - тоже выдает ТЛ1
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      видимо просто для дорешки оставлен слабенький серв
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Первый тест - из условия. Если написать заглушку на него - будет TL5, ТL17 или что-то подобное. А может и зайдёт. Это удивительно и странно.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    +1.

    У нас тоже так было. Причем один и тот же код сначала получает TL 17, а потом TL 1.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      тоже долгое время было TL17. Немного ускорили Решето(переходили не j += i, а j +=i * 2) и зашло.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а как считывать строку в М? там же 1000 тестов и длины строк до 108/2 получается около 1010 символов
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я подозреваю, что там те же самые тесты, что и в D, т.е. их в сумме 50 мб. А вот в D пришлось писать хитрый ввод - я, например, читал fread'ом блоками по 1мб.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А какое решение в D?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну мы писали что-то такое, дописать не успели:

        Будем считывать по одному символу, пока не увидим, что мы встретились. Это сделать легко, так как знаем, что суммарно подъемов и спусков N. После этого моделируем как левый пошел назад. Либо встретимся либо дойдем до начала. Иначе нам не нужно то что мы уже считали, а надо пойти вторым вперед пока не встретимся. Проверять встритились или нет так же как и в первый раз. Ну ко всему этому надо добавить рациональную арифметику заодно.
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

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

          Если они первый раз встретились строго выше земли (а из условия это всегда так), то левый на обратном пути спустится до низу строго раньше, чем правый. Потому после первой встречи - точно такая же логика, как и до неё, только рассматриваем уже правого муравья вместо левого. Более того, в формулах возникает деление только на 4 и на 5. Поэтому если домножить всё на 400, то можно все расчёты вести просто в лонгах, делить только при выводе ответа.

          Если делать всё аккуратно, проблем вроде никаких не возникает. У меня была мелкая опечатка в копипасте, потому сдал только в дорешивании.

13 лет назад, # |
Rev. 2   Проголосовать: нравится -45 Проголосовать: не нравится

Мне одному показалось, что ряд задач див2 сегодня были ненамного проще задач див1 и намного сложнее задач общей секции?

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно как по человечески H решать, я думал думал, забил и вогнал квадрат с битовыми оптимизациями. Сейчас я знаю как сделть что-то вроде этого, но уже за "эн логарифм эн", а как правильно решалась задача?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если 1 символ, то ответ HM.
    Иначе, выкидываем первый и последний символы. 
    Теперь смотрим, чего было налито больше, то и выводим. Если было равное число запросов на H и на М, то выводим не то, что стоит на последнем месте(учитывая, что последний сейчас - это предпоследний в начальной последовательности).
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Моделировать процесс. Только объем чашки считать большим, например, 20e20)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я на контесте написал решение за О(N), но оно, скорее всего, тоже не человеческое. Код: http://pastie.org/private/n5b8pnrwcuib7xb1vzdzg. Формула такая: когда мы доливаем молоко или чай на k-ом по счету шаге (наливание чая и молока в пустой стакан считаем нулевым шагом), то мы прибавляем к числителю суммы (2^(n - k) - 1) * 2^k.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    я вот так решил http://pastebin.com/fhsb0FLm
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
можно посмотреть на код P, который проходит в дорешку?
13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
Мы, конечно, сыграли контест очень плохо и сейчас этот пост заминусуют, но все же.

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

Если решето поставить до 10^6, то проходит и в дорешку.
А вот в D пришлось писать хитрый ввод - я, например, читал fread'ом блоками по 1мб.
Я долго подбирал константу
Решение будет получать TLE, даже если избавиться от dfs'а. Там вся веселуха с кэшем во время обхода дерева.

По-моему, такие контесты не нужны. Посмотрите на задачи с NEERC, на задачи этого саратовского четвертьфинала, на последние несколько контестов на Тимусе. И потом на этот. Неужели так увлекательно загонять шаманские оптимизации под 10 миллионов ввода и 15 секунд тайм-лимита?

Дискасс.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    на мой взгляд довольно смело с твой стороны это написать, ведь скорее всего многие так считают(и я тоже), но побоялись написать
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Мне всегда нравились польские задачи. Но меня, как и тебя, просто бесят эти непонятно зачем задранные ограничения. Другое дело, что они нас не заставляют решать их задачи. На их задачах полезно потренироваться, но я тоже согласен, что такие контесты еще подходят для Петрозаводских сборов, но уже не подходят для этапа Opencup'а.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -18 Проголосовать: не нравится
    Мне кажется, Олегу Христенко надо просто умножать текущие TL на 2-3. Все равно ограничения задраны так, что палево не пройдет, зато от контеста больше людей получат удовольствие.

    Тем более, что для Java там вроде есть +0.5 сек., но при таких ограничениях впритык добиться равноценности TL для C++/Delphi и Java значительно сложнее.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Мне кажется, подобные высказывания я уже слышал после ГП СПб. И я выскажусь точно так же, как и там: задачи отличные. Их действительно интересно решать. В них отличные идеи, контест в целом неплохо сбалансирован. Магия с fread'ом - она была нужна, иначе теряется идея задачи - сделать ввод намного больше, чем ML. В остальном я не вижу никаких проблем - если аккуратно всё писать, косяков не возникает. С пониманием всё точно так же, как и на финале - заходит только оптимальное решение. И заоблачные ограничения - именно для того, чтобы отсекать кривую асимптотику.

    Снарк в последнем Петрозаводске высказывался, что поляки очень любят действительно оптимальные решения. Поэтому сам он ограничения ставит не те, которые они предлагают, а по самому медленному из авторских решений со стандартным запасом в 2-3 раза. Если вы и под такие ограничения не можете запихать - может, стоит поучиться кодить? И под неасимптотическими оптимизациями я имел в виду именно это - нормальный код, а не такой, как на упомянутом Тимусе, где из последних контестов по редкой задаче нету 20-кратного запаса по времени и потому заходит вообще всё.

    • 13 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится
      просто не очень очевидно например, заходит 109 за 7сек или нет(и так в каждой задаче), потому что с такими нестандартными ограничениями задач обычно не бывает
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Олег сказал, что в этот раз было 4 от медленных авторских. То есть по I 2.5 c медленное авторское (и 0.1 с быстрое). Нам пихать пришлось I (добавили в ФФ пару оптимизаций из Диница) и D (заменили взятие по модулю и деление на 2 на шифты). С другой стороны, зная, что это поляки, мы очень многое сразу писали очень оптимально (в F я не рискнул сделать TreeSet и решал за линию)