## 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.....
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Angeh
Experienced poster

Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

### Re: 11752 - The Super Powers

How can i solve this ?
I have got TLE.

Try to catch fish rather than asking for some fishes.
arifcsecu
Learning poster

Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong

### Re: Goods2010-02-15-fifty-11

// 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.
arifcsecu
Learning poster

Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong

### 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)
Learning poster

Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### 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.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

plamplam
Experienced poster

Posts: 151
Joined: Fri May 06, 2011 11:37 am

### 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

plamplam
Experienced poster

Posts: 151
Joined: Fri May 06, 2011 11:37 am

### Re: 11752 - The Super Powers

For check Overflow
You can use
Code: Select all
`int bit = 64;int power= ceil(bit  / (log(powerBase)/log(2)));`

Example:
1. If powerBase=3 then power=41 (i.e. the maximum power of 3 is 40, 3^40 < 2^64-1(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^64-1(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

outsbook
New poster

Posts: 26
Joined: Fri Oct 28, 2011 2:42 am