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.)