10270 - Bigger Square Please...
Posted: Thu May 09, 2002 3:44 pm
Can someone send a list of number of squares for all N=3, 5, 7, ...,49 ?
thanx in advance
Magus
thanx in advance
Magus
Page 1 of 2
Posted: Fri May 10, 2002 7:52 am
And when will you ask for the even cases?
Posted: Fri May 10, 2002 8:51 am
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
Posted: Fri May 10, 2002 9:28 am
Haha, I've just read the problem completely. The even cases are trivial, right? So basically you're asking people to give you the full solution? Sorry, haven't solved it yet, can't really help. But I'll take it home, think about it...
Posted: Fri May 10, 2002 8:32 pm
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...
Posted: Sat May 11, 2002 6:43 am
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/
Posted: Sat May 11, 2002 7:50 am
It's funny! Try this: 3, 3, 5, 4, 4, 3, 5, 5!
10270 - Bigger Squares Please
Posted: Mon Oct 06, 2003 10:27 pm
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
Posted: Sat Nov 01, 2003 6:53 pm
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...
Posted: Sat Nov 01, 2003 8:43 pm
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
why primes only?
Posted: Tue Dec 23, 2003 6:51 pm
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?
Posted: Tue Dec 23, 2003 9:39 pm
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.
Posted: Fri Apr 16, 2004 10:50 am
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
Posted: Fri Apr 16, 2004 2:22 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
Posted: Mon May 24, 2004 10:23 am
I have no idea how to reduce time.
Could anyone help?
I have almost stuck in the prob.
--
DJWS, a newbie in programming
Could anyone help?
I have almost stuck in the prob.
--
DJWS, a newbie in programming