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

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

В связи с тем, что .masterhost продолжает держать opencup.ru и snarknews.info на серверах, доступных только с российского IP, выкладываю ссылки на первый и второй дивизионы ГП ICL:

http://158.250.33.215//team.cgi?contest_id=10174 — Division 1

Результаты Div1:

http://158.250.33.215//team.cgi?contest_id=10184 — Division 2

Результаты Div2:

Старт, как обычно, в 11-00. Этап будет учитываться в отборе на Чемпионат Урала.

Update:

Upsolving

Appeal

Отдельно результаты из Казани Div1 (студенты)

Отдельно результаты из Казани Div2 (школьники)

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

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

Еще бы ссылки на таблицы результатов для болельщиков.

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

Где таблица?

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

Как решать B, C, F, G, I, K?

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

    Расскажу как решать F. На контесте не сдали, забыли закомментить отладочный вывод за 3 минуты до конца и получили ВА1, но в дорешивании прошло. Идея такая: Найдем k такое, что pk ≤ n < pk + 1.

    Заметим, что количества апельсинов на дереве равно pm - a[m - 1]pm - 1 - ... - a[0]p0. При этом a[i] равно либо 0, либо 1. Тогда если два дерева дают в сумме n то это один из трех случаев:

    1. Первое дерево это pk - a[k - 1]pk - 1 - ... - a[0]p0, а у второго степень  < k
    2. Оба дерева с полиномами степени k
    3. Одно дерево это pk + 1 - a[k]pk - ... - a[0]p0, а у второго степень меньше  < k + 1

    Рассмотрим каждый из них отдельно.

    1. Можем записать следующее равенство pk - n = b[k - 1]pk - 1 + ... + b[0]p0. При этом среди коэффициентов b[i] должен быть ровно один равный -1, а остальные должны быть из множества {0, 1, 2}. При этом каждый коэффициент 1 увеличивает ответ для этого случая в 2 раза. Чтобы расставить так коэффициенты просто разлагаем n - pk в p-ричной системе счисления и меняем последовательно все коэффициенты на отрицательные, начиная с p0.
    2. Имеем такое равенство 2pk - n = b[k - 1]pk - 1 + ... + b[0]p0, при этом b[i] находятся в множестве {0, 1, 2} и должна быть хотя бы одна единица (чтобы исключить возможность взять 2 одинаковых дерева). Каждая единица увеличивает ответ вдвое. b[i] находим раскладывая 2pk - n в p-ричной системе счисления.
    3. Самый сложный случай, имеем равенство pk + 1 - n = b[k]pk + ... + b[0]p0. Среди b[i] должно быть не более 1 отрицательного числа, а если оно есть, то обязательно равное -1, при этом остальные b[i] из {0, 1, 2}. Если нет ни одного отрицательного, то если b[i] = 0 — то i может быть степенью второго полинома, тогда каждая единица до этого увеличивает ответ вдвое, а все коэффициенты после i должны быть равны 0 или 1. Если есть отрицательное — то оно заведомо степень второго полинома. Чтобы найти b[i] сначала разложим в p-ричную систему pk + 1 - n. Чтобы сделать один из коэффициентов отрицательным, надо рассмотреть каждую пару b[i] = p - 1, b[i + 1] = 0 и заменить ее на b[i] =  - 1, b[i + 1] = 1.

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

    Вот код на JAVA: http://pastebin.com/y8JXFUg9

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

    B вот так сдали: Не сложно придумать ДПшку f(lx, ly, ux, uy) = solution, где solution — вектор времен (т.е. solution[1] — время когда ячейка с 1 освободится, solution[2] — когда 2я и т.д., если solution[i] = 0, значит iго числа не было в прямоугольнике) и solution лексикографически минимальный среди всех возможных вариантов, т.е. для каждого прямоугольника посчитать оптимальный разрез, чтобы в итоге получились времена solution.

    Для расчета надо перебрать 4 варианта разреза — какой раньше будем делать — для каждого разреза получаются два прямоугольника в общем случае — sol1, sol2, чтобы померджить ответы надо просто sol1[i] | sol2[i].

    Это будет что-то (n * m)3 и по памяти столько же. Так как числа solution[i] не большие, то можно в int по 3 числа засунуть, но это тоже получается много.

    Можно заметить, что можно хранить только для минимального в прямоугольнике актуальное время (будет от 1 до 4), а для остальных хранить смещение по времени (от 0 до 4), т.е. получается на значение по 3 бита и в long long можно по 21-му числу запихать. Это уже получается (n * m)2 * (n * m) / 21. Такое зашло. Ну и там на самом деле делить на некоторую константу, потому что прямоугольников и еще не для всех считать надо.

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

    На туре не увидел, что в B динамика. Снимите мне 1000 рейтинга)

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

      Хорошо Вернул назад :)

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

        Наверное это плохо, когда из системы просто так исчезает 1000 очков рейтинга — всякие плохие спецэффекты возникнуть могут. Добавьте его мне.

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

          Сумма рейтингов прилично убывает за каждый раунд. Например сумма изменений за 114 раунд чуть меньше -35000(оба дива).

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

        Это новый способ борьбы с инфляцией рейтинга? :)

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

        Спасибо! Это заслужено :)

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

        Ой, как здорово, а можно мне снять 2016 рейтинга?

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

          Нужна кнопка "уменьшить себе рейтинг до нижней границы дивизиона". Для борьбы с инфляцией — самое то! :-D

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

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

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

