10270  Bigger Square Please...
Moderator: Board moderators
10270  Bigger Square Please...
Can someone send a list of number of squares for all N=3, 5, 7, ...,49 ?
thanx in advance
Magus
thanx in advance
Magus

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
I just want to know what is compared by the judge, and how ...
With the answer that my solution didn't solve the problem
I have a little chance to findout where is the difference and
where is the bug.
If judge check the equal number of squares there is a possibility
that someone can give solution with less number of squares,
or the same but with different coverage...
I just want to get more information about my solution.
If I just know for which N my program gives wrong solution I could
analyse it and fix the bug ....
Magus
With the answer that my solution didn't solve the problem
I have a little chance to findout where is the difference and
where is the bug.
If judge check the equal number of squares there is a possibility
that someone can give solution with less number of squares,
or the same but with different coverage...
I just want to get more information about my solution.
If I just know for which N my program gives wrong solution I could
analyse it and fix the bug ....
Magus

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
I've spoken with the problem setter, and he told me that if the problem solver give a better solution, the judge accept it. He tested it with backtrack for the rectangles n<40, but I'm quite sure, that our algoritm is good, hovewer I can't porove it. You shouldn't care about the different coverage too, of course.Magus wrote:I just want to know what is compared by the judge, and how ...
If judge check the equal number of squares there is a possibility
that someone can give solution with less number of squares,
or the same but with different coverage...

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
Enter "4,6,4,8,4,9,4" here to get some info:
http://www.research.att.com/~njas/sequences/
http://www.research.att.com/~njas/sequences/

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm
10270  Bigger Squares Please
How do we prune the search tree enough so it will run in time? my DFS algorithm with some backtracking and a optimized maximum of 20 is still too slow for prime cases!
Algorithm
I understand the idea of backtracking for this problem, in general. However, I am having trouble deciding whether I should use the size of the squares as my "nodes", or the rows, or both...
I don't see how to use DP with this problem. Is there how?
I can try backtracking, what could take long, but I think it would take less than 10 sec, because there are only 15 prime numbers, from 2 to 50.
But there is one thing that disturbs me: How can many people have given solutions that take 0 sec and 000 millisec ? Maybe they have precalculated solutions for the prime numbers, but even then 0 millisecs is too fast...
I'm trying to find a logic in those solutions for prime numbers. First I need to generate some of them manually. I created solutions for most of the prime numbers, but I am not quite sure if all of my solutions really used the mininum number of squares possible. Can anyone check if my conclusions below are correct and continue the sequence of numbers for me ?
Prime Number 2  4 Squares
Prime Number 3  6 Squares
Prime Number 5  8 Squares
Prime Number 7  9 Squares
Prime Number 11  11 Squares
Prime Number 13  12 Squares
Prime Number 17  13 Squares
Prime Number 19  13 Squares
Prime Number 23  14 Squares
Prime Number 37  18 Squares?
The other prime numbers are: 29 31 41 43 47
I can try backtracking, what could take long, but I think it would take less than 10 sec, because there are only 15 prime numbers, from 2 to 50.
But there is one thing that disturbs me: How can many people have given solutions that take 0 sec and 000 millisec ? Maybe they have precalculated solutions for the prime numbers, but even then 0 millisecs is too fast...
I'm trying to find a logic in those solutions for prime numbers. First I need to generate some of them manually. I created solutions for most of the prime numbers, but I am not quite sure if all of my solutions really used the mininum number of squares possible. Can anyone check if my conclusions below are correct and continue the sequence of numbers for me ?
Prime Number 2  4 Squares
Prime Number 3  6 Squares
Prime Number 5  8 Squares
Prime Number 7  9 Squares
Prime Number 11  11 Squares
Prime Number 13  12 Squares
Prime Number 17  13 Squares
Prime Number 19  13 Squares
Prime Number 23  14 Squares
Prime Number 37  18 Squares?
The other prime numbers are: 29 31 41 43 47

 New poster
 Posts: 4
 Joined: Wed Oct 22, 2003 9:11 pm
