Dima TAleksandr SharahovB 18783990 тот же самый алгоритм сравнения )
ты тут перемудрил


затестил ради интереса - не проходит мой код с такой проверкой.
у меня проще



Да нет, вроде верно все. Просто epsilon он на то epsilon, чтоб его подбирать при настройке алгоритма.
Задача тут отсечь равные с учетом накопившихся ошибок, не затронув при этом почти равные.



Dima TAleksandr SharahovДело в том, что таких башен конечное число, и, похоже, что после склейки верхних уровней
не существует таких башен высотой более 4 (если считать склеенные уровни за 1).
Т.е. главная фишка алгоритма - именно склейка верхних уровней.
c 10 до 4 не склеить даже если там одни двойки. 2^2^2^2 = 65536 а дальше не склеить.

Но т.к. по условию задачи исходные уровни не более 99, т.е. максимум склеиваются три верхних в один, например 2^2^2 = 16
Как следствие функция проверки должна работать без склеивания. А если она не работает, то значит должна существовать такая пара пятиуровневых башень A(a1^a2^a3^a4^a5) и B(b1^b2^b3^b4^b5) удовлетворяющих условию A<B при
a3^a4^a5>b3^b4^b5 или (a3^a4^a5=b3^b4^b5 и a2>b2) или (a3^a4^a5=b3^b4^b5 и a2=b2 и a1>b1)

Ломаю голову как найти такую комбинацию, т.е. доказать что без склейки никак не решить. Перебор тут на годы может растянуться.

Ты не понял.

У меня речь идет о 4х ВЕРХНИХ уровнях,
причем после того, как самый верхний их них был получен склейкой
(см. мой алгоритм сравнения 18783990 )


P.S.
Задачей этой почти не занимался, только в метро иногда размышляю, да слежу, что тут пишут )
Все на выходные откладываю удовольствие.
По-хорошему, про 5й уровень доказать надо, что там нету наших башенок, а то все решение коту под хвост.
Да и не особо теперь доверяю проверке от авторов задачи )

Dima TAleksandr SharahovТы не понял.

У меня речь идет о 4х ВЕРХНИХ уровнях,
причем после того, как самый верхний их них был получен склейкой
(см. мой алгоритм сравнения 18783990 )
Не сработает на такой


99^99 это 197 десятичных знаков, а в double мантисса всего 15, т.е. хвост теряется из-за погрешностей.

Да посмотри уж, наконец, мое решение 18783990 )
Все сработает.

Повторяю еще раз, твое решение полностью совпадает с моим.
Разница только в работе с epsilon, которую я не настраивал, т.к. пока не занимался этой задачей плотно.

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

К тому же я, похоже, знаю где искать почти одинаковые башенки.

Вопрос только во времени.

Dima T,

да, думаю )

Твой пример показывает, что от схлопывания может быть не только польза, но и вред.
Чтобы все сработало правильно, надо подстроить жадность алгоритма схлопывания.
У меня она задается константой 2470, исходя из которой рассчитаны значения элементов MaxBaseForPower.
Значит, нужно изменить порог схлопывания так, чтобы оно не выполнялось в данном случае - и все сработает.

Я пробую обсуждать алгоритм, а не значения констант )

Dima T,

Кстати, там же в исходнике строчкой выше объявления массива MaxBaseForPower для константы 2470
закомментирован другой вариант объявления для константы 300.

Если его раскомментировать, то твой пример проходит.

Dima TЯ так и не понял это ноу-хау с MaxBaseForPower.


Да там примитивно все.
Пусть два самых уровня башни представляют собой башенку a^b.
Тогда мы заменяем их одним эквивалентным уровнем ("склеиваем"),
если в результате склеивания будет получено значение не больше
некоторой константы (например, 300), в противном случае не склеиваем.
Такое шаманство позволяет "улучшить" плохие башни с маленьким числом сверху.
Это улучшение позволяет сосредоточить основные вычисления на верхних 4х уровнях.
Как мы видели выше, слишком увеличивать эту константу опасно,
т.к. ошибки вычислений приводят к невозможности различить разные башни.

В общем, как раз этим мне и не нравится это решение.
Какие-то полуинтуитивные действия приводят к успеху.
Хочется не то чтобы строгого доказательства,
но хотя бы четкого обоснования, почему все работает.
Почти уверен, что если в условии 99 поменять на 255, алгоритм не сработает.

Ну, и хотелось бы иметь возможность проверить работу алгоритма автора задачи )

Aleksandr Sharahov, пропущено слово ВЫСОКИХ:

Пусть два самых ВЫСОКИХ уровня башни представляют собой башенку a^b...