NALP's blog

By NALP, 7 years ago, In Russian,

279A - Point on Spiral

Из-за небольших ограничений в данной задаче можно было просто промоделировать шаги коня. Удобнее всего это делать, храня текущее направление движения и счетчик со значением, сколько шагов в эту сторону осталось. Заметим, что конь движется по спирали по следующему шаблону: 1 шаг вперед, поворот, 1 шаг вперед, поворот, 2 шага, поворот, 2 шага, поворот, 3 шага, поворот, 3 шага, поворот, 4 шага и так далее.

279B - Books

При решении этой задачи проще всего было воспользоваться методом двух указателей: левый указатель означает начало отрезка, правый — конец. При передвижении левого указателя на единицу вправо, правый надо двигать до тех пор, пока сумма ai внутри отрезка меньше или равна t. Так мы сможем для каждого левого конца найти максимально удаленный правый, а ответ на задачу — это максимальная длина из этих отрезков.

279C - Ladder

Давайте перед выполнением запросов выпишем в массив down отдельно все позиции i, для которых ai > ai + 1, и в массив up такие позиции i, такие что ai < ai + 1.

Теперь заметим важный факт для решения: отрезок [l, r] является лесенкой тогда, когда все позиции i, где ai < ai + 1 левее всех позиций j, в которых aj > aj + 1 (l ≤ i, j < r).

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

279D - The Minimum Number of Variables

Давайте решать задачу методом динамического программирования по бинарной маске. Пусть текущее состояние — это mask. Через count(mask) обозначим количество единичных битов в маске, а через b1, b2, ..., bcount(mask) их индексы (здесь и далее будем использовать 0-нумерацию).

Наше состояние означает, что в данный момент у нас имеется count(mask) переменных, которые равны ab1, ab2, ..., abcount(mask). Будем считать, что дойдя до такого состояния, мы уже сумели произвести count(mask) операций, а значит, сейчас нам надо получить x = abcount(mask) + 1.

Если это число x не представимо в виде x = bi + bj, то тогда точно следующее значение мы получить не можем, и это состояние тупиковое, а иначе даже неважно какие именно значения i, j мы возьмем, главное — убедиться, что такие существуют.

Итак, мы получаем число x на текущей операции. Теперь важно понять, куда мы можем его записать: а именно мы либо записываем в какую-либо из уже использованных переменных (старое значение стирается), либо в новую переменную (это будет стоить нам 1).

В терминах масок первая операция выглядит как выкидывание одного из битов bk, и добавление нового бита, а вторая — просто добавление нового бита.

Начальное состояние в нашей динамике — это mask = 1, конечное — любая маска, в которой есть единичный бит на позиции n - 1 (в 0-нумерации).

При аккуратной реализации такое решение будет работать за O(2n·n). В частности, следующий хитрый прием поможет добиться этого: когда нам требуется проверить, что в маске есть такие два бита bi и bj, что acount(mask) = abi + abj, то будем использовать предподсчитанный массив diff[q][p], в котором будет записан индекс такого элемента массива a, который равен разности aqap.

Это позволит нам при проверке перебирать лишь значение bi.

279E - Beautiful Decomposition

Будет опубликовано чуть позже…

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

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

Could you please translate this editorial to english. Thanks.

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can anyone help me to get where I am going wrong in my logic ? my code I am assuming : the answer is no only if there is a dip in the given range, eg. 2 1 3 has dip at index 1, also if query is in (1,2) then the subseg has no dip.

I am getting WA. any help would be great.

Edit: those who try this way, take into considerations of case like 2 1 1 2, as this is also dip but only for range (0,3) my accepted solution

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If somebody feels trouble in problem C . My normal solution with prefix sum technique and binary search

https://github.com/joy-mollick/Sorting-and-Searching-Problems/blob/master/Codeforces-279C%20-%20Ladder.cpp