## 835 - Square of Primes

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

Moderator: Board moderators

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

### 835 - Square of Primes

I have tried this problem, but the time limit is really hard. I build prefix trees for all possible sums and build the square with backtracking. I used the following rule:
First create a row, then seek a prime in the tree which begins with inserted values and create a column and so on. For example for the sample input I first create a row with a prime beginning with 1, then I create a column beginning with 1, then (after backtracking) I create a row beginning with 14, then a row beginning with 14...
My program solves the sample input quickly, but I tried also the input
23
1
and my program runs 30 seconds and creates 88 squares.
Does anyone know a better approach to this problem?

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

### some preliminary observations

I haven't solved it yet, but made some preliminary observations:

- all digits in the last column and last row should be odd; there are only 608 5-digit primes between 10000 and 99999 having all odd digits, out of a total of 8363; only considering these in the last two iteration-steps can bring down executiontimes considerably.

- the sum off the digits should be odd because of that. This roughly halves the number of precalculations (depending on your algorithm), and the number of primes that need to be considered in the first iteration-steps.

- you only have to look for squares where the prime in the first row is smaller or equal then/to the prime in the first column. The mirror from the upperleft/lowerright-diagonal is another solution (or the same). This roughly halves the number of calculations, but adds a sorting-step. Sorting is relatively cheap, when a maximum of order(100) squares will be found.

I hope this isn't too much of a spoiler (i think it's pretty obvious). If you think so, tell me, and I'll delete the message.

New poster
Posts: 10
Joined: Tue Jun 18, 2002 12:08 pm
Location: Portugal
Contact:

### Mail me if you want hints

Hi!

My program solves the "23 1" case in 4.23s on my AMD Athlon 700Mhz, giving 88 solutions (as your solution did), using gcc without optimization (if I use the option -O3 in the compiler the program takes 1.13s)

"23 3" is even a worst case (152 solutions) and my program takes 5.77s to do that (1.48s with compiler optimization)

I must confess my first approach was similar to yours, using the notion of prefix, and I needed some hints (this program has been studied by some people) to make an accpetable solution.
xenon wrote:- you only have to look for squares where the prime in the first row is smaller or equal then/to the prime in the first column. The mirror from the upperleft/lowerright-diagonal is another solution (or the same). This roughly halves the number of calculations, but adds a sorting-step. Sorting is relatively cheap, when a maximum of order(100) squares will be found.
Be careful with that!!!
Imagine input "13 1". Then this (the first square) will be one solution:

Code: Select all

``````12253              15313
54013              24223
32413    but       20443      is not valid because 31423=7*67*67 and so is not a prime
12433              51133
33331              33331
``````
Note that the problem states that "Both diagonals are read from left to right.", so 31423 is one of the diagonals. So, the mirror is not always a valid solution and we must calculate all combinations, right?

As I think this problem is very interesting, I will resist posting stronger hints here. But if you need any hints, just email me!
"Deep in the human unconscious is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic."

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland
You're absolutely right, WhiteShadow. I didn't notice that on first sight.
Now that I've been coding a little, I discovered that my observations are of little use. They could bring down calculating times, but not enough for a pure brute force attack to finish in time
I'm not through with this problem...

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Ok, I have now solved the problem with some modifications in the backtracking process. Thanks for the hint, Pedro!

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

### Re: Mail me if you want hints

WhiteShadow wrote: I must confess my first approach was similar to yours, using the notion of prefix, and I needed some hints (this program has been studied by some people) to make an accpetable solution.
Hmm, that sounds like if there's some mathematical insight behind it... My solution is just a brute force one, but it's still the fastest one so far (I need about a second for each of the cases 23/1 and 23/3, and on the judge it took about 3 seconds).

I just fooled around with my dummy account a bit and got down to 2.5 seconds...
WhiteShadow wrote: As I think this problem is very interesting, I will resist posting stronger hints here. But if you need any hints, just email me!
Yes, please. Now that I have one solution, I'd like to know more about the problem. Could you mail me what you got to pochmann@gmx.de? Thanks...

New poster
Posts: 10
Joined: Tue Jun 18, 2002 12:08 pm
Location: Portugal
Contact:
Well, you made me wanna look at the problem again, to optimize a little bit more, and now my solution is again the first one (it took 2.15 s on UVA judge). If you wanna exchange ideas, or just want to know what I did, mail me (pribeiro@dcc.online.pt)
"Deep in the human unconscious is a pervasive need for a logical universe that makes sense. But the real universe is always one step beyond logic."

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Ha! Not anymore! I took the lead again Unfortunately my program became bigger and uglier now. But beware: I could easily make it even bigger and uglier, and it would probably be even faster, too, harhar

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
i couldn't resist sending in a precalced version.
but a real algo below 2 seconds is impressive!

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
So how long would your non-precalced version run on the judge? Btw, please mark precalc solutions with a "precalc" comment, so that others don't waste time to search for the superior algorithm that doesn't exist. Well, I have to admit that I've just made up this rule for me (never thought about it before) and I'll follow it in the future.

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
My first version (which was used for precalcing) was very slow, but now i have made an optimized algo (to show that i can optimize too ).
Created a new dummy acount for the same purpose as you. As Locutus i've made it in 1.180 sec.
Next time i will indicate the precalced solution, but for this problem i couldn't reach 0.000 sec, so no modification possible.

garypanda
New poster
Posts: 1
Joined: Mon Jul 01, 2002 7:02 pm

### 835

anyone can tell me why
1 0 1 8 1
3 2 3 0 3
3 2 3 0 3
1 4 3 2 1
3 3 1 1 3
is not a solution for the sample input

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Check out second column: 02243. There cannot be leading zeroes, so this is a four-digit number not a five-digit one.

mmammel
New poster
Posts: 11
Joined: Fri Aug 23, 2002 9:42 pm
Location: MD, USA
Contact:

### WA -- output format??

I'm getting frustrated with this one...
I have it working well on my PC -- solves 23,3 in about 4s.
It generates 88 solutions for 23,1 and 152 for 23,3 which agrees with earlier posts. The output seems correct upon inspection.
I was unsure about "The solutions must be in ascending order" -- does that mean order by first row, then first column or by first row then second row? I tried both ways (my program generates by the first way but I suspect what is wanted is the second).
"The outputs of two consecutive cases will be separated by a blank line. "
So that is a second blank line after the last solution right?

It works fine for multiple inputs...does it matter if the program reads all input at the beginning or reads after outputting each set?

I've tried a bunch of formats and always WA. Does anyone want me to email my output for 23,3 (or other set) for checking?

Thanks,
Mark (msmammel@starpower.net)

mmammel
New poster
Posts: 11
Joined: Fri Aug 23, 2002 9:42 pm
Location: MD, USA
Contact:

### OK

Nevermind...
I found my mistake -- there was a little error in sorting that only occurred in one input, I finally found it.
-Mark