Page 1 of 2

### 10790 - How Many Points of Intersection?

Posted: Mon Dec 27, 2004 11:13 am
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
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
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
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
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
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
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
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 Posted: Thu Dec 30, 2004 4:37 pm
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
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
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
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... My int64 solution - 0.082 sec
My extended solution - 0.023 sec!
and avg. C/C++ solutions - 0.006 sec... Posted: Sun Jan 09, 2005 5:11 am
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. Posted: Fri Feb 18, 2005 8:31 pm
What will be the output for 20000 20000 input.

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