NALP's blog

By NALP, 12 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

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please translate this editorial to english. Thanks.

»
5 years 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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Hey, I know it's too late to make a difference for you but if you found a solution to this problem you encountered, could you please help me out to find the glitch in this algorithm because I am facing same issue as yours. Thanks in advance! :)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Hey ! It has been 9 months, and I have completely forgot what this piece of code does. But I am sure the edit part in my comment, it solved my problem with the wa code.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Thanks man.. could you share your solution link please. I haven't found error in mine's yet.

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

https://mirror.codeforces.com/contest/279/submission/79049303 check this solution, using dp and no binary search

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

Can anybody explain 279E: Beautiful Decomposition?

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

I rather made a different states for dp in Problem C.

Let's call the value in ladder sequence such that  a[i]>=a[i+1] && a[i]>=a[i-1] as pivot. So for a index there are three possibility either before the pivot, pivot itself or after the pivot. We can use dp[3][n] representing all the three possibility respectively for all index where dp[j][i] stores the value of leftmost index of the ladder when ith index is having jth possibility. We than just have to check min(dp[0][r],min(dp[1][r], dp[2][r]))<=l for answer.

Link for solution — https://mirror.codeforces.com/contest/279/submission/85828747

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

I know it is late :/ .Can someone explain what is the mistake in my code for problem C? Here is the link to my submission. https://mirror.codeforces.com/contest/279/submission/90775068

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

101232184 simple solution for C, just about finding peaks

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

can somebody plz translate problemB explanation to english

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

    279B — Books — When solving this problem, it was easiest to use the method of two pointers: the left pointer means the beginning of the segment, the right one — the end. When moving the left pointer one unit to the right, the right one must be moved until the sum a i inside the segment is less than or equal to t . This way we can find for each left end the most distant right end, and the answer to the problem is the maximum length of these segments.