FUNC - Editorial

editorial
, , , , ,
10

Exactly the same method :smiley:

11

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

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

12

PLZZ SUGGEST ANY WAYS TO REMOVE TLE IN FUNC…

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

THNX IN ADVANCE

13

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

14

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

15

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.

16

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.

17

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).

18

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

19

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

20

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

1 Like
21

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

22

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

23

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

24

@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
25

try this on your nth root implementation then, right after the while loop:

26

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

1 Like
27

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

28

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

29

@sudip1401
i did something on the similar lines but am getting tle…
why?
http://www.codechef.com/viewsolution/4108853