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 pre-calculated 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 pre-calculated 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 pre-calculate 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 pre-calculate 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