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

Правка ru4, от Edvard, 2016-01-11 22:30:59

616A - Comparing Two Long Integers

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

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

С++ solution

Python solution

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

616B - Dinner with Emma

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

C++ solution

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

616C - The Labyrinth

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

C++ solution

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

616D - Longest k-Good Segment

Эту задачу мы решили дать поскольку на страницах 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 - Sum of Remainders

616F - Expensive Strings

Теги учебный раунд 5, разбор задач

История

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