Friday, December 28, 2012

USACO - Packing Rectangles

After reading the problem statement I noticed the number of rectangles and their length and widths, as they are small enough to check all the combinations, 4! * 2^4, all permutations and each permutation you decide which rectangles to rotate. This would be enough, each time you check all the 6 layouts to put the rectangles, and find the minimum area.
I approached a little different, in a worse running time, I checked each possible enclosing rectangle X*Y, X=1...200, Y=1...200, so Order of this would be O(200 * 200 * 4! * 2^4) which is fast enough to pass the tests. For each Rectangle I check all the 4! * 2^4 possible ways to put the rectangles, and see whether I can put all the rectangles in that enclosing Rectangle or not, if yes, then I presume this rectangle would be an answer, then between all these rectangles I find the answer.

No comments:

Post a Comment

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...