Editorial for TLE '17 Contest 7 P3 - Countless Calculator Computations

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: leonchen0613

Dear Reader,

I wrote this problem in response to CCC 2018. That final year, I tied with 12 others for a score of 54. Because that would mean that 38 people would have gone to CCO, and typically less than 30 people are invited, the cutoff was set to 56 instead.

I was excluded.

After that, I developed depression. I lost all my will to do anything. I gave up on life.

Despite having worked so hard, I ended up falling 2 points short. My heart goes out to everyone else who has or will suffer from the same fate. To whom it may concern, yes, I'm talking to you.

Moral of the story: If you do well on the CCC, but not well enough to make CCO, then your hard work was all for nothing.

…

The above statement is absolutely wrong. (Happy April Fools)

I realized that there was so much valuable knowledge and experience that I have gained on that journey. We are so driven by our ambitions that we, like machines, become broken upon failure. But we are not machines - we are human. And humans make mistakes and learn from them.

Like Beethoven, I found my resolution in composing music. And in doing well at school. And in hanging out with friends. There is so much more to life than just making CCO (or even IOI).

So if you fail, it's not the end of the world. Let's have a drink (actually, probably not, since you're likely underage). "You'll be fine."

Anyways, back to the problem.

Firstly, note that the function $Z=X^{X^{X^\cdots}}$ ~Z=X^{X^{X^\cdots}}~ is monotonically increasing when $X \ge 1$ ~X \ge 1~. Therefore, we can binary search for an approximate value of $X$ ~X~ that yields $Z$ ~Z~.

The lower bound of $X$ ~X~ is $1$ ~1~ since $Z \ge 1$ ~Z \ge 1~, and the upper bound of $X$ ~X~ can be set to $10$ ~10~ since $Y \ge 2$ ~Y \ge 2~ and $Z \le 2^{31}-1 < 10^{10}$ ~Z \le 2^{31}-1 < 10^{10}~. Simply setting the upper bound of $X$ ~X~ to $2^{31}-1$ ~2^{31}-1~ may result in a TLE.

Applying this, the problem can therefore be solved in $\mathcal O(kQY)$ ~\mathcal O(kQY)~ time, where $k$ ~k~ $(k \le 48)$ ~(k \le 48)~ represents the maximum number of binary search trials in order to pinpoint $X$ ~X~ within an absolute error of $10^{-5}$ ~10^{-5}~.

EDIT: P.S. I still got accepted into Waterloo Computer Science so it's all good :)

Comments

11

Plasmatic commented on March 15, 2021, 5:19 a.m.

and typically less than 30 people are invited

18

weCryOPEN commented on Nov. 4, 2019, 4:58 p.m.

what a rollercoaster