3 ms·
That'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 ve
by itomatik 13y ago
That'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 13y 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 13y agonice! makes sense. I real life 'done is often better than perfect' =)