H - Ограбления

Подсказка 1: Попробуйте решить задачу без запросов за линию. Примените похожее решение к исходной задаче

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

Подсказка 2: Посчитайте динамику в вершинах дерева отрезков.

October 3, 2018
by Максим Деб Натх
0
11

G - Откат

Всё чуть сложнее, чем реализовать персистентное ДО.

Пусть T_i - это массив, где a_j = 1 <=> на суффиксе i...n-1 в изначальном массиве число на j - й позиции встретилось впервые.

То есть для массива 1 2 1 3 1 2 1:

T_0 = [1, 1, 0, 1, 0, 0, 0]
T_1 = [0, 1, 1, 1, 0, 0, 0]
T_2 = [0, 0, 1, 1, 0, 1, 0]
T_3 = [0, 0, 0, 1, 1, 1, 0]
T_4 = [0, 0, 0, 0, 1, 1, 0]
T_5 = [0, 0, 0, 0, 0, 1, 1]
T_6 = [0, 0, 0, 0, 0, 0, 1]

Далее надо сделать бинпоиск.

October 3, 2018
by Максим Деб Натх
0
13

F - Крыса - роботяга

Попробуйте оценить максимальную глубину вложенности рамок в друг друга

|

|

|

|

|

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

||

|

Это же примерно log_2(10^18)!

October 3, 2018
by Максим Деб Натх
0
11

E - Ложь, наглая ложь и статистика

Подсказака 1: попробуйте написать решение за полином, затем погенерировать тесты и внимательно всмотреться в то, что выдаёт ваша программа.

(ниже ещё одна подсказка)

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|

|


Подсказка 2: попробуйте показать, что минимальное среднее будет достигаться на отрезках длины 2 или 3

October 3, 2018
by Максим Деб Натх
0
23
Show more