10083 - Division

[Shahab]

I have no idea how to solve the problem 10083 with such big numbers, can you share your ideas with me?

[bugzpodder]

Hello,

I have tried almost (you'll see why in a sec) every optimization i could think of but still got TLE. specifically, I tried:
1. check for a%b!=0 or t=1 or a/b*log10(t)>=99 all of which leads to not an integer
2. check a=0 which gives 0
3. i optimized my exponent method to use a binary search type algorithm where i use something like t^a=(t^(a/2))^2 if a is even, and (t^(a/2))^2*t if a is odd.
4. i computed t^b, then use t^b to compute t^a for optimization

i think if you pass #1, then you are guanrenteed to have an integer result that is less than 100 digits, which must be outputted.

so why am i getting TLE? i could only think of two possibilities: either i got an infinite loop in there somewhere, or that my BigInt methods are way too slow. anyone got any suggestions?

Thanks,

Bugz

[nikhil]

10083
what is the idea beeeeeeeee
i can think out none
can Y help me?????

[zoranh]

I've got TLE as well, and here's what I did:

1. checked for special cases (b < a, b = 0, a = 0 -- although problem text says POSITIVE integers --, t = 1) - in each of these cases, result is either integer 0, or is not an integer
2. checked whether (a - b) * log10(t) > 99 - in this case result is has more than 99 digits
3. in other cases, used fastexp to calculate t^a and t^b:
M^N=(M^(N/2)) ^ 2 when N is even
M^N=M * (M^((N-1)/2))^2 when N is odd
After that, just divided big numbers, and got TLE.

However, when I removed division from step #3, I got WA (expected) with time = 0.002, which means that all operations except big number division yield zero time. So, what I'm going to do now is to optimize division as much as I can, as all other operations seem not to be complex at all.

[zoranh]

Well, I finally got it AC in only 0.002 sec, without use of big number division.

To solve the problem, you got to transform the expression to the form:
D(t, a, b) = sum(i=0, a/b - 1) (t^b)^i, where a%b=0

This sum can be further solved recursively:
D(t, a, b) = f(t^b, a/b)
f(x, 1) = 1
f(x, 2k) = (1 + x)*f(x^2, k), k = 1, 2, 3, ...
f(x, 2k + 1) = 1 + x*(1+x)*f(x^2, k), k = 1, 2, 3, ...

Special cases are (test in this particular order):
1. a=b => result=1
2. b=0 => not an integer...
3. a=0 => result=0
4. a%b != 0 => not an integer...
5. t=1 => not an integer...
6. (a - b) * log10(t) > 99 => not an integer...

If none of these conditions is met, then result is an integer with less than 100 digits, and then algorithm above should be used to calculate the result.

[bugzpodder]

hmmmmmmmmmmmm....
I followed your advice and still got a TLE. its either an infinite loop or my bigInt implementation is too slow then...

[bugzpodder]

Okay, I am asking about 10083 in UVA...
This is a Waterloo local contest question, and their official solution is available on the web, making use of Java BigInt class.

I implemented the exact same way as the official solution did, except using my own big Integer class written in C++ STL (strings)

unfortunately my solution runs way over 10 seconds. I see some people got 0.000 seconds... thats a pretty huge difference...

I only used multiplication and addition for this problem, with the classical implementation (how you would do multiplication/addition by hand). and my BigInt class is pretty correct considering i have used it in about 30 other UVA problems (but I usually see about .5 second difference, not 10)

so does anyone have any suggestions for me?

[Andrey Mokhov]

Hi!

I remember to have the same problem when I tried to get AC on the problem. But then I realized that the problem was not in the algo of addition and/or multiplication. The bug was that there are test cases when you need to add lots of equal numbers and you shouldn't do that. You should get the answer another way in such cases.

Hope it helps.

Bye.
Andrey.

[da0321]

i use zoranh's algorithm, but i have no idea why i always got WA??

Code: Select all

#include<iostream>
#include<cmath>

#define digitMax 101

using std::cin;
using std::cout;
using std::endl;

int main(){
	int t, a, b;
	int ans[digitMax], divisor[digitMax], tmp[digitMax];
	int i, j, k, count, bit;
	
	while(cin>>t>>a>>b){
		if(a==b){
			cout<<"("<<t<<"^"<<a<<"-1)/("<<t<<"^"<<b<<"-1) 1"<<endl;
			continue;
		}
		else if(a==0){
            cout<<"("<<t<<"^"<<a<<"-1)/("<<t<<"^"<<b<<"-1) 0"<<endl;
            continue;
		}
		else if(b==0 || a%b!=0 || t==1 || (a-b)*log10(t)>99){
            cout<<"("<<t<<"^"<<a<<"-1)/("<<t<<"^"<<b<<"-1) is not an integer with less than 100 digits."<<endl;
            continue;
		}
		
		
		for(i=0; i<digitMax; ++i){
			divisor[i] = 0;
			tmp[i] = 0;
		}
		count = 1;
		divisor[0] = 1;
		for(i=0; i<b; ++i){
			for(j=0; j<=count; ++j){
				divisor[j] *= t;
				if(j>0 && divisor[j-1]>9){
					divisor[j] += divisor[j-1]/10;
					divisor[j-1] %= 10;
					if(j==count){
						++count;
					}
				}
			}
		}
		
		ans[0] = 1;
		bit = 1;
		for(k=0; k<a/b-1; ++k){
			for(j=0; j<count; ++j){
				for(i=0; i<bit; ++i){
					tmp[i+j] += ans[i]*divisor[j];
				}
			}
			tmp[0] += 1;
			bit += count-1;
			for(i=1; i<=bit; ++i){
				if(tmp[i-1]>9){
					tmp[i] += tmp[i-1]/10;
					tmp[i-1] %= 10;
					if(i==bit){
						++bit;
					}
				}
				ans[i-1] = tmp[i-1];
				tmp[i-1] = 0;
			}
		}
		
        cout<<"("<<t<<"^"<<a<<"-1)/("<<t<<"^"<<b<<"-1) ";
		for(i=bit-1; i>=0; --i){
			cout<<ans[i];
		}
		cout<<endl;
	}
	return 0;
}

[fh]

zoranh's order is not correct.
The first thing to check should be : if the denominator is zero (t == 1).
There is no test case where t,a,b is less than 1, so no need to check for a == 0 or b == 0.

[Ahmad]

it would be great if zoranh (or anyone) helped us by the Mathematical principle behind this conditions to check .... this is why we solve such problems i guess .. to learn

[predicate]

I was able to understand all the other conditions except these two :

• if ((a-b)log10(t) + 1 >= 100) -> not an integer
• if (a % b != 0) -> not an integer

can someone please give me mathematical proofs as to why the above two conditions are true.

[Muftee_Ruet]

if (a==b) result is 1.

if(t==1 || a<b) result is not an integer;

if(a>b) {

check numberOfDigits is less than 100 using logarithm

else

not an integer less than 100 digits;

}