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

№	Пользователь	Рейтинг
1	ecnerwala	3650
2	Benq	3582
3	Geothermal	3570
3	orzdevinwang	3570
5	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3532
8	Radewoosh	3522
9	Um_nik	3483
10	jiangly	3468

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

279A - Point on Spiral

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

279B - Books

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

279C - Ladder

Давайте перед выполнением запросов выпишем в массив 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 - The Minimum Number of Variables

Давайте решать задачу методом динамического программирования по бинарной маске. Пусть текущее состояние — это 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 - Beautiful Decomposition

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

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

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

jk_qq

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

-12

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

→ Ответить

NALP

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

← 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

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

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__

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

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

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

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

scameeer

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

← Rev. 4 →

UPD:got it!

utsavparakhiya

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

Please help me i am getting wrong answer

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

kstheking

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

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.

Блог пользователя NALP

279A - Point on Spiral

279B - Books

279C - Ladder

279D - The Minimum Number of Variables

279E - Beautiful Decomposition