138 - Street Numbers

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

Moderator: Board moderators

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:
Yes i also do the same and got AC

Rav
New poster
Posts: 27
Joined: Sat Jun 14, 2003 1:00 pm
Location: Polska Wroc&#322;aw
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.
Rafał Sokołowski

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Can someone explain the Pell's Formula solution?

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
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
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:
I use pre-calculation and then just print that .

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
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
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

A simple property

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
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

A simple property

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
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

hints

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...
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Re: hints

epsilon0 wrote: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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
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]
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:
epsilon0 wrote: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
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:
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.
Not AC yet AC at last Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan
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.
_____________
NO sigNature