Hi, for the problem CHPUZZLE, what are some good high scoring approaches? In the contest what I did was,
Initialize a 0 matrix ‘M’.
For each piece ‘P’
a. take a pseudo-random pixel ‘r’ in ‘M’,
b. Check compatibility (No overlap and overflow) with ‘M’ for ‘p’ starting from ‘r’.
c. If compatible, Add ‘P’ to 'M’starting from ‘r’.
Compute score for the assignment. Repeat a fixed ‘K’ times and print Maximum matrix ‘M’.
I got ~40 points, but what are some high scoring approaches. Please help.
PS: Could not find editorial for this problem. I did go through highly scored codes, but too hard to understand approaches.
compute the minimum size rectangles of each part . Then sort them increasingly and place them
1)keep tham alligned to x axis .and calculate.
2)keep them alligned to y axis .and calulate
compute the maximum of these
this gives around 70
For I package of tests, I try to put puzzle which have best possible cover, with previously placed puzzle. This method work well for small fields.
II package is combining this above approach and following.
For big ones nice packing is out of considering. Time not aloud this type of commodity.
So I divide packaging in two phase:
Packing puzzle like this was rectangles, from left to right. Sorting puzzles in some way are show some improvement on score. Odd rows of puzzles I leveled by up edge (of first “rectangle” in this row) and even rows by down edge.
In empty space between placed puzzle, I try to put remaining puzzle.
For this two phases I examine various methods of filling. Best I reach is for firs phase: sort by height of puzzle, descending (big one first) and for phase 2 also try to put most valuable puzzle first (priority queue) and if it not possible, I discard it, and go for next one.