After the first practice session and lunch followed a dress rehearsal, which is like a second practice session, but this time without coaches and otherwise much closer to the actual contest. This year, they presented 12 problems on the practice session (which I believe gives a clue that there'll be 12 problems on the main contest), and while 11 were very easy or quite easy, the last was very tricky, and I'm not aware of any team solving it successfully. The problem had a preface saying something like "this problem was intended for the main contest, but it was too easy so we moved it to the rehearsal", which apparently has been a joke :)
The problem boiled down to the following question: given two power towers, which one evaluates to a larger value? A power tower is an expression like 2232, or 2^2^3^2 if you don't see superscripts, which is evaluated right-to-left like 2^(2^(3^2)). Each number in both power towers is an integer between 1 and 100, and the height of the tower is also between 1 and 100.
After quite some time thinking and writing code together with Roman Elizarov and Evgeny Kapun, I believe we have a solution that works and that we can prove. A side effect of that is that I hope to be able to generate the "toughest" cases (probably after the tomorrow's finals), so if you think you have a solution that works, feel free to upload the code somewhere and post a link here, and I'll test it :)
While you're thinking about the problem, here are some pictures of teams doing the same:
And there are also pictures from the UPE dinner, which is the relaxation event between the two practice sessions and the actual contest. People sit and talk for several hours, distinguished service awards are given out to coaches and ICPC volunteers. This time it happened in another historic university building (which did remind me of many Russian university buildings, especially if one was to exit the main hall, which was different from the rest, and which is pictured below :)) - the Warsaw University of Technology.
The problem boiled down to the following question: given two power towers, which one evaluates to a larger value? A power tower is an expression like 2232, or 2^2^3^2 if you don't see superscripts, which is evaluated right-to-left like 2^(2^(3^2)). Each number in both power towers is an integer between 1 and 100, and the height of the tower is also between 1 and 100.
After quite some time thinking and writing code together with Roman Elizarov and Evgeny Kapun, I believe we have a solution that works and that we can prove. A side effect of that is that I hope to be able to generate the "toughest" cases (probably after the tomorrow's finals), so if you think you have a solution that works, feel free to upload the code somewhere and post a link here, and I'll test it :)
While you're thinking about the problem, here are some pictures of teams doing the same:
And there are also pictures from the UPE dinner, which is the relaxation event between the two practice sessions and the actual contest. People sit and talk for several hours, distinguished service awards are given out to coaches and ICPC volunteers. This time it happened in another historic university building (which did remind me of many Russian university buildings, especially if one was to exit the main hall, which was different from the rest, and which is pictured below :)) - the Warsaw University of Technology.
Oops sry, I just saw the constraints
ReplyDeleteHi Petr, may I know what are the constraints for the power tower problem? How many numbers can there be in a tower and how tall can the tower be?
ReplyDeleteI hope this solution works :) It would be great if you test it.
ReplyDeletehttp://pastebin.com/QYytsSL7
Sorry, I posted the solution too early, without proper testing. It was based on the hypotheses that the precision of 1e-8 will be enough. So, it failed on another tough test: 4^35^15 and 20^57^13. Also, using too many magic numbers is an evil! Here is a modified version with the precision increased up to 1e-12.
ReplyDeletehttp://pastebin.com/31ymMpNn