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

Правка ru3, от Edvard, 2016-01-11 22:22:53

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

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 Первая редакция (опубликовано)