Как решалась Н (точнее, как разбирать в ней частный случай k = 1) и кто до какого теста дошел в N?

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

    В H можно написать например какой-то такой брут:
    for(i=1;i<=max(a[1]-1,n-a[1]);i++)ans+=((a[1]-1)/i+1)*((n-a[1])/i+1);
    cout<<ans-max(a[1]-1,n-a[1])+1<<endl;
    a[1] тут позиция нашего единственного дерева.
    Теперь заметим что различных пар среди ((a[1]-1)/i+1), ((n-a[1])/i+1) будет немного не смотря на то что i может быть очень большим. Тогда за одну итерацию будем считать какая получается пара и сразу сколько таких будет. Код

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

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

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

opencup.ru по-прежнему недоступен. Можно ли выложить прямые ссылки ещё и на дорешивание?

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

Как решается задача D??

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

    Отсортируем машины по координате Х, т.е. по времени, за которое они доехали бы до моста, если бы других машин не было. Пусть время въезда каждой машины на мост будет time[i], а номер машины среди всех машин с таким же временем (ведь несколько машин могут заехать на мост одновременно) будет Num[i].

    Рассмотрим теперь машину номер k. Если X[k] > time[k-1], то time[k] = X[k], Num[k] = 1. Иначе, если Num[k-1] < B, то time[k] = time[k-1], Num[k] = Num[k-1] + 1. Если же Num[k-1] == B, то time[k] = time[k-1] + 1, Num[k] = 1.

    Ответ: time[N]

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

Как решалась задача L?

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

    Можно было решить с помощью стэка — в нем будут хранится текущие потенциальные победители: Идем слева на право. Пусть мы рассматриваем машину i: выкидываем из стэка всех игроков, которых выигрывает машина i. Если стэк пустой или "ничья" у машины i с последним невыкинутым элементом стэка, то кладем i в стэк. В итоге стэк — это ответ.

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

В G зашло в дорешивании следующее:

1) Пусть time(X,Y) = INF, если игрок X не может поймать игрока Y, и максимальному времени, сколько Y может сопротивляться, если X может поймать Y. 2) Тогда пусть win(A) = time(A, B), если time(A, B) < time(C, A) (вроде как естественное условие, но может кстати и без него будет работать?..) и time(A, B) < time(C, B) (иначе C может "встать между A и B и добиться ничьей), и INF иначе. Аналогично для win(B) и win(C). 3) Тогда если среди win есть единственный минимум, то он и побеждает в игре для троих, иначе ничья.

Выглядит правдоподобно, но это далеко не первая итерация, и все предыдущие тоже выглядели правдоподобно :) Может у кого-то есть объяснение или более простое работающее решение?

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

    о, что-то похожее на авторское =)

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

    alexey.enkov даже умеет доказывать корректность такого решения

    думаю, что вряд ли существует что-нибудь попроще :)

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

    Как считать ф-цию TIME? В ней нужно учитывать, что есть ещё враг, который может всё обломать? Вот рассмотрим например третий сэмпл: 3 3 1 2 1 3 2 3 1 2 3

    time(ALICE,BOB)=1; time(ALICE,CEASER)=1; time(BOB,ALICE)=INF; time(BOB,CEASER)=1; time(CEASER,ALICE)=INF; time(CEASER,BOB)=INF;

    win(ALICE)=1; win(BOB)=INF; win(CEASER)=INF; => ANS: ALICE

    Где я не понял решения?

    Ещё: как решалась задача Е(Фифекты Гечи), задача J(Острова) и задача N(Числа)?

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

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

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

      Е — пусть мы что-то сделали и у нас получилось
      a1 первых операций, a2 операций и.т.д.
      min(ai) = 0, ибо можно каждое уменьшить на 1.

      Ясно, каких операций меньше всего(0).
      Из этого ясно, сколько всго операций.
      Посчитаем, сколько тогда должно быть все остальных операций. Там получается уравнение вида, ax = b, если решений нет, то сразу падаем.

      Осталось восстановить порядок, как делал я:
      Скидаем в приоритетную очередь (номер, стартовое_количество), наверху — минимальное по кол-ву. Достаем очередной минимум на i-ом шаге: если стартовое кол-во < i — падаем, иначе выводим и увеличваем на k-1 стартовое_количество.

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

      В этом сэмпле никто никого не может поймать — они же на цикле? Поэтому все time равны INF.

      Считать time примерно так — построим ту часть графа, начинающуюся в вершине B, которая является деревом — т.е. как только мы доходим до цикла, помечаем эту вершину как "выход" и дальше не идём. В этой части есть ровно одна вершина, откуда стартует A — либо где он сейчас, либо где он появится. Подвесим часть за неё, тогда нужно на пути от B до корня понять, докуда B ещё может дойти, и из всех этих вершин найти самого глубокого ребёнка, считая глубину цикла INF.

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

      Ну то есть, отвечая на второй вопрос — для подсчета time про третьего вообще забываем.

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

      Задача E.

      Пусть Ai — стартовое кол-во людей с i дефектом, а Bi — конечное. Di = Bi — Ai — разница между начальным и конечным значением.

      Для начала проверим, чтобы сумма всех Di была равна нулю. Если это не так, то ответ -1. Если все Di равны нулю, то ничего делать не надо и ответ 0. Далее рассмотрим общий случай:

      Пусть K — общее количество операций, которое мы совершили над нашим множеством. Ei — количество встреч людей без i-го дефекта.

      Тогда для каждого человека должно выполняться следующее уравнение:

      Ai + (m — 1) * Ei — (K — Ei) = Bi

      Что преобразуется в:

      Ei * m — K = Di . Тогда, Ei = (Di + K) / m

      Теперь, для каждого человека нужно найти такое минимальное K > 0, чтобы (Di + K) делилось на m и (Di + K) / m >= 0. Для отрицательных Di, K равно Di, а для неотрицательных, найдем Div = Di / m + 1. Тогда Di + K = Div * m, K = Div * m — Di.

      Среди всех людей найдем максимальное K. Теперь нужно проверить всем ли людям данный K подходит. Т.е. для всех людей (Di + K) должно делится на m. Если это не так, то ответ — 1. А заодно для каждого человека найдем уже финальное Ei.

      Теперь мы знаем для всех — Ei и нам нужно оптимальным образом выполнить эти операции. Заведем очередь с приоритетами, где на вершине будет хранится человек с минимальным текущим Ai и которому еще нужно сделать операции Ei. Достаем человека. Если его текущее значение — кол-во проведенных операций < 0, то ответ -1. Иначе прибавляем ему значение m и если ему нужно сделать еще операции, то добавляем его обратно в очередь.

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

