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

Revision ru4, by Edvard, 2016-01-11 22:30:59

616A - Сравнение длинных чисел

Замечу, что в этой задаче решения использующие стандартные типы длинной арифметики (класс BigInteger в Java, стандартные длинные числа в Pyhon) не должны проходить. Это связано с тем, что они хранят число не в десятичной системе счиления и соответственно при создании длинного числа происходит его конвертация из десятичной системы счисления, которая является тяжёлой операцией и работает обычно за O(n2), где n — длина числа.

Для решения задачи можно просто добавить лидирующих нулей к более короткому числу, а далее сравнить, получившиеся строки в лексикографическом порядке (алфавитном).

С++ solution

Python solution

Сложность: O(n).

616B - Ужин с Наташей

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

C++ solution

Сложность: O(nm).

616C - Лабиринт

Давайте сначала пронумеруем все компоненты связности, запомним для каждой её размер, а также для каждой свободной клетки запомним номер её компоненты. Это можно сделать с помощью одного обхода в глубину. Теперь ответ для непроходимой клетки будет равен единице плюс размеры всех соседних различных компонент. Соседних в смысле компонент всех соседних клеток (в общем случае четырёх).

C++ solution

Сложность: O(nm).

616D - Наидлиннейший k-хороший подотрезок

Эту задачу мы решили дать поскольку на страницах Codeforces часто видим вопрос "Что такое метод двух указателей?". Эта задача является типичным примером задачи, решаемой этим методом.

Будем искать для каждой левой границы l наибольшую границу r такую, что отрезок (l, r) k-хороший. Заметим следующее: если некоторый отрезок (l, r) k-хороший, то отрезок (l + 1, r), тоже является хорошим. Таким образом, поиск максимальной правой границы для левого конца l + 1 мы можем начинать с максимальной правой границы для левого конца l. Далее просто будем поддерживать в массиве cntx для каждого числа x количество его вхождений в текущий отрезок (l, r), а также количество различных чисел. Будем пытаться двигать правую границу пока можем, далее двигать на единицу левую границу. Итого два указателя l, r вместе передвинутся 2n раз.

C++ solution

Сложность: O(n).

616E - Сумма остатков

616F - Дорогие строки

Tags учебный раунд 5, разбор задач

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English Edvard 2016-01-12 02:30:42 15 Tiny change: ' i\right)=\frac {m(m+1)}2 - \sum\li' -
ru9 Russian Edvard 2016-01-12 02:30:03 15 Мелкая правка: ' i\right)=\frac {m(m+1)}2 - \sum\li' -
en8 English Edvard 2016-01-12 02:28:15 1258
en7 English Edvard 2016-01-12 02:03:12 1444
en6 English Edvard 2016-01-12 01:28:08 932
en5 English Edvard 2016-01-12 00:30:42 12
ru8 Russian Edvard 2016-01-12 00:30:19 24 Мелкая правка: '[problem:6' -
en4 English Edvard 2016-01-12 00:28:34 515
ru7 Russian Edvard 2016-01-12 00:16:51 1 Мелкая правка: 'че решения использую' -> 'че решения, использую'
en3 English Edvard 2016-01-11 23:50:30 4 Tiny change: 'fter that should fi' -> 'fter that you should fi'
en2 English Edvard 2016-01-11 23:49:50 265
en1 English Edvard 2016-01-11 23:47:56 727 Initial revision for English translation
ru6 Russian Edvard 2016-01-11 23:31:14 1308 Мелкая правка: 'ользовать ~map~ для хране' -int, int
ru5 Russian Edvard 2016-01-11 22:52:54 1637 Мелкая правка: 'i i\rfloor)$.\n\n[pr' -
ru4 Russian Edvard 2016-01-11 22:30:59 930
ru3 Russian Edvard 2016-01-11 22:22:53 505
ru2 Russian Edvard 2016-01-11 22:16:30 207
ru1 Russian Edvard 2016-01-11 22:14:10 856 Первая редакция (опубликовано)