835

Adrian Kuegel · Post by **Adrian Kuegel** » Fri Jun 21, 2002 1:00 am

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 · Post by **xenon** » Fri Jun 21, 2002 2:42 am

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.

WhiteShadow · Post by **WhiteShadow** » Fri Jun 21, 2002 4:18 am

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!

xenon · Post by **xenon** » Fri Jun 21, 2002 10:48 am

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

Adrian Kuegel · Post by **Adrian Kuegel** » Fri Jun 21, 2002 6:23 pm

Ok, I have now solved the problem with some modifications in the backtracking process. Thanks for the hint, Pedro!

Stefan Pochmann · Post by **Stefan Pochmann** » Sun Jun 23, 2002 7:15 am

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

WhiteShadow · Post by **WhiteShadow** » Mon Jun 24, 2002 2:25 am

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)

Stefan Pochmann · Post by **Stefan Pochmann** » Mon Jun 24, 2002 3:05 am

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 · Post by **Picard** » Mon Jun 24, 2002 2:28 pm

i couldn't resist sending in a precalced version.

but a real algo below 2 seconds is impressive!

Stefan Pochmann · Post by **Stefan Pochmann** » Mon Jun 24, 2002 10:05 pm

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 · Post by **Picard** » Tue Jun 25, 2002 1:02 am

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 · Post by **garypanda** » Mon Jul 01, 2002 7:05 pm

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 · Post by **Ivan Golubev** » Mon Jul 01, 2002 7:19 pm

Check out second column: 02243. There cannot be leading zeroes, so this is a four-digit number not a five-digit one.

mmammel · Post by **mmammel** » Tue Sep 10, 2002 8:35 pm

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 · Post by **mmammel** » Tue Sep 10, 2002 9:18 pm

Nevermind...

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

OJ Board

835 - Square of Primes

835 - Square of Primes

some preliminary observations

Mail me if you want hints

Re: Mail me if you want hints

WA -- output format??

OK