Page 1 of 1
"Mondriaan's Dream" made me crazy
Posted: Wed Jun 16, 2004 7:19 am
I met a problem yesterday,It seemed I can finish it ,but in the end,I had no way,can you give me some ideas?
Thank U ^_^
Posted: Wed Jun 16, 2004 6:13 pm
Maybe dynamic programming? For each 1<=i<=w and S - subset of fields in the ith column calculate number of different ways fields in the i-1 first columns AND S can be filled.
Posted: Tue Oct 19, 2004 8:32 pm
We had this problem at a local contest and we couldnt solve it in time. You can try a backtracking approach. But actually a friend of mine told me that there is even a closed formular for this problem.
Posted: Sat Nov 06, 2004 12:17 pm
You can solve the problem with dynamic programming, with an exponential space complexity of O(w*(2^h)) and time complexity like O(wh*2^h).
The key observation is when you are filling column #i, there are 2^h possibilities where a block spans from column #(i-1).
(Hmm, it's not easy to explain.. Maybe you can look at a similar problem posed at a TopCoder match. Which is more difficult, but has some solution disscussions. See SRM 209 CaseysArt.)