10270 - Bigger Square Please...

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Magus
New poster
Posts: 5
Joined: Thu May 09, 2002 9:34 am

10270 - Bigger Square Please...

Post by Magus »

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

thanx in advance

Magus

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

And when will you ask for the even cases? ;-)

Magus
New poster
Posts: 5
Joined: Thu May 09, 2002 9:34 am

Post by 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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by 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
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi »

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...
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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

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

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi »

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

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

10270 - Bigger Squares Please

Post by 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
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

Algorithm

Post by 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
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

Post by 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
New poster
Posts: 4
Joined: Wed Oct 22, 2003 9:11 pm

why primes only?

Post by 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
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

Re: why primes only?

Post by Algoritmo »

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

dieter
New poster
Posts: 2
Joined: Tue Mar 16, 2004 8:08 am

Post by 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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS »

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

--
DJWS, a newbie in programming :wink:

Post Reply

Return to “Volume 102 (10200-10299)”