Codeforces #308 (Div. 2) Editorial

Правка ru5, от Wild_Hamster, 2015-06-19 15:37:58

552A - Ваня и таблица

В этой задаче проходило множество решений:

1) С каждым новым прямоугольником добавляется его площадь к результату, так что будем считать площадь каждого прямоугольника и прибавлять к ответу, т.е. для каждой строки x1, y1, x2, y2 прибавляем к ответу (x2 - x1 + 1) * (y2 - y1 + 1)

Асимптотика данного решения по времени O(n).

2) Просто сделаем все, что описано в условии, создадим массив и с каждым запросом будем прибавлять прямоугольник к массиву, после чего просто сложим все элементы массива.

Асимптотика по времени O(n * x * y)

C++ code Wild_Hamster

Java code Wild_Hamster

Python code Zlobober

552B - Ваня и книги

Можно вывести формулу результата:

для n < 10 ответом будет n = n - 1 + 1 = 1 * (n + 1) - 1;

для n < 100 ответом будет 2 * (n - 9) + 9 = 2 * n - 9 = 2 * n - 10 - 1 + 2 = 2 * (n + 1) - 11;

для n < 1000 ответом будет 3 * (n - 99) + 2 * (99 - 9) + 9 = 3 * n - 99 - 9 = 3 * n - 100 - 10 - 1 + 3 = 3 * (n + 1) - 111;

для n < 10sz ответом будет ;

Асимптотика по времени O(sz), где sz — длина числа.

Так же можно было просто перебрать всех возможных 10 вариантов n < 10, n < 100, ..., n < 109, n = 109 и подсчитывать для каждого результат.

C++ code Wild_Hamster

Java code Wild_Hamster

Python code Zlobober

UPD: Don't use function pow() to find powers of 10, because it doesn't work right sometimes.

552C - Ваня и весы

Переведем число m в w-ичную систему счисления. Если все разряды числа – 0 или 1, то нашу вещь можно взвесить, поставив гири, номера разрядов которых равны 1, на одну чашу весов, а нашу вещь на другую.

Если же это условие не выполняется, то пройдемся от младшего разряда к старшему и если он не равен 0 или 1, пытаемся отнять от него w и прибавить к старшему разряду единицу. Если этот разряд становится равен  - 1, то ставим гирю под данным номером на одну чашу с нашей вещью, если 0 — то не ставим гирю никуда, если иначе – то вещь нельзя взвесить по заданным условиям и ответ .

Асимптотика по времени O(logm).

C++ code Wild_Hamster

Java code Wild_Hamster

Java code Zlobober

552D - Ваня и треугольники

Переберем все возможные пары точек, проведем через каждую из пар прямую и запишем, что этой прямой принадлежат эти 2 точки с помощью map. Если на прямой находится x точек, то на самом деле мы посчитаем нашим перебором, что на ней 2 * x * (x - 1) точек. Таким образом можно завести массив типа b[2 * x * (x - 1)] = x, чтобы определять, сколько точек находится на прямой. Тогда если на прямой находится x точек, то мы теряем x * (x - 1) * (x - 2) / 6 возможных треугольников с возможных n * (n - 1) * (n - 2) / 6 треугольников. Таким образом, для каждой прямой, на которой находится x точек, мы будем отнимать от n * (n - 1) * (n - 2) / 6 значение x * (x - 1) * (x - 2) / 6, таким образом подсчитывая ответ.

Асимптотика решения O(n2 * logn).

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

UPD: I am sorry, that O(n3 / 6) solutions passed, my solution with O(n3 / 6) didn't pass before the contest, so I decided, that TL 4 sec is good(it was for Java TL).

C++11 code Wild_Hamster

Java code Wild_Hamster

Java code Zlobober

552E - Ваня и скобки

Можно увидеть, что максимальный ответ будет тогда, когда скобки будут находится между двумя знаками  * , или между знаком  *  и концом выражения. Для удобства прибавим в начало выражения 1 * , а в конец выражения  * 1.

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

Чтобы подсчитать выражение, используем две переменные x и y, в начале x = 0, y = firstnumber, где firstnumber — первая цифра выражения, тогда если следующий знак  + , тогда x = y, y = nextnumber, а если  * , тогда x = x, y = y * nextnumber. Результатом выражения будет x + y, для подсчета выражений в скобках и вне скобок можно написать функцию.

Асимптотика по времени O(|s| * 172).

C++ code Wild_Hamster

Java code Wild_Hamster

Java code Zlobober

Теги 308, round, div2, editorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский Wild_Hamster 2015-06-24 11:27:28 1 Tiny change: '1,x_2,y_2$we will ad' -
en6 Английский Wild_Hamster 2015-06-24 11:26:19 91
en5 Английский Wild_Hamster 2015-06-19 15:48:15 1063
ru5 Русский Wild_Hamster 2015-06-19 15:37:58 1061
en4 Английский Wild_Hamster 2015-06-18 22:25:40 169
en3 Английский Wild_Hamster 2015-06-18 22:25:00 104
ru4 Русский Wild_Hamster 2015-06-18 22:24:15 277
ru3 Русский Wild_Hamster 2015-06-18 21:34:25 87
en2 Английский Wild_Hamster 2015-06-18 21:33:53 87 (published)
ru2 Русский Wild_Hamster 2015-06-18 21:31:36 87
en1 Английский Wild_Hamster 2015-06-18 21:30:19 3422 Initial revision for English translation
ru1 Русский Wild_Hamster 2015-06-18 21:25:34 3645 Первая редакция (сохранено в черновиках)