Statement (in Vietnamese) and submission link: https://oj.vnoi.info/problem/tst25_bai2.
Summary: Given an integer $$$N$$$ and an array $$$A$$$ of $$$N$$$ elements. Initially, $$$\forall 1\leq i\leq N:\ A_i = 1$$$. You need to perform some operations (possibly none) to make all $$$A_i = i^i$$$. There are two types of operations:
- $$$+\ i\ j\ k$$$: make $$$a_k\leftarrow a_i + a_j$$$.
- $$$*\ i\ j\ k$$$: make $$$a_k\leftarrow a_i\cdot a_j$$$.
To pass the test, your total number of operations (let's call it $$$Q$$$) must satisfy $$$Q\leq 5\cdot N$$$. Otherwise, you will receive points according to the following formula:
- If $$$Q \gt 20\cdot N$$$, you receive $$$0$$$ points.
- Otherwise, you receive $$$0.9^{Q - 4}$$$ points (on a scale of $$$1$$$).
I already have a solution using binary exponentiation, but it only scores 30/100 (code: https://ideone.com/SBgtEt). Please help me. Thanks for your attention!
I haven't solved the full problem yet, but by simple inspection the ratios of (i^i)/((i-1)^(i-1)) converge to an arithmetic sequence with common difference = e (2.718).
Here is some python code to demonstrate this.
>>> f = lambda n: n**n
>>> g = lambda i: f(i+1)/f(i)
>>> [f(i) for i in range(1,13)]
[1, 4, 27, 256, 3125, 46656, 823543, 16777216, 387420489, 10000000000, 285311670611, 8916100448256]
>>> [g(i) for i in range(1,13)]
[4.0, 6.75, 9.481481481481481, 12.20703125, 14.92992, 17.65138460219479, 20.371997576325704, 23.09206062555313, 25.81174791713197, 28.5311670611, 31.25038814277037, 33.96945877292082] >>> [g(i+1)-g(i) for i in range(1,13)]
[2.75, 2.731481481481481, 2.725549768518519, 2.722888749999999, 2.7214646021947893, 2.7206129741309155, 2.720063049227427, 2.7196872915788397, 2.719419143968029, 2.7192210816703692, 2.7190706301504477, 2.7189536574794317]
>>>
the implication is that you could keep a counter index = floor(current ratio) , and add either +2 or +3 to it each time to get the next ratio floor. this way, using the already computed i^i you can get an approximation of (i+1)^(i+1) in the range (i+1)^(i+1) — i^i <= x <= (i+1)^(i+1). this would only take 3 operations (increment the counter, multiply Ai by Ai-1, and multiply Ai by counter), so if you could take it from approximation to actual value in <= 2 more moves this would get full score.