Расскажите, как решать B?

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

Про задачу J

4 4
0112
1100
1000
1110
1 1
4 4

Кажется, правильный ответ NO. Мое AC-решение на opencup выдает YES. weak tests?!

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

    Кажется, правильный ответ YES. Можно дойти таким образом: (1,1)->(1,2)->(1,3)->(1,4)->(1,3)->(1,2)->(2,2)->(2,1)->(3,1)->(4,1)->(4,2)->(4,3)->(4,4)

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

      А, я перечитал второй sample. Я не понял задачу, но получил по ней Accepted :)

      Оказывается, слово "подряд" означает "два раза последовательно" :-D

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

Как решалась К?

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

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

    Вычтем из каждого слагаемого суммы $i$. Получим

    Очевидно, что если мы умеем считать $ansLeft`$, то мы сосчитаем и ansLeft. Для того, чтобы его сосчитать, воспользуемся деревом отрезков, в вершинах которого хранится сумма и количество элементов на отрезке. Тогда, если у нас на отрезке лежат все элементы, меньшие  - 2x + 1, то ответ равен их сумме плюс количество оставшихся (т.е. тех, которые больше либо равны  - 2x + 1) умноженное на  - 2x + 1. Поэтому просто будем класть запросы в порядке возрастания  - 2x + 1 и находить сумму на отрезках.

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

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

Внезапно вспомнил о задаче C (сосульки) — что-то её так и не разобрали. Как решать?

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

    Эгегей!

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

      Я попробовал написать на контесте примерное следующее:

      Отсортируем все шарики в порядке увеличения высоты, и будем рассматривать их в этом порядке: будем помечать каким-нибудь образом, что отрезок с x_i-r по x_i+r покрывается для каждого шарика. Если добавлять их с приоритетом, зависящим от высоты, то потом, пробегая по массиву длинной 10^7, который отвечает за сосульки, можно для каждой сосульки легко определить, какой именно шарик её убивает первым. Затем нужно взять первые (по времени) 10^5 событий вида сосулька убивает шарик и просто вычислить ответ по их значениям (просуммировав и поделив на количество).

      Решение, на самом деле, не зашло(получило ва), но мне кажется, что из-за моей криворукости, а не из-за неправильности. Извиняюсь, если объяснение непонятное =)

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

      Затем отсортируем все эти события и будем обрабатывать их слева направо, при этом храня set из всех ординат "текущих" шариков. Будем рассматривать соседние события и помечать все сосульки, соответствующие промежуточным точкам между двумя последовательными событиями тем шариком, что находится в вершине set'a. Всё остальное, вроде бы, должно быть понятно.

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

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

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

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