## 10790 - How Many Points of Intersection?

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

Moderator: Board moderators

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

### 10790 - How Many Points of Intersection?

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.
``````
I love Problem Solving!!!

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

### Re: 10790 Time Limit Exceed

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).
My signature:
• Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
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!
I love Problem Solving!!!

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
In fact, a simple formula exists. Just think about it, because in this way your solution becomes in a O(1) solution.

Best regards

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
soyoja, it's a two line program with O(1) soln. try the same way .. simplified your equation. Use long long ofcourse
"Everything should be made simple, but not always simpler"

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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?

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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?
"Everything should be made simple, but not always simpler"

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
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.
"Everything should be made simple, but not always simpler"

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
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..

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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...

As in this task,
My int64 solution - 0.082 sec
My extended solution - 0.023 sec!
and avg. C/C++ solutions - 0.006 sec...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
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.
Impossible is Nothing.

ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:
What will be the output for 20000 20000 input.

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
ibrahim wrote:What will be the output for 20000 20000 input.
39996000100000000
Last edited by shamim on Sat Feb 19, 2005 3:57 pm, edited 1 time in total.