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

16 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

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? CodeChef: Practical coding for everyone

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.

4 Likes

I am not happy with my performance. :frowning:

7 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

Exactly the same method :smiley:

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

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

PLZZ SUGGEST ANY WAYS TO REMOVE TLE IN FUNC…

SOLN LINK… :-- CodeChef: Practical coding for everyone

THNX IN ADVANCE

Can somebody please explain why is This Solution giving WA, while this solution is giving AC.

I couldn’t find any single test case for which my code give wrong ans…please tell me the error in code.

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

There is one more way to do this question, view my accepted solution. Using pow() function and using fast exponent method to find a^b, where a and b are integers. CodeChef: Practical coding for everyone.

A few doubts:

  1. computing pow(x,i/i) while traversing over the array upto 61 indices. Would it be costly for each query?
  2. What you are saying is it that we should compute 1…to…10^6 raised to power 3…to…60, and then as per x and i(used for iteration and determining the i/i th power) search for a p(1…10^6) and look for the value closest to that of x(less than or equal to)
  3. Had there been more limitation on space, would calculating upto upto x^5(as we did the sqrt(x) in current solution) we could have done it in space of 10^3 and 6-60?

if the statements are a bit confusing i will restate them.

When we need to find that whether p^q<=x.Can we not do it in O(1) by finding whether q*LOG§<=LOG(x).

Can anyone please debug my solution : https://www.codechef.com/viewsolution/9714771

nth root can be calculated by using following formula

fun(ll x, ll n) {

return pow(10,double(log10(x)/n));

}
it gives ac to my solution

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

1 Like