Codeforces Round #171 (Div. 2) Разбор Задач

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

279A - Точка на спирали

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

279B - Книги

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

279C - Лесенка

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

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

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

279D - Минимальное количество переменных

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

Наше состояние означает, что в данный момент у нас имеется count(mask) переменных, которые равны a_b₁, a_b₂, ..., a_{b_count(mask)}. Будем считать, что дойдя до такого состояния, мы уже сумели произвести count(mask) операций, а значит, сейчас нам надо получить x = a_{b_count(mask) + 1}.

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

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

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

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

При аккуратной реализации такое решение будет работать за O(2ⁿ·n). В частности, следующий хитрый прием поможет добиться этого: когда нам требуется проверить, что в маске есть такие два бита b_i и b_j, что a_count(mask) = a_{b_i} + a_{b_j}, то будем использовать предподсчитанный массив diff[q][p], в котором будет записан индекс такого элемента массива a, который равен разности a_q–a_p.

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

279E - Красивая декомпозиция

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

Комментарии (38)

Показать архивные | Написать комментарий?

jk_qq

12 лет назад, # |

-12

Можно подробнее B?

→ Ответить

NALP

12 лет назад, # ^ |

← Rev. 2 →

+10

проще показать сам код решения:

int ans = 0, r = 0, sum = 0;
forn(l, n) {
    while (r < n && sum + a[r] <= t) {
       sum += a[r];
       r++;
    }

    ans = max(ans, r - l);
    sum -= a[l];     
}

cout << ans << endl;

спасибо)

Aeon

← Rev. 5 →

На B и C динамика простая. Одномерная

Ximera

B можно и бинпоиском решить :)

_dangerous_

ну очень понятно вот тут

Будем считать, что дойдя до такого состояния, мы уже сумели произвести count(mask) операций, а значит, сейчас нам надо получить x = acount(mask).

так все-таки, count(mask) — это количесто переменных или количество действий, которые мы произвели? ведь при присваивании мы можем какие-то биты удалить, и уже не будет count(mask) равно количеству действий, скорее уж количеству переменных, или я что-то не понял?

Да, я немного ошибся.. Конечно же, у нас в маске каждый раз максимальный индекс единичного бита увеличивается ровно на единицу. Поэтому надо найти номер максимального единичного бита в маске, прибавить 1 и вот такое по счету число из массива a собирать.

-9

опубликовали разбор? давайте его заминусуем! забавно.

MIG29

В задаче "С" я обошелся без бинарного поиска. Идея была такова: 2 вспомогательных массива ll и lr. ll — для каждого i будем хранить самую правую позицию где заканчивается возрастающая часть лесенки из i. К примеру для массива a[] = {1, 2, 3, 1, 2}, ll = {2, 2, 2, 4, 4}. В lr тоже самое только наоборот — самая левая позиция убывающей части лесенки из i. В итоге ответом будет 'Yes', если ll[l] >= lr[r]. Сложность O(n + m)

Nodir.Daminov

В твоем примере в массиве а[] у тебя индексы начинаются с 0 или 1?

С нуля

Спасибо!!!

gohard

← Rev. 8 →

+13

Да, в С можно легко обойтись без логарифма. У меня решение чуть-чуть отличается от предложенных выше, хотя принцип тот же. Может, кому-нибудь мое будет понятнее :)

В up[i] храним начало подъема, на котором лежит i-ый элемент массива. В down[i] храним начало спуска, на котором лежит i-ый элемент массива. Понятно, как пересчитывать эти значения:

a[i] >= a[i — 1] -> up[i] = up[i — 1], иначе up[i] = i

a[i] <= a[i — 1] -> down[i] = down[i — 1], иначе down[i] = i

Получив запрос, мы можем посмотреть на следующее равенство: up[down[r]] = up[l]

То есть, если на отрезке есть "перелом", то он будет началом спуска для элемента r. Также начало подъема для "переломного" элемента должно быть таким же, как и для элемента l.

Осталось не забыть про случай, когда в запросе мы получили невозрастающую подпоследовательность, по условию она также будет являться "лесенкой". Этот случай обрабатывается равенством down[l] = down[r]

Случай с неубывающей подпоследовательностью автоматически обработается первым равенством.

Lord_F

Помогите найти ошибку в решении задачи C:

Пусть t[i] — количество "долин" на отрезке от 1 до i, т.е. кол-во таких i, что a[i]<a[i-1] и a[i]<a[i+1]. Тогда отрезок будет лесенкой, только если на отрезке [l+1; r-1] не будет "долин", т.е. t[r-1]-t[l]==0. Отдельно разбираем случаи l==r и l==r-1, но понятно, то тогда отрезок точно будет лесенкой.

