хороший вопрос. а точно во всех букварях так?

Вроде да

А какая разница-то?

интересно. может в этом какой то смысл скрытый

оффтоп

Есть ли хороший учебник по алгоритмам, который содержит как задачи по темам, так и ответы к ним? А то не понятно, как проверять себя

А чем сборники задач по типу хакерранка не устраивают?

Соратники!
Помогите разобраться с решением задачи из Яндекс Блиц 12.

https://m.habr.com/ru/company/yandex/blog/340784/

Задача называется «Красно-черные деревья»

Не понимаю приведенный вариант решения.
Ниже приведу цитаты из решения, которые непонятны:

1)
...
Корнем у него может быть любое число i от 1 до N. Тогда в левом поддереве будет содержаться i-1 вершина, а в правом — j=N-i вершин.
...
- здесь непонятно как у красно-черного дерева вершиной может быть любое число i от 1 до N БЕЗ НАРУШЕНИЯ СВОЙСТВ КЧ-ДЕРЕВЬЕВ
Например, если N=5, а i=1, то по приведённой выше логике в левом поддереве будет i-1=0 вершин, а в правом j=5-1=4. Но в кч дереве согласно 2-му свойству
(Каждая вершина либо имеет два потомка, либо является листом (не имеет потомков)
а согласно 5-му свойству
(Количество черных вершин на пути от корня до любого листа дерева одинаково)

Если в левом поддереве 0 узлов,  то каким образом в правом поддереве с 4-мя узлами может соблюдаться черная высота равной в левом? Это возможно только если в правом поддереве все вершины красные, но тогда нарушается 4-е свойство кч-деревьев (У красных вершин оба потомка имеют черный цвет)

2)
...
Поскольку нам нужно вычислить количество деревьев с точностью до изоморфизма, достаточно посчитать ответ для i-1 <= j. Если i-1 < j, то прибавим к ответу CountBlack[N][H] произведение числа поддеревьев слева и справа: CountLeft*CountRight. Если же мы строим оба поддерева из одинакового числа элементов (i-1=j), то к результату нужно прибавить CountLeft*(CountLeft+1)/2 вариантов.
...
- откуда могут быть получены такие выводы? Самое главное почему для случае равенства нужно прибавлять CountLeft*(CountLeft+1)/2  ?

3)
...
Следовательно, достаточно рассмотреть черные высоты, не превосходящие H = 2*log(N)*20
...
Откуда взялось 20? В кч-дереве верхнее ограничение черной высоты H = 2*log(N + 1)
https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE#.D0.94.D0.BE.D0.BA.D0.B0.D0.B7.D0.B0.D1.82.D0.B5.D0.BB.D1.8C.D1.81.D1.82.D0.B2.D0.BE_.D0.B0.D1.81.D0.B8.D0.BC.D0.BF.D1.82.D0.BE.D1.82.D0.B8.D1.87.D0.B5.D1.81.D0.BA.D0.B8.D1.85_.D0.B3.D1.80.D0.B0.D0.BD.D0.B8.D1.86

Подскажите, есть функция, которая выдает возрастающие значения. у нее один параметр - день. мне нужно найти когда эта функция выдаст значение больше, чем X . Штука в том, что я бы применил бинарный поиск, но верхняя граница неизвестна. т.е я не могу сказать, что искать нужно в интервале 10 лет, а искать просто перебором тоже не очень то

Как насчёт эктраполяции касательной?

Это выглядит интересным, но у меня просто функция на java,которая выдает long а принимает int. Может что проще есть ?

То есть вы говорите, что ограничений нет, а у вас ограничение int?

Наверное, даже int. Функция же int принимает

Да, поправил)

Да, так и есть.  Лонг и есть опасения ,что при слишком большом входном параметре может быть переполнение

А вы не знаете что функция считает?

На int.max_value хотелось бы ее не вызывать ). Там наверняка будет переполнение и результат в Лонг не поместится

Знаю. Там сумма значений g_i^day

А g_i - что?

Есть метод типа

long doSomething(int x)

Который неизвестно как работает, но при увеличении x выдаёт возрастающий результат, правильно?
И надо сделать наподобие

int getMinX(long y)

который возвращает минимальное значение x, при котором результат doSomething(х) будет меньше, чем y. Так?