10083 - Division

All about problems in Volume 100. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Shahab
New poster
Posts: 24
Joined: Sun Nov 10, 2002 2:17 pm

10083 - Division

Post by Shahab » Sun Nov 10, 2002 2:25 pm

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

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

10083 - Division (TLE)

Post by bugzpodder » Sat Jul 12, 2003 3:16 am

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
New poster
Posts: 11
Joined: Wed Oct 08, 2003 1:37 pm

10083

Post by nikhil » Thu Oct 09, 2003 2:10 am

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

zoranh
New poster
Posts: 8
Joined: Wed Nov 26, 2003 7:23 pm

Post by zoranh » Wed Nov 26, 2003 7:35 pm

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
New poster
Posts: 8
Joined: Wed Nov 26, 2003 7:23 pm

Post by zoranh » Thu Nov 27, 2003 12:41 pm

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
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder » Mon Feb 16, 2004 11:04 pm

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

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

BigInteger (10083 Division)

Post by bugzpodder » Sat Sep 11, 2004 1:19 am

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
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Mon Sep 13, 2004 8:11 am

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.

da0321
New poster
Posts: 1
Joined: Sat Mar 05, 2011 7:03 pm

Re: 10083 - Division

Post by da0321 » Sat Mar 05, 2011 7:08 pm

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;
}

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Re: 10083 - Division

Post by fh » Fri May 20, 2011 12:06 pm

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.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

Ahmad
New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

Re: 10083 - Division

Post by Ahmad » Sun Jul 03, 2011 5:19 pm

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
New poster
Posts: 18
Joined: Tue Jun 17, 2014 9:32 pm
Location: Hyderabad, India

Re: 10083 - Division

Post by predicate » Mon May 04, 2015 4:21 pm

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
New poster
Posts: 10
Joined: Fri Sep 16, 2011 6:36 am

Re: 10083 - Division

Post by Muftee_Ruet » Fri Oct 23, 2015 10:25 am

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;

}

Post Reply

Return to “Volume 100 (10000-10099)”