Page 1 of 1

10083 - Division

Posted: Sun Nov 10, 2002 2:25 pm
by Shahab
I have no idea how to solve the problem 10083 with such big numbers, can you share your ideas with me?

10083 - Division (TLE)

Posted: Sat Jul 12, 2003 3:16 am
by 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

10083

Posted: Thu Oct 09, 2003 2:10 am
by nikhil
10083
what is the idea beeeeeeeee
i can think out none
can Y help me?????

Posted: Wed Nov 26, 2003 7:35 pm
by 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.

Posted: Thu Nov 27, 2003 12:41 pm
by 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.

Posted: Mon Feb 16, 2004 11:04 pm
by bugzpodder
hmmmmmmmmmmmm....
I followed your advice and still got a TLE. its either an infinite loop or my bigInt implementation is too slow then...

BigInteger (10083 Division)

Posted: Sat Sep 11, 2004 1:19 am
by 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?

Posted: Mon Sep 13, 2004 8:11 am
by 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. :roll:

Bye.
Andrey.

Re: 10083 - Division

Posted: Sat Mar 05, 2011 7:08 pm
by 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;
}

Re: 10083 - Division

Posted: Fri May 20, 2011 12:06 pm
by 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.

Re: 10083 - Division

Posted: Sun Jul 03, 2011 5:19 pm
by 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 :)

Re: 10083 - Division

Posted: Mon May 04, 2015 4:21 pm
by 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.

Re: 10083 - Division

Posted: Fri Oct 23, 2015 10:25 am
by 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;

}