Убийственная математика

Заметим, что из каждой пары $$$(a, b)$$$ мы можем получить четыре различных результата. Сделаем bfs по такому неявному графу и получим минимальное «расстояние» от исходной пары до пары с двумя одинаковыми элементами.

Данный алгоритм работает за время $$$\mathcal{O}(b^2)$$$. Количество операций до достижения ситуации $$$a = b$$$ меньше $$$\log_2 b$$$, так как есть последовательность изменений, в которой расстояние между числами каждый раз уменьшается хотя бы в два раза (всегда заменять $$$b$$$ на меньшее из двух средних, например). А тогда максимальное число состояний bfs равно $$$4^{\log_2 b} \sim b^2$$$.

Так же за ту же асимптотику работает метод динамического программирования по подотрезкам, где $$$\mathtt{dp}_{i,j}$$$ равно минимальному числу операций до достижения пары равных чисел. Пересчет происходит за $$$\mathcal{O}(1)$$$, так как из каждого состояния есть не более четырех переходов.

Тем не менее, есть жадный алгоритм, так же решающий эту задачу, но за $$$\mathcal{O}(b)$$$, который каждый раз заменяет $$$b$$$ на минимальное из двух средних, однако сложность его доказательства не позволяет рассматривать его как ожидаемое решение, и поэтому все правильные решения за $$$\mathcal{O}(b^2)$$$ получали вердикт «OK».