You say you have a solution. Can you give an idea?

And towers to compare can be of different height?

It seems that the same problem is discussed here.

There is written:

Then

But what does

mean?

My unproved and probably wrong solution is like this. Let's evaluate the tower from top to bottom in floating point number until it's too large to go further. Then we discard the remaining bottom part of the tower and just compare the accumulated top values (if bottom parts are of equal height). Also, before doing all that, we have to somehow normalize the numbers and consider longest common top part.

I saw a similar problem at the IFMO's Internet Olympiad (russian statements, problem G). Unfortunately, jury's solution and tests are incorrect.

The test case posted is easy in the sense that it can be solved with loglog

let a=54^8^35^4

let b=19^55^92^3

log log a = 35^4 * log(8) + log log 54 = 3120463.347019

log log b = 92^3 * log(55) + log log 19 = 3120463.343260

But I can't see a way to generalize this. Is it a correct way to approach the problem?

still waiting for the solution.

hmmm, seems like ITERATIVE LOG (log*) function should do the work, shouldn't it ?

It seems that we need to find the maximum equal upper part of two towers, i.e. such minimal i and j that a_i^a_i + 1^...^a_n = b_j^b_j + 1^...^b_m for towers of heights n and m. To find potential i and j level-index arithmetic (some sort of implementation of iterative log idea) can be used. Then the equality must be verified using some exact computations.

By the way, how does modular arithmetic help to solve the problem? In particular, it is not clear how to prove that two towers are equal. If we found that two towers are not congruent modulo p, where p is prime, then they are not equal. However, the converse is not always true.

There are several reasons to find equal part of towers. The first is that it seems to be the only way to pass some tests. For example, if a = 5^99^99^99^99 and b = 6^99^99^99^99, then lnlna = lnln5 + ln99 × 99^99^99 and lnlnb = lnln6 + ln99 × 99^99^99. So, these expressions differ only by last few digits. If you want to deal with approximate representations of numbers, then you will have to store all significant digits, which is absolutely impossible.

The second reason is that if two towers are not equal, then it is affected very much by upper powers. I mean that if we have upper part of the first tower sufficiently larger than of the second, then we can't make the whole first tower smaller by modifying its lower part. For example, build two towers of equal height: the first with 16 on its top and the second — with 2. The first tower will be always greater then the second under given conditions: a₁^a₂^...^a_n - 1^16 > b₁^b₂^...^b_n - 1^2, where n ≥ 1 and 2 ≤ a_i, b_i ≤ 100 for 1 ≤ i ≤ n. This can be generalized:

This means that if the ratio of a and b is at least 10, then ratio of two towers, which have a and b on the top (bottom parts must have equal lengths), will also be at least 10 under constraints, given in the statement. So, if we process towers consequently from top to bottom, and at the same level found that first is sufficiently greater than the second (more than 10 times), then the whole first tower is greater.

One more important property is the following. If tops of two towers are big enough, but the second is slightly bigger, then the whole second tower will be at least 10 times larger then the second (here the previous property is taken into account).

This means that we will have to deal only with real numbers, bounded with something about 10⁹, unless there exist pairs of different almost equal towers, greater than this bound, but I can't see any way to prove it, except testing on all such cases. The bound 10^- 8 is taken based on two Petr's tests and can be lowered if necessary.

Sorry for cumbersome post, there are only some ideas on how to solve the problem. They may lead to a solution, very similar to al13n's one, and show that his solution is very likely to be correct.