maulik12's blog

Cutting a chocolate bar
By maulik12, history, 9 years ago, In English

I recently encountered this question from one of my friends. You are given an chocolate bar of size M*N. Also you are given an array of pieces to be cut. Example: If M- 3 and N = 4, the array that is given is : 1,2,3 and 6

We can divide the chocolate into such rectangular pieces of these sizes. Note that the sizes have to be rectangular.

Can we do this just by checking the sum and then see if the following constraints are satisfied:

  1. I am using just a verification that if the size to be cut(K) is odd, then the value of M or N has to be greater than or equal to K, then only we can cut it into (1 X K) or (K X 1).

I do not get whether this is an advanced problem or just some ad hoc problem. Please advice on how to solve the question and ask any queries.

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I also wasn't able to understand how DP works in this one. Please help us understand the solution to this problem.this is the link to the problem

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    That question is different. Let $$$dp_{i,j,k}$$$ denote the least cost to cut a chocolate of height $$$i$$$ and breadth $$$j$$$ into $$$k$$$ pieces.

    $$$dp_{i,j,k} = min(dp_{i-l, j, k-m} + dp_{l,j,m} + j^2, dp_{i,j-l, k-m}+ dp_{i,l,m} + i^2)$$$

    We are just checking each possible cut, and for each cut, we are checking the optimal way to divide the number of pieces obtained from both new pieces. $l$ and $$$m$$$ are iterator variables. This is $$$O(nm(n+m)k^2)$$$ with a small constant factor, so it should pass.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If somebody be so kind to give an hint for this problem, it is about chocolate bars, too. Thanks!

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    you can't immediately use grundy numbers, because the game isn't symmetric. But what if you rotated the boards $$$90^{\circ}$$$ each turn. Then the game is symmetric. Now you can precompute the answer for all states in $$$O(nm(n+m))$$$ using basic game theory. Just brute force each possible cut.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got stuck in cumputing the states. I think these are much more than n*m.

      Consider 500*500 board. First cut is possible on 249 positions, second on 249 positions, third on 123... etc.

      How would you store the state?

      → Reply