FUNC - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vivek Hamirwasia
Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa

DIFFICULTY:

Medium

PREREQUISITES:

number theory, binary search

PROBLEM:

You are given an array A. You are given Q queries, In each query, you are given a number x and asked to find f(A, x) where
f(A, x) = root(x, 1) * A[1] + root(x, 2) * A[2] + … + root(x, N) * A[N].

root(N, x) is defined as x th root of N. In more formal terms, it is the largest y such that y x <= N.

QUICK EXPLANATION

  • Most important observation is that the root(x, k) will decrease very fast and will become 1 soon.
    If at some iteration, value of root has become 1, then we don’t need to iterate over the entire remaining part of the array,
    we simply need to find sum of the remaining array.
    For finding sum of a specific part of array, we can use calculate prefix sums and use them to compute the sum of any part.
    eg. Let prefixSum[i] denotes the sum of array from 1 to i. Then sum of part of array from L, R can be easily found by prefixSum[R] - prefixSum[L - 1].

    We can simply note that in our case, we needs sum of the suffixes of the array (ie R = N). So we can simply compute sum of suffixes
    and directly use them to calculate our answer.

  • Root(x, 60) = 1 for all x ≤ 2 60 .

  • Hence for each q from 1 to 60, we need to find p such that p q ≤ x.

  • We can do a binary search to find value of p.

  • In the binary search, we need to check the conditions of form p q ≤ x. We can not do that by simple looping in O(q)
    time as it will get TLEd.
    So we need to check the above given condition faster. For that we can make use of following facts.

    • if q = 1, then p = x.

    • if q = 2, then p = sqrt(x).

    • if q = 3. then p <= 10 6 . So we will already store all possible powers of numbers <= 10 6 .

  • After doing these optimizations, we will make sure that p is surely less than 10 6 . Now we can do a binary search of p over
    values from 1 to 10 6 .
    Note that we need O(1) computation for computing the powers of numbers below 10 6 as they are already stored in the pre-computation
    step mentioned above.

EXPLANATION

We will show that root(x, k) decreases very fast and becomes 1 in at most 60 steps. So for x ≤ 10 16 , root(x, k) will reduce to 1
in at most 60 steps.

Note that root(x, k) means to find largest p such that p k ≤ x.
For x = 2 60 and k = 60. p will be 2.
For x = 2 60 and k = 61, p will be 1.
If k becomes largest than log(x) then p will become 1. Hence we have proved this fact.

So by using this fact, we simply need to find first 60 terms only.

Now how to find f(A, x) ?

Note f(A, x) = root(x, 1) * A[1] + root(x, 2) A[2] + … + root(x, N) * A[N].
So f(A, x) = root(x, 1) * A[1] + root(x, 2) A[2] + … + root(x, 60) A[60] + 1 * A[61]+ 1 * A[N].
Hence it becomes f(A, x) = root(x, 1) * A[1] + root(x, 2) A[2] + … + root(x, 60) A[60] + Sum of the array from 61 to N.
Finding the sum of the array from 61 to N, you can store the cumulative sum up to i th index and make use of that.
You can also store the suffix sum ie suffixSum[i] will denote sum of elements from i to N. Hence sum of array from 61 to N will be suffixSum[61].


So will iterate over q from 1 to 60. We need to find largest p such that p q <= x.
Note that we can just iterate over values of p from 1 to x and check whether p q <= x. Complexity of this solution is too high, because it
will need O(x) step, Our x is at most 10 18 , doing 10 18 computation won’t fit in the time.

So we need to somehow optimize this.
Note that p^q is an non-decreasing function over q.
So we can do binary search on the function.

Can we somehow get a good estimate of values of p, Yes, we can use pow function in C++/Java and get pow(x, 1.0 / q), it will give us a good estimate of
possible values of p, as the computation in double is not reliable, we will take some margin of error (let us say 100).
So our range for binary search will be pow(x, 1.0 / q) - 100 and pow(x, 1 .0 / q) + 100.


Now in the binary search routine, we need to check whether given p, q, x whether p q <= x or not?
We can do this by simply powering directly in O(q) time. But it will time out in our case.
We can compute this by powering by squaring in O(log(q)) time, Unfortunately, this will time out in our case.
We need to do something fast.

