codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

292.md (6290B)


      1 Source: https://codeforces.com/blog/entry/7371
      2 
      3 [292A - SMS-центр](/contest/292/problem/A "Чемпионат КРОК 2013 - Раунд 1")
      4 
      5 Для каждого момента *i* времени запомним количество сообщений *z*[*i*], которое нужно отправить в момент времени *i*. Теперь пройдем по каждому моменту времени от 1 до 106, поддерживая текущий размер очереди *sz*. На каждой итерации попробуем уменьшить размер очереди на 1, то есть выполним *sz* = *max*(*sz* - 1, 0), затем прибавим сообщения, которые нужно отправить в эту секунду, то есть выполним *sz* = *sz* + *z*[*i*]. На каждом шаге будем обновлять максимальное значение очереди и текущее время, если *sz* > 0. После выполнения цикла, если в очереди остались неотправленные сообщения, то нужно еще раз обновить ответ.
      6 
      7 [292B - Топология сети](/contest/292/problem/B "Чемпионат КРОК 2013 - Раунд 1")
      8 
      9 В этой задаче нужно было посчитать степени каждой вершины и найти ответ. Замечу, поскольку *n* >  = 4, *m* >  = 3 и граф связный, то ответ однозначный.
     10 
     11 1) все степени 2 и у двух вершин степень 1 — шина.  
     12 2) все степени 2 — кольцо  
     13 3) все степени 1 и у одной степень  > 2 — звезда  
     14 4) иначе неизвестно
     15 
     16 [292C - Красивые IP-адреса](/contest/292/problem/C "Чемпионат КРОК 2013 - Раунд 1")
     17 
     18 Задача решается перебором. Для начала переберем сколько цифр в каждом четверти мы возьмем, например *AAA*.*B*.*CC*.*DDD*. Теперь посчитаем количество символов в этой строке (*AAABCCDDD*) и переберем цифры на первой половине этой строки (поскольку строка должна быть палиндромом, то вторая половина однозначно восстанавливается). После этого проверим, что такой ip-адрес является корректным и содержит правильный набор цифр. Если ip-адрес удовлетворяет всем условиям задачи, то добавим его к ответу.
     19 
     20 [292D - Компоненты связности](/contest/292/problem/D "Чемпионат КРОК 2013 - Раунд 1")
     21 
     22 Ограничения в задаче были не слишком удачными и провоцировали писать решение за квадрат, мы постарались максимально не позволить таким решениям пройти.
     23 
     24 У этой задачи много правильных решений. Изначально планировалось решение, которое предподсчитывает частичные *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).
     25 
     26 [292E - Копирование данных](/contest/292/problem/E "Чемпионат КРОК 2013 - Раунд 1")
     27 
     28 У этой задачи много правильных решений. Изначально предполагалось решение, использующие корневую эвристику. Разобьем все запросы на *sqrt*(*m*) блоков. Будем поддерживать текущий массив *b* в виде отрезков в массиве *z*, который хранит четверки (*lf*, *rg*, *type*, *start*), где *lf*, *rg* — отрезок индексов массива *b*, *type* — 0 или 1, означающее из какого массива взяты числа для этого отрезка, *start* — позиция начала этого отрезка в массиве типа *type*.
     29 
     30 На запросы будем отвечать в тупую, то есть честно пересчитывать как изменится массив *z* от запроса копирования и отвечать на запросы значения в позициях. Однако, каждые *sqrt*(*m*) запросов будем сливать данные из массива *z* в массив *b*, для того чтобы сам массив *z* сильно не разрастался.
     31 
     32 Есть простое решение с деревом отрезков, которое умеет делать покраску на отрезке. Пусть пришел запрос копирования [*lf* ; *rg*], , тогда покрасим отрезок запроса [*lf* ; *rg*] в цвет, равный номеру запросу. Все запросы будем сохранять. Пусть пришел запрос значения в позиции *x*, тогда найдем цвет в дереве в этой позиции. Если такого цвета нет, значит мы находимся в исходном массиве *b* (выведем *b*[*x*]), иначе посчитаем смещение *dx* от начала этого запроса до нашей позиции *x* и выведем *a*[*x* + *dx*].