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?

Post by soyoja » 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. 
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

Post by .. » 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).
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:

Post by soyoja » 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!
I love Problem Solving!!! :) :) :)

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » 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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » 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
"Everything should be made simple, but not always simpler"

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » 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?

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » 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?
"Everything should be made simple, but not always simpler"

prince56k
New poster
Posts: 33
Joined: Fri Dec 12, 2003 10:32 pm
Location: BANGLADESH

Post by prince56k » 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 :lol:

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » 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.
"Everything should be made simple, but not always simpler"

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » 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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » 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..

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » 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... :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
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » 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. :lol:
Impossible is Nothing.

User avatar
ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim » Fri Feb 18, 2005 8:31 pm

What will be the output for 20000 20000 input.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Feb 19, 2005 8:45 am

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.

Post Reply

Return to “Volume 107 (10700-10799)”