NALP's blog

By NALP, 8 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.

»
15 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

  • »
    »
    5 months 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 months 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 months 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.

»
12 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

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

Can somebody help me to figure out what's wrong with my approach. In problem C solution link

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

For problem C.

One could also keep the most recent increasing index from left to right, and then the most recent increasing index from right to left.

Once given l and r, in a similar spirit as the provided solution, check if the (most recent increasing index from left to right) is smaller than the (most recent increasing index from right to left)

78337564

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

can any one help me in B. I am getting TLE in test case 9. https://codeforces.com/contest/279/submission/78465775

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

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

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

Can anybody explain 279E: Beautiful Decomposition?

»
3 months ago, # |
  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://codeforces.com/contest/279/submission/85828747

»
4 weeks 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://codeforces.com/contest/279/submission/90775068

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi. I was able to solve B using sliding window approach. However, I'm trying to learn how to solve it using prefix sum and binary search. I've implemented it here, but I'm getting TLE. This approach is O(n * log n) so it should work on the test cases for the problem. Can anyone provide any hints or tips?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C can be solved using segment tree and by making two array for keeping track of most recent increasing and most recent decreasing sequence. Note:Segment tree node must keep track of index of maximum element in that range.