Вердикт WA №19. На over10000-ной строчке выводит Yes вместо No. Во-первых понятно, что "долины" могут быть только на концах лесенки, а если они есть на отрезке [l+1; r-1], то отрезок точно не лесенка. (Или нет?!) Во-всяком случае, придумать пример, чтобы отрезок не был лесенкой, а мой вариант выводил, что он таковым является, я не смог.

pavel.savchenkov

4 1
3 2 2 3
1 4

Ответ: No

Когда появится разбор задачи 279E - Красивая декомпозиция???

Astekinane

Разбор в 0-индексации

Идея 1:

Нам не важно, приводить данное число к нулю или приводить ноль к данному числу сложениями/вычитаниями чисел вида 2^k;
Рассмотрим двоичную запись числа от старших битов к младшим (ровно как в условии) тогда операция "прибавить 2^k" — это операция "занулить все единички слева до первого встречного нуля, а первый встречный ноль превратить в единичку", а операция "отнять 2^k" — это "заеденичить все нули слева до первой встречной единички, а первую встречную единичку превратить в ноль"
Информацию "первая единичка слева от бита (i)" и "первый нолик слева от бита (i)" можно прекалкнуть.
Пусть dpNull[i] — это количество прибавлений/вычитаний чисел вида 2^k которые нужны, чтобы занулить, число вида s[0..i-2]+"0" (простым языком — префикс длины i числа из условия, но на последнем месте этого префикса стоит 0), dpOne[i] — аналогичное, но на последнем месте стоит 1, и real(i) которая равна dpNull[i] еcли s[i]=='0' и dpOne[i] если s[i]=='1'

С iым битом мы можем сделать три операции — оставить его в покое, прибавить ему 2^i и отнять от него 2^i, из всех этих вариантов нам нужно выбрать наилучший, собственно, пересчёт следующий:

dpOne[i]=min(dpOne[Первый_ноль_слева(i)]+1,real(i-1)+1 ); Первый вариант — прибавить 2^i, второй — отнять, почему это так понятно из пункта 2, оставлять в покое смысла нету, так как тогда iый бит никогда не занулится.

dpNull[i]=min(dpNull[Первая_единица_слева(i)]+1,real(i-1) ); Первый вариант — отнять 2^i, второй — оставить в покое, прибавлять смысла нету по тем же причинам.

Ответ : real(s.size()-1);

Так решал, например, я: 3253261

Идея 2:

Будем решать в числах n — число из задачи, k — степень двойки такая, что k/2<n<=k, то ответ на задачу, это 1 + ответ для min(k-n,n-k/2) вторая часть формулы — это просто вычитание старшего единичного бита, первая часть формулы — это, фактически, инверсия всех битов, которые не старше самой старшей единички. Фактически, мы просто работаем с самым старшим единичным блоком и решаем, как его выгодно занулить: инвертировав его в нули или вручную поотнимав. Работать можно, естественно, только со строками, и инверсию выполнять неявно (запомниать, сейчас инвертирована строка или нет).

Так решал, например, Zip753: 3247041

Вот еще довольно простое решение, как я понял жадностью.

Скоро... :)

rob.kh

← Rev. 3 →

Подобная задача была на Codeforces Beta Round #96. Div1 D "Константы на языке Шекспира". Разбор

Можете пока прочитать тот разбор. Хотя там утверждается, что жадина не прокатит, я тем не менее сдал другой жадный алгоритм(3249333), и оно прошло все тесты.

Извиняемся за беспокойство, но как скоро будет "Оффициальный" разбор 279E - Красивая декомпозиция?

I_Love_Equinox

9 лет назад, # |

Could you please translate this editorial to english. Thanks.

harshraj22

5 лет назад, # |

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

Enrique__

5 лет назад, # ^ |

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! :)

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.

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

Its already in my first comment ?

Oops. thanks buddy!!

KloudIzNoGoud

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

scameeer

4 года назад, # |

Can anybody explain 279E: Beautiful Decomposition?

vedang122

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.net/contest/279/submission/85828747

y0g38h_kum4r

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.net/contest/279/submission/90775068

4 года назад, # ^ |

← Rev. 4 →

UPD:got it!

utsavparakhiya

Please help me i am getting wrong answer

Solution link : https://codeforces.net/contest/279/submission/97835951

kstheking

101232184 simple solution for C, just about finding peaks

Pulkit_07

4 1 4 3 3 5 1 4 try for this

AdityaG

can somebody plz translate problemB explanation to english

sid_rasa

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.