## "Mondriaan's Dream" made me crazy

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Tourskey_911
New poster
Posts: 8
Joined: Sat Jun 12, 2004 4:12 am

### "Mondriaan's Dream" made me crazy

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

gawry
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 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.

Hedge
New poster
Posts: 11
Joined: Thu Jul 29, 2004 8:59 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.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
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.)
JongMan @ Yonsei