Page 1 of 1

"Mondriaan's Dream" made me crazy

Posted: Wed Jun 16, 2004 7:19 am
by Tourskey_911
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 ^_^

here

http://acm.zju.edu.cn/show_problem.php?pid=1100

Posted: Wed Jun 16, 2004 6:13 pm
by gawry
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
by Hedge
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
by Whinii F.
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.)