138 - Street Numbers

[Master]

Yes i also do the same and got AC

[Rav]

hello
i'm angry beacouse i thought about alghoritm and i discovered this
[cpp]
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int main()
{
int wsk=0,s=2;
double pier;

while (wsk<10)
{
using ::sqrt;
pier=sqrt(2*s*s+1);
if (pier==(int)(pier))
{
printf("%10Ld%10Ld\n",(int)(pier)*s,2*s*s);
++wsk;
}
pier=sqrt(2*s*s-1);
if (pier==(int)(pier))
{
printf("%10Ld%10Ld\n",(int)(pier)*s,2*s*s-1);
++wsk;
}
++s;
}
}
[/cpp]

it works in 0.004 s. but judge gives me WA . Why ?. I don't want use precalc beacuse i think this is not fair. Please help.

[Larry]

Can someone explain the Pell's Formula solution?

[Joseph Kurniawan]

Well, I think for this one, all you have to do is simply to check for a certain sum of houses n whether:

n*(n+1)/2 is a square number or not (if the square root of the result is a positive round number)

If you check the value n starting from 8 until the tenth n is found, it will take for about 3 min in my PC(166 MHz).
And from my observation, the number n is increasing by the factor of 5,........

[Master]

I use pre-calculation and then just print that .

[Joseph Kurniawan]

Of course if you use precalc like Master, you'll get AC in no time.
But what I'm trying to say here is how to make an algo that's fast enough.
My code ran in 17 ms (0.017 sec) in Pentium 4 (1.7 GHz).
Is there any algo that can run under 1 milisec? (0.000...... sec) so in the status, the CPU time will be 0:00.000

[Ryan Pai]

I'll assume that you realize that this problem is equivalent to finding a pair (k,n) such that 2*k^2 = n(n+1). Once you have this the obvious solution is to just iterate through values of n (or of k) and solve for the other, checking to see if it is an integer. Of course it's equally obvious that this method will time out.

But lets note something about the quantity n(n+1). It is equal to twice a square, so in its prime factorization the exponents will all be even (except the exponent of 2). Also note that if a prime divides n, then it does not divide n+1. Thus every exponent in the prime factorization of n must be even (except maybe 2). By this you only need to check n's which are either squares or two times a square. This speeds up the algorithm considerably enabling the solution to be calculated within the time limit.

[Ryan Pai]

I'll assume that you realize that this problem is equivalent to finding a pair (k,n) such that 2*k^2 = n(n+1). Once you have this the obvious solution is to just iterate through values of n (or of k) and solve for the other, checking to see if it is an integer. Of course it's equally obvious that this method will time out.

But lets note something about the quantity n(n+1). It is equal to twice a square, so in its prime factorization the exponents will all be even (except the exponent of 2). Also note that if a prime divides n, then it does not divide n+1. Thus every exponent in the prime factorization of n must be even (except maybe 2). By this you only need to check n's which are either squares or two times a square. This speeds up the algorithm considerably enabling the solution to be calculated within the time limit.

[Julien Cornebise]

Hi

I can't see how the Pell's Equation, as defined in
http://mathworld.wolfram.com/PellEquation.html
can help solve this problem.
I agree that
k^2 = n(n+1)/2
for all (k, n) solutions, but how can Pell's Equations do help please ?

[epsilon0]

here are a few hints:

1] the sum of all integers from 1 to n is n * (n+1) / 2

2] n and n + 1 don't have any common divisor (other than 1).

3] look at the first two couples:

6 8
35 49

6 = 2 * 3
and 8 = 2 * 2^2, 8+1 = 9 = 3^2
in other words 8 * 9 / 2 = 6^2

35 = 5 * 7
and 49 = 7^2, 49+1 = 50 = 2 * 5^2
in other words 49 * 50 / 2 = 35^2

if your smart, then your bruteforce will be fast, because you look for numbers with very special properties...

[Julien Cornebise]

here are a few hints:

1] the sum of all integers from 1 to n is n * (n+1) / 2

2] n and n + 1 don't have any common divisor (other than 1).

3] look at the first two couples:

Hi !
First, thanks for your answer. I got AC a few days ago, with slicker bruteforce than the basis, but kinda brute anyway.
I already tried a brute force by testing the condiition of m^2 = n*(n+1)/2, but alas, rounding errors got me out.
I can't figure how to use this trick without rounding errors. Or are there other properties that this one implies that makes the work int ?
I'm not satisfied by the way I solved the problem, so I'm really looking for an elegant answer....

[epsilon0]

here is my C code for this problem.
as you can see, it's quite short.
you will notice that you can improve it. obviously, the test if (!((int)xi % 2)) is useless if you replace j++ with j += 2 in the loop. the square of an odd number cannot be even!!!

also, my mate Olivier Bery has a solution for this problem without any kind of brute force! he found an empirical relation between the numbers of the line n and n + 1.
the only problem is that we are both clueless about why this formula gives the right answer!! it's magic!
i hope Olivier will read this and post his solution, so that someone can try to demonstrate why it works.


[c]/* @JUDGE_ID: ******* 138 C Street Numbers */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MIN(a,b) ((a)<(b)?(a):(b))

int main()
{
unsigned int n = 0;
double i,j,xi,xp, tmp;
for(j = 2; n < 10; j++)
{
xi = j * j;
if (!((int)xi % 2))
continue;
xp = xi - 1;
tmp = xp / 2;
i = floor(sqrt(tmp));
if (i * i == tmp)
{
printf("%10.0lf%10.0lf\n", i*j, xp);
n++;
}
xp = xi + 1;
tmp = xp / 2;
i = floor(sqrt(tmp));
if (i * i == tmp)
{
printf("%10.0lf%10.0lf\n", i*j, xi);
n++;
}
}
return EXIT_SUCCESS;
}
[/c]

[Julien Cornebise]

also, my mate Olivier Bery has a solution for this problem without any kind of brute force!

Well, I'll ask him tonight at dinner... The world is small ! He's my teammate ! And didn't even knew he had such a formula

[bery olivier]

Hi,

Sorry, I'm a bit late. But I got some problem to log in the board under linux.

That's right, I have a weird solution.
This is how it works :

The result is :
6| 8
35| 49
204| 288
1189| 1681
6930| 9800
40391| 57121
235416| 332928
1372105| 1940449
7997214| 11309768
46611179| 65918161
for the left colunm, the operation is (6*previous)-previous(2)
for instance, for the 3rd row, we have : (6*35)-6
The can suppose that the first number is 0 and the second is 1. So that, for the 1st column, we have : 6=(6*1)-0, then 35=(6*6)-1 etc.

for the second column, the operation is (6*previous)-previous(2)+2
So :
(6*1) -0+2 =8
(8*6)-1+2=49
(49*6)-8+2=288
(288*6)-49+2=1681 etc.

But I wasn't able to prove it, and I'm not sure it'll always work.
Maybe one of you can help me.


Thanks to Julien and epsilon witch helped me a lot during these years I was doing ACM. Moreover, they have a beatifull mind.

[Farid Ahmadov]

Here is a part of my AC code:

Code: Select all

begin
  x:=x*6-a[i-2];
  a[i]:=x;
  s:=s+a[i-1];
  writeln(x:10,x+2*s:10);
end;

That is all. I thought if you talk about formulas or something like, here is my formula. Hope it helps to get that works.