PPOW | Editorial

editorial
, , ,
1

Contest Link: http://www.codechef.com/CDSM2014

Problem Link: http://www.codechef.com/problems/PPOW

Author and Editorialist: Prateek Kumar

PREREQUISITES:

Pre- Computations, Storage of large numbers in an array.

PROBLEM:

You are given two numbers a and b, and you are supposed to calculate the value of ab for a number of test cases.

EXPLANATION:

  1. The constraint on b is 4000 and on a is 9. The value is large, so we have to store the value of ab in an integer array. This task was accomplished by simple modulo and division of the values. This allows to store the digits of number in an array.


    There is a problem http://www.codechef.com/problems/FCTRL2/ in the easy section that deals with the storage of large numbers in an array.

    The tutorial for the same is here: http://www.codechef.com/wiki/tutorial-small-factorials .
    This tutorial covers in detail the storage of large numbers in an array.

2.There was also the issue of time limit. Instead of computing the value of a^b for each test case, we can calculate the answer for each and every possible values of a and b store it in a 2-D array, before taking any input. This is known as pre-computation.
Also, when we calculate a^4, we also get the answer a^1, a^2 , a^3 at the iterations and finally get a^4. We can calculate all these values for a particular (a) by iterating from 1 to 4000 in one go. Calculate these for all values of a and store them in a 2-D array.

  1. This problem would have been very simple in python, and in JAVA using the BigInteger class. For this reason, python was not in the language choice and the BigInteger solution was not fast enough to pass the specified time limit.

SIMILAR APPROACH PROBLEMS:

http://www.codechef.com/problems/FCTRL2/


AUTHOR’S SOLUTIONS:

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

2 Likes
2

I applied the same logic but got TLE.
Here’s my


(http://www.codechef.com/viewsolution/5426035)
3

Hey, check my solution given above, you can see that I have calculated the values for all the possible values of a and b before even taking the input. I have stored these values in a 2-D array. This pre computation will prevent the TLE. You can simply use power[a] [b] (Here power[a][b] is the answer for a and b) directly.

4

thanks for the editorial
I tried many times using Exponentiation by squaring for biginteger and then gave up :confused:

is the problem moved to practice section?

5

Yes, the problem is moved to the practice peer section.

1 Like