HolkinPV's blog

By HolkinPV, 11 years ago, In Russian

292A - SMSC

Для каждого момента i времени запомним количество сообщений z[i], которое нужно отправить в момент времени i. Теперь пройдем по каждому моменту времени от 1 до 106, поддерживая текущий размер очереди sz. На каждой итерации попробуем уменьшить размер очереди на 1, то есть выполним sz = max(sz - 1, 0), затем прибавим сообщения, которые нужно отправить в эту секунду, то есть выполним sz = sz + z[i]. На каждом шаге будем обновлять максимальное значение очереди и текущее время, если sz > 0. После выполнения цикла, если в очереди остались неотправленные сообщения, то нужно еще раз обновить ответ.

292B - Network Topology

В этой задаче нужно было посчитать степени каждой вершины и найти ответ. Замечу, поскольку n >  = 4, m >  = 3 и граф связный, то ответ однозначный.

1) все степени 2 и у двух вершин степень 1 — шина.
2) все степени 2 — кольцо
3) все степени 1 и у одной степень  > 2 — звезда
4) иначе неизвестно

292C - Beautiful IP Addresses

Задача решается перебором. Для начала переберем сколько цифр в каждом четверти мы возьмем, например AAA.B.CC.DDD. Теперь посчитаем количество символов в этой строке (AAABCCDDD) и переберем цифры на первой половине этой строки (поскольку строка должна быть палиндромом, то вторая половина однозначно восстанавливается). После этого проверим, что такой ip-адрес является корректным и содержит правильный набор цифр. Если ip-адрес удовлетворяет всем условиям задачи, то добавим его к ответу.

292D - Connected Components

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

У этой задачи много правильных решений. Изначально планировалось решение, которое предподсчитывает частичные dsu (структура данных disjoint set union) на префиксах и на суффиксах, то есть массивы ldsu[M][N] и rdsu[M][N]. После этого на запрос [lf ; rg] легко ответить за время O(N·A - 1), если объединить множества ldsu[lf - 1] и rdsu[rg + 1], где A - 1 -- обратная функция Аккермана (константа от dsu).

292E - Copying Data

У этой задачи много правильных решений. Изначально предполагалось решение, использующие корневую эвристику. Разобьем все запросы на sqrt(m) блоков. Будем поддерживать текущий массив b в виде отрезков в массиве z, который хранит четверки (lf, rg, type, start), где lf, rg — отрезок индексов массива b, type — 0 или 1, означающее из какого массива взяты числа для этого отрезка, start — позиция начала этого отрезка в массиве типа type.

На запросы будем отвечать в тупую, то есть честно пересчитывать как изменится массив z от запроса копирования и отвечать на запросы значения в позициях. Однако, каждые sqrt(m) запросов будем сливать данные из массива z в массив b, для того чтобы сам массив z сильно не разрастался.

Есть простое решение с деревом отрезков, которое умеет делать покраску на отрезке. Пусть пришел запрос копирования [lf ; rg], , тогда покрасим отрезок запроса [lf ; rg] в цвет, равный номеру запросу. Все запросы будем сохранять. Пусть пришел запрос значения в позиции x, тогда найдем цвет в дереве в этой позиции. Если такого цвета нет, значит мы находимся в исходном массиве b (выведем b[x]), иначе посчитаем смещение dx от начала этого запроса до нашей позиции x и выведем a[x + dx].

  • Vote: I like it
  • +51
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone translate tutorial of 292-D in english

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    English Translation-

    The restrictions in the problem were not very successful and provoked a solution to be written in a square; we tried not to let such solutions pass as much as possible.

    This task has many correct solutions. Initially, a solution was planned that calculates partial dsu (data structure disjoint set union) on prefixes and suffixes, that is, arrays ldsu [ M ] [ N ] and rdsu [ M ] [ N ] . After that, the request [ lf ; rg ] it is easy to answer in time O ( N · A  - 1 ) if we combine the sets ldsu [ lf  - 1] and rdsu [ rg  + 1] , where A  - 1 is the inverse Ackerman function (constant from dsu).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't understand the 292E (copy data) solution. Can someone help me out.