11752  The Super Powers
Moderator: Board moderators
11752  The Super Powers
Any Ideas How To solve This Problem efficiently ....
and How To handle The overflow?
any help is appreciated.....
and How To handle The overflow?
any help is appreciated.....
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)

 Learning poster
 Posts: 64
 Joined: Fri Sep 25, 2009 11:29 am
 Location: Chittagong,University of chittagong
 Contact:
Re: 11752  The Super Powers
How can i solve this ?
I have got TLE.
Please help any body.
I have got TLE.
Please help any body.
Try to catch fish rather than asking for some fishes.

 Learning poster
 Posts: 64
 Joined: Fri Sep 25, 2009 11:29 am
 Location: Chittagong,University of chittagong
 Contact:
Re: Goods20100215fifty11
// What is this ..................
It is very important forum for the programmers but not for others ...............
Try to catch fish rather than asking for some fishes.

 Learning poster
 Posts: 74
 Joined: Fri May 08, 2009 5:16 pm
Re: 11752  The Super Powers
Take the composite powers of nos upto 2^16
2^4
2^6
...
3^4
3^6
..
4^4
4^6
..
To handle overflow before multiplying just chek it log(no1)+log(no2)<64log(2)
2^4
2^6
...
3^4
3^6
..
4^4
4^6
..
To handle overflow before multiplying just chek it log(no1)+log(no2)<64log(2)
Re: 11752  The Super Powers
My best for this problem is 0.032 (The best for this problem is 0.028 ). And I didn't even optimize my code, no I/O opt nothing. (May be someday I can beat the best record with I/O Optimization ). I am not going to tell you my algorithm....no way guys but I can give you hints. You have to print a total of 67385 lines(including 1). And think a bit, what property would a number have if it is the power of at least two different positive integers? For example 16 = 2^4 and 4^2 and 729 = 3^6 and 9^3 and 27^2 etc. No more hints for you, you must solve this problem by yourself Be assured, you won't get WA or TLE if your algo is correct and efficient and you are printing exactly 67385 lines(In increasing order). (You can check this by increasing a counter variable starting from 0 whenever you are printing a line and later just print that counter variable )
Last hint(probably the most useful one) : You have to print all the numbers in ascending order as specified in the description. However this does not necessarily mean that you have to FIND all such numbers in ascending order.
Last hint(probably the most useful one) : You have to print all the numbers in ascending order as specified in the description. However this does not necessarily mean that you have to FIND all such numbers in ascending order.
You tried your best and you failed miserably. The lesson is 'never try'. Homer Simpson
Re: 11752  The Super Powers
And @Angeh the best way to handle overflow in this problem is by using log/ln (any one will do), but I didn't use the log/ln function in my program
You tried your best and you failed miserably. The lesson is 'never try'. Homer Simpson
Re: 11752  The Super Powers
For check Overflow
You can use
Example:
1. If powerBase=3 then power=41 (i.e. the maximum power of 3 is 40, 3^40 < 2^641(unsigned long long range)). 3^41 is overflow at 64 bit integer.
2. If powerBase=5 then power=28 (i.e. the maximum power of 5 is 27, 5^27 < 2^641(unsigned long long range)). 5^28 is overflow at 64 bit integer.
You can use
Code: Select all
int bit = 64;
int power= ceil(bit / (log(powerBase)/log(2)));
1. If powerBase=3 then power=41 (i.e. the maximum power of 3 is 40, 3^40 < 2^641(unsigned long long range)). 3^41 is overflow at 64 bit integer.
2. If powerBase=5 then power=28 (i.e. the maximum power of 5 is 27, 5^27 < 2^641(unsigned long long range)). 5^28 is overflow at 64 bit integer.
"Learning to love yourself is the greatest love of all"  Michael Masser and Linda Creed