10270 - Bigger Square Please...

[Magus]

Can someone send a list of number of squares for all N=3, 5, 7, ...,49 ?

thanx in advance

Magus

[Stefan Pochmann]

And when will you ask for the even cases?

[Magus]

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

[Stefan Pochmann]

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

[ftomi]

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

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.

[Stefan Pochmann]

Enter "4,6,4,8,4,9,4" here to get some info:
http://www.research.att.com/~njas/sequences/

[ftomi]

It's funny! Try this: 3, 3, 5, 4, 4, 3, 5, 5!

[bugzpodder]

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!

[rbuchan]

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

[Algoritmo]

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

[chervensky]

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?

[Algoritmo]

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?

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

[dieter]

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

[little joey]

Hm, for 41 the answer is 15 squares:

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

I guess the judge's solution is too mild.

[DJWS]

I have no idea how to reduce time.
Could anyone help?
I have almost stuck in the prob.

--
DJWS, a newbie in programming