The Rise and Fall of Power

Does the given time limit indicate compile time? Or the time for producing the output?

Is there anyway to limit the input size? i could not use double (in java) for such a big number. Mine should work for n value till 140 (where n^n is within double limit). Any help please

@jagan

Have you considered using java.math.BigInteger ?

-Zach

@jagan It is possible to code this in C . You can't possibly store that large a number in a double. Think of other ways to get the required result.

There is a problem with overloading the pow() function.

hello admin..

I am new to codechef..I am working on my first problem "The Rise and Fall of Power"..I saw in the FAQ's that the file should be names Main.java...and i think that, the only file my solutions should have is Main.java..no more class files...please correct me if i am wrong..

thank, Jaydip

Yes, that is correct. Name your class as Main.

hello admin,

I was working on this problem using Java (1.5), I am testing my solution for larger numbers like 1000000000...but i think due to the known bugs as listed below, the performance is getting too slow...is it possible to solve this using Java...

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897

Hello Admin,

Please check my submitted solution and inform me if the way of taking user inputs one case at a time and displaying the result output to the console cause the result "Time limit exceeded"...or something else..

Thanks,

Jaydip

hey suppose if thwe input is

1

100 5

then shud the output be

10000 00000

or

10000 0

Any ideas??

hi admin .. isn't cout , cin , iostream recognizable in c++ with linux .  i am using windows . any substitute??it is giving compilation error but program is compiling successfully in my pc

