10790 - How Many Points of Intersection?

[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.


[..]

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).

[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!

[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

[anupam]

soyoja, it's a two line program with O(1) soln. try the same way .. simplified your equation. Use long long ofcourse

[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?

[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?

[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

[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.

[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.

[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..

[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...

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

[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.

[ibrahim]

What will be the output for 20000 20000 input.

[shamim]

What will be the output for 20000 20000 input.

39996000100000000