Codeforces Round #350 (Div.2) Editorial

Revision en5, by fcspartakm, 2016-05-05 17:56:59

670A - Выходные

There are many ways to solve this problem. Let's talk about one of them. At first we need to write a function, which takes the start day of the year and calculate the number of days off in such year. To make it let's iterate on the days of the year and will check every day — is it day off or no. It is easy to show that if the first day of the year equals to the first day of the week (i.e. this day is Monday) in this year will be minimum possible number of the days off. If the first day of the year equals to the first day off of the week (i.e. this day is Saturday) in this year will be maximum possible number of the days off.

670B - Игра роботов

To solve this problem we need to brute how many identifiers will called robots in the order from left to right. Let's solve this problem in one indexing. Let the current robot will call i identifiers. If k - i > 0 let's make k = k - i and go to the next robot. Else we need to print a[k], where a is the array with robots identifiers and end our algorithm.

670C - Поход в кино

We need to use map-ом (let's call it cnt) and calculate how many scientists knows every language (i. e. cnt[i] equals to the number of scientists who know the language number i). Let's use the pair res, where we will store the number of \textit{very pleased} scientists and the number of \textit{almost satisfied} scientists. At first let res = make_pair(0, 0). Now we need to iterate through all movies beginning from the first. Let the current movie has the number i. Then if res < make_pair(cnt[b[i]], cnt[a[i]]) let's make res = make_pair(cnt[b[i]], cnt[c[i]]) and update the answer with the number of current movie.

670D1 - Волшебный порошок - 1

This problem with small constraints can be solved in the following way. Let's bake cookies one by one until it is possible. For every new cookie let's calculate val — how many grams of the magic powder we need to bake it. For this let's brute all ingredients and for the ingredient number i if a[i] ≤ b[i] let's make b[i] = b[i] - a[i], else let's make b[i] = 0 and val = val + a[i] - b[i]. When we bruted all ingredients if val > k than we can't bake more cookies. Else let's make k = k - val and go to bake new cookie.

670D2 - Волшебный порошок - 2

Будем делать бинарный поиск по ответу. Пусть мы проверяем текущий ответ cur. Тогда целевая функция должна выглядеть следующим образом. Насчитаем в переменную cnt сколько грамм волшебного порошка нам нужно для приготовления cur печенек. Переберём все ингредиенты по очереди. Пусть текущий ингредиент имеет номер i. Тогда если a[icur > b[i] выполним присвоение cnt = cnt + a[icur - b[i]. Если после рассмотрения какого-то ингредиента cnt стало больше чем k, целевая функция должна вернуть false. Если такого не произошло ни после какого ингредиента, целевая функция должна вернуть true.

Понятно, что если целевая функция вернула true нужно сдвинуть левую границу бинпоиска в cur, иначе нужно сдвинуть правую правую границу.

670E - Редактор правильных скобочных последовательностей

Будем решать данную задачу следующим образом. Сначала с помощью stack насчитаем массив pos, где pos[i] будет означать позицию скобки, парной для скобки в позиции i. Затем заведём два массива left и right. Тогда left[i] будет равно позиции ближайшей слева относительно позиции i неудалённой скобки, а right[i] будет равно позиции ближайшей справа относительно позиции i неудалённой скобки. Если таковых скобок нет, будет хранить в соответствующей позиции в массиве число \texttt{-1}.

Пусть текущая позиция курсора равна p. Тогда при операции \texttt{L} выполним присвоение p = left[p], а при операции \texttt{R} выполним присвоение p = right[p]. Осталось научиться обрабатывать операцию \texttt{D}.

Пусть lf равно p, а rg равно pos[p]. Если lf > rg сделаем swap(lf, rg). То есть теперь мы знаем границы подстроки, которую нужно удалить. Пересчитаем сначала позицию p. Если right[rg] =  =  - 1 (то есть после удаления текущей подстроки не останется скобок справа), нужно сдвинуть p влево, то есть выполнить присвоение p = left[lf], иначе нужно выполнить присвоение p = right[rg]. Осталось только пересчитать ссылки для концов удаляемой подстроки. Здесь нужно быть аккуратным, и проверять есть ли скобки слева и справа относительно концов удаляемой подстроки.

Для вывода ответа нужно определить номер первой слева неудалённой скобки, с помощью массива right пройти по всем неудалённым скобкам и вывести их в ответ. Для определения номера первой неудалённой скобки можно сложить все пары концов удаляемых подстрок в массив, затем отсортировать его и, проитерировавшись по полученному массиву, определить искомую позицию. Бонус: как определить позицию первой неудалённой скобки за линейное время?

670F - Восстанови число

Сначала нужно найти длину изначального числа. Для этого просто переберем её. Пусть текущая длина равна len. Тогда если len равно длине заданной строки минус количество цифр в числе len, то len это и есть длина изначального числа (то есть она определяется однозначно). Затем нужно убрать из заданной строки все цифры, которые есть в числе len, сгенерировать три строки из оставшихся цифр и выбрать из них лексикографически минимальную — это и будет ответом. Пусть t — это подстрока, которую запомнил Вася. Какие же три строки нужно сгенерировать?

  1. Записать сначала строку t, а затем все оставшиеся цифры из заданной строки в возрастающем порядке. Эта строка может быть составлена, только если t не начинается с нуля.

  2. Записать сначала наименьшую цифру из оставшихся в заданной строке отличную от нуля в начало. Если таковой нет, то такую строку составить мы не сможем. В противном случае, нужно записать все оставшиеся цифры, меньшие первой цифры в строке t в возрастающем порядке, затем дописать строку t и затем все оставшиеся цифры в возрастающем порядке.

  3. Записать сначала наименьшую цифру из оставшихся в заданной строке отличную от нуля в начало. Если таковой нет, то такую строку составить мы не сможем. В противном случае, нужно записать все оставшиеся цифры, меньшие или равные первой цифре в строке t в возрастающем порядке, затем дописать строку t и затем все оставшиеся цифры в возрастающем порядке.

Также нужно отдельно рассмотреть случай, когда число которое передавал Вася равно нулю.

Tags div2, 350, round, editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru14 Russian fcspartakm 2016-05-05 21:35:00 0 (опубликовано)
ru13 Russian fcspartakm 2016-05-05 21:31:11 2
en9 English fcspartakm 2016-05-05 18:51:14 2620
en8 English fcspartakm 2016-05-05 18:27:42 2234
en7 English fcspartakm 2016-05-05 18:07:04 334
ru12 Russian fcspartakm 2016-05-05 18:02:23 7 Мелкая правка: 'ть правую правую гр' -> 'ть правую гр'
en6 English fcspartakm 2016-05-05 18:02:09 1123
en5 English fcspartakm 2016-05-05 17:56:59 813
en4 English fcspartakm 2016-05-05 17:50:53 783
en3 English fcspartakm 2016-05-05 17:44:46 584
en2 English fcspartakm 2016-05-05 17:38:10 1000
en1 English fcspartakm 2016-05-05 17:32:35 6507 Initial revision for English translation
ru11 Russian fcspartakm 2016-05-05 17:13:38 1749
ru10 Russian fcspartakm 2016-05-05 15:46:58 1564
ru9 Russian fcspartakm 2016-05-05 15:09:44 2 Мелкая правка: ']$, где $a[]$ &mdash; ' -> ']$, где $a$ &mdash; '
ru8 Russian fcspartakm 2016-05-05 15:04:18 1 Мелкая правка: 'ше чем $k$ целевая ф' -> 'ше чем $k$, целевая ф'
ru7 Russian fcspartakm 2016-05-05 15:03:54 3
ru6 Russian fcspartakm 2016-05-05 15:03:36 766
ru5 Russian fcspartakm 2016-05-05 14:44:25 651
ru4 Russian fcspartakm 2016-05-05 14:23:34 631
ru3 Russian fcspartakm 2016-05-05 14:10:53 382
ru2 Russian fcspartakm 2016-05-05 14:04:26 569
ru1 Russian fcspartakm 2016-05-05 13:53:08 191 Первая редакция (сохранено в черновиках)