3 ms·
combinatorics as the whole is quite interesting. i've done an implementation that arranges different fixed-dimension flooring panels into rooms of different siz
by leeoniya 14y ago
combinatorics as the whole is quite interesting. i've done an implementation that arranges different fixed-dimension flooring panels into rooms of different sizes.
- itomatik 14y agoThat's pretty cool. It's actually non-trivial problem. Did you write some sort smart bruteforce? Or you had figured some DP approach? There was a simplified version of it on IOI 2004 (http://olympiads.win.tue.nl/ioi/ioi2004/contest/day2/phidias.pdf http://olympiads.win.tue.nl/ioi/ioi2004/contest/day2/phidias...) which asked to cut the room by a series of horizontal and vertical cuts. At the end each of remainder blocks can either be fully covered by predefined set of fixed-dimension panels or thrown away. The problem asked to minimize what we throw away. It was solvable using DP due to the fact that cuts are always split the room into separate parts.
- leeoniya 14y agoit was not DP, but worked quite well, because some of the conditions were eased. the product quantity was unlimited, so as many products as needed could be used. we basically needed to fill the space with as few products (thus dimensionally larger) as possible to minimize the installation work. it ended up starting out greedy, taking large panels first and adaptively backtracking when the current size could not be placed. if by the end of the iteration we did not reach a minimum coverage area, we would backtrack and remove the last significant size panel and fill it with smaller ones. it didnt get us the "optimal" solution but it was fast and more than sufficient.
- itomatik 14y agonice! makes sense. I real life 'done is often better than perfect' =)