why primes only?
why are you interested in primes only?
for even numbers, > ok, can be done with 4 squares
what about 15 for example? it is odd and not prime, why is it easier than 3, 5 or any other prime number?
for even numbers, > ok, can be done with 4 squares
what about 15 for example? it is odd and not prime, why is it easier than 3, 5 or any other prime number?
Re: why primes only?
Number 15 is not prime, so to get the minimum number of squares, you must use same solution you would use for number 3 (it's smallest prime factor) and multiply the size of each square by 5 (15/3 = 5).chervensky wrote:why are you interested in primes only?
for even numbers, > ok, can be done with 4 squares
what about 15 for example? it is odd and not prime, why is it easier than 3, 5 or any other prime number?
For number 3 you would use a square of size 2 and 5 squares of size 1.
For number 15 you would use a square of size 10 and 5 squares of size 5.
Note that for any two prime numbers P1 and P2, if P2 > P1, then certainly the minimum number of squares P2 requires is greater or equal than the minimum number of squares that P1 requires.
Thus, you do only have to compute solutions of prime numbers.
The table in http://joachim.wulff.net/valladolid/difficult.html shows this problem is part of the 10% most difficult ones.
I solve 4 problems per day, then I expend 4 days stuck in a single problem. But I think I'm doing well... ID 37180
These are my output:
Prime Number 2  4 Squares
Prime Number 3  6 Squares
Prime Number 5  8 Squares
Prime Number 7  9 Squares
Prime Number 11  11 Squares
Prime Number 13  11 Squares
Prime Number 17  12 Squares
Prime Number 19  13 Squares
Prime Number 23  13 Squares
Prime Number 29  14 Squares
Prime Number 31  15 Squares
Prime Number 37  15 Squares
Prime Number 41  16 Squares
Prime Number 43  16 Squares
Prime Number 47  16 Squares
I am not sure if they are optimal, but my precalculate code gets AC.
I hope it will be helpful
Prime Number 2  4 Squares
Prime Number 3  6 Squares
Prime Number 5  8 Squares
Prime Number 7  9 Squares
Prime Number 11  11 Squares
Prime Number 13  11 Squares
Prime Number 17  12 Squares
Prime Number 19  13 Squares
Prime Number 23  13 Squares
Prime Number 29  14 Squares
Prime Number 31  15 Squares
Prime Number 37  15 Squares
Prime Number 41  16 Squares
Prime Number 43  16 Squares
Prime Number 47  16 Squares
I am not sure if they are optimal, but my precalculate code gets AC.
I hope it will be helpful

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Hm, for 41 the answer is 15 squares:
I guess the judge's solution is too mild.
Code: Select all
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAACCCDDDDEEEEEEEEEEE
AAAAAAAAAAAAAAAAAAAAAAACCCDDDDEEEEEEEEEEE
AAAAAAAAAAAAAAAAAAAAAAACCCDDDDEEEEEEEEEEE
AAAAAAAAAAAAAAAAAAAAAAAFFGDDDDEEEEEEEEEEE
AAAAAAAAAAAAAAAAAAAAAAAFFHHHHHEEEEEEEEEEE
IIIIIIIIIIIIIIIIIIJJJJJJJHHHHHEEEEEEEEEEE
IIIIIIIIIIIIIIIIIIJJJJJJJHHHHHEEEEEEEEEEE
IIIIIIIIIIIIIIIIIIJJJJJJJHHHHHEEEEEEEEEEE
IIIIIIIIIIIIIIIIIIJJJJJJJHHHHHEEEEEEEEEEE
IIIIIIIIIIIIIIIIIIJJJJJJJKKKLLEEEEEEEEEEE
IIIIIIIIIIIIIIIIIIJJJJJJJKKKLLEEEEEEEEEEE
IIIIIIIIIIIIIIIIIIJJJJJJJKKKMNNNNNNNNNNNN
IIIIIIIIIIIIIIIIIIOOOOOOOOOOONNNNNNNNNNNN
IIIIIIIIIIIIIIIIIIOOOOOOOOOOONNNNNNNNNNNN
IIIIIIIIIIIIIIIIIIOOOOOOOOOOONNNNNNNNNNNN
IIIIIIIIIIIIIIIIIIOOOOOOOOOOONNNNNNNNNNNN
IIIIIIIIIIIIIIIIIIOOOOOOOOOOONNNNNNNNNNNN
IIIIIIIIIIIIIIIIIIOOOOOOOOOOONNNNNNNNNNNN
IIIIIIIIIIIIIIIIIIOOOOOOOOOOONNNNNNNNNNNN
IIIIIIIIIIIIIIIIIIOOOOOOOOOOONNNNNNNNNNNN
IIIIIIIIIIIIIIIIIIOOOOOOOOOOONNNNNNNNNNNN
IIIIIIIIIIIIIIIIIIOOOOOOOOOOONNNNNNNNNNNN
IIIIIIIIIIIIIIIIIIOOOOOOOOOOONNNNNNNNNNNN