Разбор задач Educational Codeforces Round 2

Правка ru1, от Edvard, 2015-11-27 19:05:18

586A - Alena's Schedule

Эта задача является чисто технической. Нужно было сделать ровно то, что написано в условии.

586B - Laurenty and Shop

Давайте отсортируем числа первого массива. Теперь будем идти по второму массиву и для текущего числа bj найдем бинарным поиском индекс первого большего числа в первом массива. Этот индекс и будет являться ответом.

Другим подходом в этой задаче было следующее: отсортируем оба массива сохранив при этом индексы чисел (например можно сортировать пары <значение, позиция>). Теперь будем идти по второму массиву и хранить переменную p — указатель на первый элемент ap такой, что он больше текущего bj. Поскольку оба массива отсортированы указатель можно не сбрасывать на каждой итерации, а просто двигать его дальше вправо.

Асимптотическая сложность решения: O(nlogn).

585A - Gennady the Dentist

Давайте посчитаем для каждого символа c сколько раз он встречается в s. Обозначим эту величину cntc. Рассмотрим нечетные cntc. В палиндроме нечетных cntc может быть не больше одного. Пусть a1, a2...ak — это символы с нечетным cntc в алфавитном порядке. Заменим любой символ ak символом a1, символ ak - 1 символом a2 и так далее пока не дойдем середины. Теперь у нас имеется имеется не более одного нечетного символа. Если нечетный символ есть поставим его в середину ответа. А в первую половину возьмем от всех букв cntc / 2 в алфавитном порядке. Например, если s = aabcd мы сначала заменим d на b, после этого поставим символ c в середину и после перестановки остальных символов получим строку abcba.

Асимптотическая сложность решения: O(n).

585B - Phillip and Trains

585C - Alice, Bob, Oranges and Apples

585D - Lizard Era: Beginning

585E - Present for Vitalik the Philatelist

585F - Digits of Number Pi

Асимптотическая сложность решения: O(nd2).

Теги educational round 2, editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Edvard 2015-12-20 01:06:01 7190 Reverted to en5
en6 Английский Edvard 2015-12-20 01:04:40 7190 Tiny change: 'oks of $i$th genre. ' -
ru12 Русский Edvard 2015-11-28 02:56:22 58
en5 Английский Edvard 2015-11-28 02:55:31 1179
en4 Английский Edvard 2015-11-28 01:56:48 12 Tiny change: 'l to large``. There is' -> 'l to large''. There is'
en3 Английский Edvard 2015-11-28 01:56:19 14 Tiny change: 'l to large``. There is' -> 'l to large''. There is'
en2 Английский Edvard 2015-11-28 01:33:31 1343
en1 Английский Edvard 2015-11-28 00:38:09 2786 Initial revision for English translation
ru11 Русский Edvard 2015-11-27 23:53:58 9
ru10 Русский Edvard 2015-11-27 23:50:23 9 Мелкая правка: 'чение $d$ —- наибольш' -> 'чение $d$ --- наибольш'
ru9 Русский Edvard 2015-11-27 23:29:29 1188
ru8 Русский Edvard 2015-11-27 20:04:30 63
ru7 Русский Edvard 2015-11-27 20:03:57 104 (опубликовано)
ru6 Русский Edvard 2015-11-27 19:54:54 51
ru5 Русский Edvard 2015-11-27 19:53:17 24
ru4 Русский Edvard 2015-11-27 19:52:37 197 Мелкая правка: ' to large`). Давайт' -
ru3 Русский Edvard 2015-11-27 19:48:36 1406
ru2 Русский Edvard 2015-11-27 19:25:41 1280
ru1 Русский Edvard 2015-11-27 19:05:18 1827 Первая редакция (сохранено в черновиках)