Author: Ryan Leonel Somali
This was the hardest problem in the contest. I could not solve this problem without any help or hint from the author (Ryan Leonel).
Hyper operator of level n is defined recursively as a repetition of level (n – 1) hyper operator. I will note hyper operator of level n as hypern (e.g. hyper2, hyper3, etc.).
We can write each of hypern as:
hyper0(a,b) = a(0)b = 1 + b hyper1(a,b) = a(1)b = a + b hyper2(a,b) = a(2)b = a + a + ... + a = a x b hyper3(a,b) = a(3)b = a x a x ... + a = a^b hyper4(a,b) = a(4)b = a^(a^(...^a)) = a^^b hyper5(a,b) = a(5)b = a^^(a^^(...^^a)) = a^^^b
and so on…
I’m sure most of you are able to solve hypern-mod for n <= 3 (addition, multiplication and exponentation). If you have solved UVA 10692 (Huge Mod), then solving hyper4-mod would be easy for you, as UVA 10692 is a generalized version of hyper4-mod. The figure below will give you some ideas about how to solve hyper4-mod (tetration).
Any hypern can be expressed by hyper(n-1). It means that any hypern for n >= 4 can also be expressed by hyper4. Let me show you some examples:
2^^^3 = 2^^(2^^2) = 2^^(2^2) = 2^^4 2^^^4 = 2^^(2^^(2^^2)) = 2^^(2^^(2^2)) = 2^^(2^^4) = 2^^(2^(2^(2^2))) = 2^^(2^(2^4)) = 2^^(2^16) = 2^^65536 3^^^^3 = 3^^^(3^^^3) = 3^^^(3^^(3^^3)) = 3^^^(3^^(3^(3^3))) = 3^^^(3^^(3^9)) = 3^^^(3^^19683) = ...... I give up!
Ryan, If you read my blog then I beg you… please DO NOT paste the exact value of 3^^^^3 in my blog’s comment!!
To solve hypern-mod for n >= 5, you’ll need this amazing fact: “The cycle size in each exponentation level will decrease VERY FAST!”. What make it more amazing is, the maximum level to decrease the cycle size from m to 1 never reaches 20 (for any valid input in this problem). It means that the value of 2^^99999999 mod m will be the same as 2^^20 mod m. To be exact, any hypern(a,b) mod m where n >= 4 and b >= 20 will be the same as hyper4(a,20) mod m. This fact REALLY decreases the search space significantly.
No team solved this problem.
- Title Page
- Problem A – Anti Brute Force Lock
- Problem B – Bonus Treasure
- Problem C – Panda Land 7: Casino Island
- Problem D – Disjoint Paths
- Problem E – Expert Enough?
- Problem F – Free Parentheses
- Problem G – Greatest K-Palindrome Substring
- Problem H – Hyper-Mod
- Problem I – ICPC Team Strategy
- Problem J – Jollybee Tournament