Задача B с муниципа:

Пусть мы зафиксировали ширину d

Потратим плиток <= t

f(d) <= t

d <= ...

d <= min((n - 1) / 2, (m - 1) / 2)

m * n - (n - 2d) * (m - 2d) <= t

m * n - n * m + 2d * n + 2d * m - 4d^2 <= t

4 d^2 - 2d(n + m) + t >= 0

4d^2 - ad + b >= 0

-inf <= d <= d1, d2 <= d <= inf 

0 <= d <= c



m = 7, n = 6
t = 38

Фиксируем ширину d 
Потратим в таком случае 

m * n  - (n - 2d) * (m - 2d) плитки = 42 - (7 - 2d) * (6 - 2d) = 
42 - 42 + 12d + 14d - 4d^2 = -4d^2 + 26d

-4d^2 + 26d <= 38

-2d^2 + 13d <= 19

2d^2 - 13d + 19 >= 0

D = 169 - 4 * 2 * 19 = 169 - 152 = 17 

(13 + sqrt(17)) / 4 = 2.44
(13 - sqrt(17)) / 4 = 2.21

-inf <= d <= 2.41, 2.44 <= d <= inf 

0 <= d <= 2




Задача C с Div3:


1) Пусть map < pair < int, int >, int > m

m[{x, y}] = i - последний индекс 

Идея популярная - хотим найти подотрезок с каким-то свойством, обычно это максимум/минимум 

Баян пример - найти подотрезок с максимальной суммой 


int ans = 0; - макс.ответ 

int min = 0;

for (r = 0; r < n; r++){
	p[r] = сумма a0 + ... + ar 
	ans = max(ans, p[r] - min);
	min = min(p[r], min); 
}

Еще пример - найти подотрезок с суммой х 

map < int, int > m;

m[sum] = i - это индекс, префиксной суммы sum, a0 + ... + ai = sum 

for (r = 0; r < n; r++){
	p[r] - префиксная сумма до r 
	int need = p[r] - x 
	if (m.find(need) != m.end()){
		
	}
	m[p[r]] = i;
}

Либо:

set < int > s;

if (s.find(need) != s.end())

set, map - C++  все операции за log

Либо есть вариант unordered_set, unordered_map - работают за О(1) в среднем
Но проблема - unordered_map / set от пар не работает 
Можно сделать unordered_set < int > 

Но нельзя сделать unordered_set<pair<int, int>>, т.к. нет встроенного хешера для пар

set<int> s

Можно найти за лог наименьший элемент >= x 

s.lowerbound(x)



Задача B, Div2:



Давай за nm переберем все вершины елок(все клетки матрицы)

Идем вниз, считаем количество елок с такой вершиной 





Бинарный поиск:

1) Найти корень монотонной функции 

eps = 1e-8;

while ((l - r) > eps){
	int m = (l + r) / 2;
	if (f(m) > 0){
		r = m;
	}
	else{
		l = m;
	}
}

2)

Найти число в массиве 

a[n] : a[0] <= a[1] <= ... <= a[n - 1]

Хотим найти вхождение x

a[n] = [2, 3, 3, 4, 5, 5] - хотим найти 1 


int l = -1, r = n

a = [l, m], [m, r]

while (l < r - 1){
	int m = (l + r) / 2;
	if (a[m] <= x){ - ищет самое правое вхождение х 
		l = m;
	}
	else{
		r = m;
	}
}

while (l < r - 1){
	int m = (l + r) / 2;
	if (a[m] < x){ - ищет самое левое вхождение х 
		l = m;
	}
	else{
		r = m;
	}
}



Чтобы понять, встречается ли элемент, сравнивем с a[l] 
        0, 1, 2, 3, 4, 5
a[n] = [2, 3, 3, 3, 4, 5] - ищем 3


Бинпоиск по ответу:

Мы умеем искать в остортированном массиве элемент, умеем работать с монотонными функциями


У нас есть функция f(x)

Всегда это "булева" функция, которая принимает значения только 0/1 

Классический пример - нас просят найти минимальное время, за которое мы можем что-то сделать

Уже можно спросить - f(x) = 0/1 - можем сделать что-то за время x или нет 

На примере вырубки леса - x - количество дней 

Единственное, что нужно доказать: если можно что-то сделать за х дней(вырубить лес), то можно сделать 
и за х + 1

f(x) = 0, 0, .., 1, ..., 1, ...

У нас есть время t - количество дней 

(t - t / k) * a + (t - t / k) * b

Волшебный корабль:



Можно ли попасть из (x1, y1) -> (x2, y2) за t дней? 


(dx, dy) - сдвиг за полный цикл

t / n = k делаем циклов 

(x1 +  k * dx, y1 + k * dy)

Сдвинемся еще за t % n Дней еще куда то 
(resx, resy) 

abs(resx - x2) + abs(resy - y2) <= t