@sudip1401
i did something on the similar lines but am getting tle…
why?
http://www.codechef.com/viewsolution/4108853
PLZZ SUGGEST ANY WAYS TO REMOVE TLE IN FUNC…
SOLN LINK… :-- http://www.codechef.com/viewsolution/4109517
THNX IN ADVANCE
@tyler_durden You’re calling pow(x,r) twice. Call it once and store it. And don’t use the floor and ceil functions, they’re an overhead, simply assign to the LL variable to get floor and +0.5 to get ceil. If it still gets TLE, use scanf printf instead of cin cout.
you are repeatedly computing for the sum of a[60] to a[n] each query…
you can precalculate the sum before entering the query…
I couldn’t find any single test case for which my code give wrong ans…please tell me the error in code.
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. http://www.codechef.com/viewsolution/4077616.
A few doubts:
- computing pow(x,i/i) while traversing over the array upto 61 indices. Would it be costly for each query?
- 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)
- 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).
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