We make following simple but important observations.

  • if q = 1, then p = x.
  • if q = 2, then p = sqrt(x).
  • if q > 2. then p <= 10 6 . So we will already store all possible powers of numbers <= 10 6 .

So in the case of q > 2, we will store all the powers of the numbers p, Note that these powers are not much, they can be at
most (10 6 log(10 6 ))
which will easily fit in the memory (Proof of this is left for readers as homework).

So we will first check whether q <= 2 or not. If yes, then we can directly compute the answer using the previous observations.
Otherwise we will do a binary search of p over values from 1 to 10 6 .

Note that we need O(1) computation for computing the powers of numbers below 10 6 as they are already stored in the pre-computation
step mentioned above.


Note the following important point.

If you have to check whether a * b <= x or not, where a, b and x all fit in long long.
Then we can not directly check it by doing if (a * b <= x), because a * b will not fit in long long and will overflow,
which will make our calculations erroneous.

Instead we can check the above condition in the slightly modified way, ie. if (a <= x / b). In this way both a and x / b will fit in long long and
wont overflow. You should pick up this trick and it will be really helpful in programming contests.

Complexity:
O(log(10 6 ) * 60) per query.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

15 Likes

unable to download the author’s solution/tester’s solution.please check it!

Can any one give some corner test cases. I have checked my code(logic is similar to above one, this is in C) with the bruteforce(this is in python ) with many cases.Both the outputs matches for all the cases.I could not understand where my code fails.Any one please help to debug

http://www.codechef.com/viewsolution/4095014

It is possible to calculate root using C++ std::pow() with taking care of precision errors.

5 Likes

1
3 1
4 5 6
1000000
Your code gives Wrong answer atleast for this Test Case

1 Like

Thanks a lot that helped me, I have struggled for this problem from last 2 days with so many WA

did’t know that pow func can give wrong results. caused me multiple wa and several days of headache and still no ac.
I think it should have been mentioned in the problem that pow func causes precision errors.

2 Likes

Newton’s method should be faster than binary search as it gives quadratic convergence as opposed to linear convergence. Can anyone tell, why do I get a TLE then? http://www.codechef.com/viewsolution/4106068

Instead of pre-computing the roots I calculated them on the go. I knew by running 10^18 as a query on the sample test case that there were precision problems with simply using pow() and trying out the nth root algorithm with an initial guess of 1 made it time out. So I ended up finding a fine balance between the two by first calculating an approximate root using pow() and then plugged that into the nth root method as my initial guess, let it run once, and then use that as my nth root.
Granted, its not the fastest method but I just thought I should mention it.

3 Likes

your EPS is probably too small. try increasing it, as you only need the integer part of the root.

I am not happy with my performance. :frowning:

5 Likes

can anyone provide some corner test cases. I used binary search with previous (n-1th) root as initial guess. getting WA. please help to debug

http://www.codechef.com/viewsolution/4092148

i think your o[] vector is wrong. o[1] should be 10^18, o[2] =sqrt(10^18)=10^9 … you missed the first root: no root at all => j = 1

Exactly the same method :smiley:

@caioaao-thanks for answering, but in the code, o[j] contains the overflow value x such that x^(j+1) is just less than or equal to 10^18
(my code works for the test case given in the problem)

1 Like

try this on your nth root implementation then, right after the while loop:
http://pastebin.com/kaDHzghW

Yes it is possible.
To find the nth root of x, find y = pow(x, 1.0/n)
Because of precision errors, the answer could be either y rounded up or down. So lo = y and hi = (y+0.5)
Check if pow(hi, n) <= x, if yes, hi is the root else lo is the root.
2 pow calls to find one root.
I managed to get AC with that :smiley: http://www.codechef.com/viewsolution/4088724

1 Like

WA again
http://www.codechef.com/viewsolution/4106864

the only thing I can see that’s different in your implementation is that you’re not testing if ans < 0 (see first two comments in http://www.codechef.com/JUNE14/problems/FUNC).
try printing (ans+MOD)%MOD to ensure it’ll never be negative. other than that I can’t see anything wrong in your implementation, and all I’ve tested using your code gives the same output as my AC implementation.

Did everything almost the same but then too tle…plz help

http://www.codechef.com/viewsolution/4107738