They work perfectly fine (though are extremely slow, so you really shouldn't use them). Perhaps you are doing something like forgetting using namespace std; or something else to cause a compile error.

Hi all,

I am getting time out result.

Is it possible to get single threaded optimal solution for this problem.

Hi all,

Is anyone get the single threaded correct solution for this problem..

Hi all,

Is it possible single threaded accepted solution for this problem.

I have submitted a solution which is showing time out.

I optimize my code enough. still it is showing same.

Should i go for multi-threading??

plz give me hints..

You never need to write a multithreaded solution for any of these problems.

Hi Admin,

I have tried multiple solutions to this problem. As discussed in the blog, if my solution is "numerically-correct" and which it is, it should not give WAs. I see that there was some problem with the test data earlier. Is it resolved ?

My output for the input set that Shishir Mittal has posted above matches with his. So there's a stronger reason to believe that my code is giving correct output.

Please check and let me know.

ADMIN ... i am getting runtime error for my code ... can u plz tell why ... it's working on my system

@Abhyajit Please read the FAQ and www.codechef.com/wiki

Hi Aniruddha,

I have been working on this problem for very long time. Its working fine on my computer even for very large values. But here its saying wrong answer. I think the error must be with the first part of output i.e the first k digits of the number. It would be very helpful if you can tell me for what test cases its failing. Or any suggestion in this direction would be helpful.

Thanks,

Arun

in Java if an exception like arrayindexoutofbound occurs in a submitted solution will the judge show it as WA or run time error ??

That is exactly what runtime error means.

i have got the idea of the problem clear..my code is giving correct output for some cases but for some cases there is rounding off error as i am using log to solve the prob.i have read abt adding epsilon to counter tht error in uva forum...bt didnt get it..can anyone expain abt this a bit more..giving some example or some url abt it...

@admin I am trying to submit my solution in php. Can you please tell me what error I am doing. The code runs perfectly in my laptop. Can I post my code here?

I submitted solutions for some other problems which takes a lot of memory for php in comparison to c. for same algo, I also had the timeout error for the same code of C/C++/Jave (Successfully compiled programs) written by some1 else when I change the syntax to PHP

can any one plz confirm that the output given by sishir mittal given above is correct or not

my output is matching with his output by i am getting WA. So plz confirm whether his output is corret or not

my program gives the same output as given by shishir mittal but i am getting WA.

please anyone confirm whether the output is correct or not

@Alok

I am also getting the same o/p but its showing WA....

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474

It is impossible to calculate the full value of n^n in any language and get accepted within the time limit. That is not the approach you are supposed to take in this problem.

@ Admin,

I am unable to get any idea for this problem . Plzzzzzzzzz try to provide the tutorial for this problem :P .

@stephen

so  some other approach is to be used to calculate full value or there is no need of calculating full value(answer could be obtained without calculating full value)?

As I said, calculating the full value is impossible. You must use another approach.

i am getting the right outputs but a run time error. I have coded in simple c++ but used recursion to calculate the last k digits. Is it because of the recursion that I am getting runtime error?

I am facing a precision problem here. Not able to get the last digit from the first digits. I have tried 6 approaches but could only get the precision till first 8 digits at best. Any suggestions.

Chefs, Need a clarification: Are all the 30000 testcases required to complete within the 4 allowed seconds? Or is it a maximum of 4 seconds per test case?

FAQ

faq! thanks, should've done that first.

Its interesting how there isn't even a single successful Java solution to this problem. Time to abandon the libraries I suppose - too slow!

Can any one provide me the o/p for the large value actually i wanna know whether my programe is running correct or not.

leg eg: give me the o/p for K=84246793

You can use Wolfram Alpha(http://www.wolframalpha.com/) to check your answers

@BorT btw K has to be <=9

Dangit, more java optimizations, still out of time.

Hey Stephen, you're a Java dude. and I see you don't have this problem in your list, want to share ideas?

@admin

N=84246793( random)

provide me output. for any large number i want to check

for N=594859374,K=9

o/p =321824352 095142400

is this o/p is correct can any one can help

for N=594859374,K=9

o/p =321824352 095142400

is this o/p is correct can any one can help

AC Outputjunk@debian:~$ echo 1 19423474 8 | ./a.out
16307491 26110976
junk@debian:~$ echo 1 19423474 9 | ./a.out
163074912 826110976
junk@debian:~$

@everyone

i have method to calculate higher n^n but while we calculate 10^9 is near about 9*10^9 decimal digit and the code cross memory usage limit then how we can store it in memory...???

Trying to calculate the full value is impossible. You have to figure out a way of just calculating the digits you need.

@Admin :

I have been trying this problem for quite a while now ... have made a few sumissions. I am getting "wrong answer" each time. Can you please provide me with some help / hint ?

Thanks :)

@ admin :

I tried a new approach to the solution. My code ran for a longer time but yet again - I got "Wrong Answer" . Can u plzz help me out ?? Where am i going wrong ?

@admin

if the input is

10 3

then should the answer be

100 000

or

100 0

The problem works fine on my system but i keep getting WA here..

Please help..am I missing some special test cases ??

@admin

my submission is giving a run time error

plz tell me the reason

Hello admin can u just have a look at this code I am sure that is right but it gives wrong answer!!

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

Hello Admin

Please check the above link!!

Same question again .

Should the answer for 10 3 be 100 000 or 100 0 ??

I think i am having precion problems, any hints i am using double and unsigned long long int . Calculating only first k and last k digits. my solution is at http://www.codechef.com/viewsolution/352153

@ Admin, could you please let me know what is the problem in my submitted solution, since I am getting WA which I think shouldn't be the case. http://www.codechef.com/viewsolution/357085

@admin please check these two links
http://www.codechef.com/viewsolution/349188
http://www.codechef.com/viewsolution/351625

Hey...

my code is in python... Have tried a lot of time, the algo is correct and is executing within the time limit... Have tried most of the test case and get the correct answers even for the worst ones. dont know what the problem is.... can you pls help!!!!

@admin- pls check this link

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

can u pls tell me where i'm going wrong.. it seems to be workin fine on my comp...

@^^ oops i dint mean to make it so big.. :P

To Admins:

I don't know how far the test cases are correct, but for first k digits I am using first k digits of 10^(fraction(nLog10(n))). Here are my observations:

Any number like n=457474575, 10^(fraction(nLog10(n))) = 2.7866096861492488724505088885778 as per windows calculator. But, in my code, the long double precision is only upto 15 places of decimal. So, when Log10 (15 places of decimal) is multiplied with a 9 digit number, i.e. 457474575, the correctness of (fraction(nLog10(n))) is only upto 6 places of decimal. Hence, when I raise the fraction to 10^fraction, I have a result which is correct to only 4 places of decimal.

I almost broke my head for the last two days to make the 10^fraction correct upto 9 places, but couldn't succeed. After repeated attempts, I was successful to be precise upto 8 places of decimal.

Guess what, when I submitted the 8 places decimal precise code, my code was repeatedly rejected as "wrong answer", but when I submitted the 4 place precise answer, my code was accepted.

For n = 457474575,

Windows calculator ans = 2.7866096861492488724505088885778 (precise upto 31 places of decimal)

8 places precise ans = 2.78660965 (rejected multiple times)

4 places precise ans = 2.78661176 (accepted)

I don't know how the test cases are determined, but here I can definitely say they are faulty here. I am new to CodeChef platform, and I was redirected to this puzzle from Directi carrers page. I am sorry to say that I am utterly disappointed as a new user, I worked hard on this problem for 2 days to make it 8 places precise, only to find those test cases are not considered here.

@Ujjwal you should read this

http://discussed.codechef.com/showthread.php?t=115

@Ujjwal - I'm afraid there is nothing wrong with the test cases (which do include ones like you mentioned). I'm not sure what you are using to compile your code, but on codechef and most compilers, long double has 18 decimal places of accuracy, compared to a normal double which has 15.

Your accepted code correctly outputs 278660968 for the test case you mentioned. If you wrote other code which you think has more accuracy, then that code must have a bug in it.

hi stephen! Thanks for your revert. I am using Microsoft Visual Studio 2008: Visual C++ as my compiler. Please suggest me any good compiler on windows. Also, here I found out that standard long double is 15 digits precise only, thats why the confusion: http://msdn.microsoft.com/en-us/library/s3f49ktz%28VS.90%29.aspx

@vivek, I figured out that and corrected it later

That is one of the special cases (see http://en.wikipedia.org/wiki/Long_double)

If you want to ensure that you are getting the same results as the judge then you should use the same compiler (gcc-4-0-0-8 or gcc-4-3-2), for which you can find compatible IDEs at http://en.wikipedia.org/wiki/GNU_C_Compiler .

Hey is the current requirement 6 digits or 9 digits of precision coz in that forum discussion it says only 6 digits required. also could the admin tell me if im failing in 1st k last k or both digits please?

Somebody please tell me why am I getting a wrong answer for this question!!

Internal Error. Can not submit your answer now. Please try after some time.

why is the judge showing me wrong answer ? is the internal error still persistent ?

Nope, you are getting wrong answer because your answer is wrong.

@all

what will be the output of

1 5

is it

00001 00001

or

1 00001

or

1 1

???

The 'Input' section clearly says that test case will not be provided.

n                k

34              9    :      117566389  909569536

23              8    :       20880467   32910567

92              9    :      466101087  933364736

199            7    :       2963208     3999799

234232       9    :      943982129  347762176

3476566     9    :      226270832  024828416

569999999  9    :      349261536  429999999

999999999  9    :      367879441  999999999

567891234  9    :      191465113  712180736

457474575  9    :      278660968  380859375

@Stephen :can you check whether above soln are correct or not??

@admin: Where i am doing wrong. http://www.codechef.com/viewsolution/426502.. Unable to verify for larger input.. Getting rite answer as far as  calc supports...

@Manohar - one of your results is off by 1. That suggests whatever approach you are using is not precise enough.

@nikhil - you can verify whether your approach will work for larger input. How many digits is log10(n) correct to? When you multiply that by a 9 digit number, how many digits will your number be accurate to? Is that enough?

Is it really so easy problem?? Why i am unable to do this even i have done problem of level 4. But no precise idea for this level 1 problem :(..

@admin,

I think my Python code is fast and precise enough to be accepted within time limit but gives TLE.

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

what astonishes me more is there are no python AC, all in c/c++ :O

everytime WA dnt know whats the prob please help!!!!!

My code: http://www.codechef.com/viewsolution/439918

does a 0(n) algo work for this ques

is 4 sec time limit for all testcases or for each testcase

@all....how can we find the last k digits....plzz....do reply....

Can anyone tell me where is my code giving WA : http://www.codechef.com/viewsolution/474576

please check the output for n=5 and k=4... if anyone gets a wrong answer please reply here... i was getting an exceptional wrong answer for this input.. is anybody else getting this exceptional case.. only with wrong answers reply.

Hi admin,

Can you give me a hint on where am I going wrong.

1. Is my algorithm incorrect and I need to think for a different solution or

2. I just need to tweak my algorithm?

Here is my solution: http://www.codechef.com/viewsolution/537865

Please guide.

@admin or anyone who has solved the problem

please guide where am I going wrong. At the least, please tell me if I am in the wrong direction so that I could stop wasting time. I am getting TLE.

My solution: http://www.codechef.com/viewsolution/539127

Thanks..

Can somebody tell what is the wrong with this result?

11
34 9
23 8
92 9
199 7
234232 9
3476566 9
569999999 9
999999999 9
567891234 9
457474575 9
1000000000 9
117566389 909569536
20880467 32910567
466101087 933364736
2963208 3999799
943982129 347762176
226270832 024828416
349261650 429999999
367880063 999999999
191464928 712180736
278661176 380859375
100000000 000000000