Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 8:00 (UTC) due to technical maintenance. ×

servesh196's blog

By servesh196, history, 6 years ago, In English

I started solving standard DP problem. I found this problem here is the link, https://www.geeksforgeeks.org/dynamic-programming-set-21-box-stacking-problem/ . I have already solved this problem. Now in this problem we have infinite instance of single box so we can use any rotation of a particular box. so, this problem with little variation what if we can use only one instance of box. How to solve this problem I tried to figure out solution myself but I am not getting the idea how to solve ??. Brute force solution won't work here complexity of brute force solution would be 4^n.

Each box can have six different rotation in which pair of two will have same base area so for each box we have total 3+1 choice 1 for not selecting particular box . so, complexity will be 4*4*…..n-times. I also tried the same way as standard problem can be solved with slight difference in implementation but I am getting wrong answer. I am not asking this question without trying enough. I have spent many days in this problem. I also tried to google if i can get any hint.

Any suggestion or hint would be helpful, Thank You.

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it