is finding root via binary search (as applied in editorial) better than directly doing floor(pow(x,1/p)) where x is the input and p signifies the pth root(iterating from 1 to 60).
x,p are double.
if so why?
use floor(pow(x,1/p)) for x=1e18 and p=3 u wont get correct ans…i guess the reason would be by doing 1/3=0.3333333 and there z a precision error in dat n so exact power wont be returned
when i used this approach it gave TLE not WA(please excuse me, i am a novice)
as per your answer : http://ideone.com/EVvckj
is finding the root via the method specified in editorial faster?
yes siddv29, i also tried 2 solve in a similar manner but due to precision error of pow, u will not get a correct answer also pow is slower compared 2 the method specified in editorial… it will be better if u apply the algorithm specified in the editorial…
I got AC by adding a simple condition to the return val of pow function :
temp = floor(pow(x,1/p))
if(pow(temp+1, p) <= x){
temp = temp+1;
}
this handles the precision issue.
@u_seem_surprsd i didnt quite get what that approach means. can you please explain it once?
@u_seem_surprsd, @svishal is the editorial method really faster than pow?
@u_seem_surprsd i got a TLE for a reason i dont know.
How can precision create a problem here. and if as you did, why shouldn’t we check for temp+2 and so on.
That part confuses me. Can you explain that please?
The condition checks if the pow function has returned correct value or not, while calculating using pow suppose the answer is 10 but pow function returns 9.9999999 since we store it in a integer, its value gets rounded down to 9, therefore i check for 10 and raise it to the power p if ans is <= to x that means that value was rounded down and hence should be incremented by 1.
1 Like
siddv29, u_seem_surprsd has given you a very good answer. Think about it…and it’ll make sense. I “think”, and if i am wrong i will start a new discussion, even doing a “temp+2” will still give you the right answer. But we want to narrow the range to search for, as much as posible. So, just “+1” will/should do.