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.
Oh, this method is so beautiful, but how can we accurately calculate $$$e$$$? Since $$$i^i$$$ can be really big, an error of $$$0.3$$$ or $$$0.7$$$ from $$$e - 2$$$ or $$$3 - e$$$ is a big problem.
For a composite , let p = spf(i) and i = p * m. Then i^i = (p * m)^i = p^i * m^i = p^i * (m^m)^p So once m^m is ready, I only need p^i and (m^m)^p. I process p from large to small. This is valid because if p = spf(i), then all prime factors of m are at least p, so spf(m) >= p. Therefore m^m has either been computed in an earlier stage, or earlier in the same stage. For primes, I compute p^p directly, but with short addition chains instead of binary exponentiation. For composites with the same smallest prime factor p, I keep a running value of p^i and move it forward using the gaps between consecutive valid numbers. This avoids recomputing p^i every time. I also do not initialize all A[i] = i. I only build the prime values and small gap values that are actually needed. Finally, I use one power-of-two index as a temporary cell and restore it at the end, since s^s can be rebuilt by repeated squaring. These tricks bring the number of operations under 5N.
can you explain to me what is short addition chains? Also do you compute (m^m)^p with such technique?