Page 1 of 2

10790 - How Many Points of Intersection?

Posted: Mon Dec 27, 2004 11:13 am
by soyoja
It's so easy problem, I just use loop calculation.

But my solution received TLE by OJ system.

Maybe OJ system use so many test case.

Is there any tips for calculate solution more quickly?

Code: Select all

for( i = 1; i <= a - 1; i++ )
	for( j = b - 1; j >= 1; j-- )
		sum += (i * j);
// a, b is input. 

Re: 10790 Time Limit Exceed

Posted: Mon Dec 27, 2004 11:20 am
by ..
soyoja wrote:

Code: Select all

for( i = 1; i <= a - 1; i++ )
	for( j = b - 1; j >= 1; j-- )
		sum += (i * j);
// a, b is input. 
I am not sure if your formula is correct.
But it is obvious that, you can simplify it to

Code: Select all

for( i = 1; i <= a - 1; i++ )
     sum += i * sum(1,2, ..., b-1);
// a, b is input. 
When I solve the problem, I first made a O(ab) solution, then simplify to O(b) and at last to O(1).

Posted: Tue Dec 28, 2004 2:39 am
by soyoja
Wow! Thank you guy. ^^

Your suggestion makes my calculation's complexity

O(N^2) to O(N), and I got accepted!!

PS) My formula was correct ^^. haha.

Thank you again!

Posted: Tue Dec 28, 2004 5:08 am
by Antonio Ocampo
In fact, a simple formula exists. Just think about it, because in this way your solution becomes in a O(1) solution.

Best regards

Posted: Thu Dec 30, 2004 10:08 am
by anupam
soyoja, it's a two line program with O(1) soln. try the same way .. simplified your equation. Use long long ofcourse

Posted: Thu Dec 30, 2004 11:18 am
by little joey
Anupam, what's wrong with you? Many times you only repeat what others said before. Don't you read the thread before posting your comment?

Posted: Thu Dec 30, 2004 1:02 pm
by anupam
OOPS! little joye sorry! I just solved the program today. using double I got WA and using long long I got ac. Is there any reason for it? And, can we use I64 data type (I have used never at uva). Is it allowed now?

Posted: Thu Dec 30, 2004 4:33 pm
by prince56k
the max value of a,b is 20000.
i don't know your formula but for 20000 input the vaule should be out of double/long double range. u can try :lol:

Posted: Thu Dec 30, 2004 4:37 pm
by anupam
May I give the formula here. it is a multiplication of four term and then a division by 4.00 and i used .0lf to print the value.

Posted: Thu Dec 30, 2004 6:31 pm
by abishek
the final answer is clearly an integer, so using double for this some is a criminal offence:-) and hence was expected to get WA.
my experience tells me never to use any doubles if the input and output excepted in a program are integers.

Posted: Thu Dec 30, 2004 6:40 pm
by Larry
double doesn't have the same amount of precision as long long. You might get away with it sometimes, when the precision isn't needed, or if it's a multiple of 2. You might be able to get away with long double, but why? Use what gives you the most precise answer..

It's trivial to derive a O(1) solution, after given the for loops in the first post.. yes, everyone else already mentioned this, no need to add that in..

Posted: Fri Dec 31, 2004 4:07 am
by Observer
Well I agree that if you use C/C++ you should use long long in this kind of questions. However, as a Pascal programmer, I myself often use extended (equivalent to long double in C/C++)! The reason is that int64 is VERY slow in Pascal, at least 4 times slower than extended. And we know that extended gives around 18 digits of precision... :wink:

As in this task,
My int64 solution - 0.082 sec
My extended solution - 0.023 sec!
and avg. C/C++ solutions - 0.006 sec... :P

Posted: Sun Jan 09, 2005 5:11 am
by cytmike
The formula is very trivial as long as you know how to sum up Arithmetic Progression.
Just list all the small cases of P(m,n) and you can find out the formula. :lol:

Posted: Fri Feb 18, 2005 8:31 pm
by ibrahim
What will be the output for 20000 20000 input.

Posted: Sat Feb 19, 2005 8:45 am
by shamim
ibrahim wrote:What will be the output for 20000 20000 input.
39996000100000000