Lien's blog

How to solve this cutting cake problem ?

By Lien, 10 years ago, In English

Hi,

I am trying to solve this problem but it is hard to find a possible approach. Could somebody help me?

Problem:

Let you have a rectangle cake. You want to divide it to N people. All of them must eat all piece of the cake and they have equally area. What is the minimum number of parallel cut you need to take.

Example:

Divide the cake for 5 people you need at least 3 cut: 2 horizontal cuts the cake into 3 parts: 2/5 and 2/5 and 1/5. Then with 1 vertical cut, the cake is divided into 6 parts: 4 piece2 1/5 and 2 pieces 1/10. Join 2 pieces 1/10, you have divided the cake equally for 5 people.

There is no limitation for N in this problem. However, I hope someone can show me an approach for 1 <= N <= 100000.

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

»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I try to solve this problem ^^ if i wrong, dont laugh me :) We easy see that if n = 1 we dont need to cut and ans is 0. if n = 2 we need 1 cut. i call a[i] is the number of cut to make cake to i people. now if n is a odd number we need 1 cut to make the cake in 2 side (n-1)/n and 1/n. now we need to share (n-1)/n cake to n-1 people (n-1) now is even. we habe a[n] = a[n-1] + 1; if n is a even number, we need 1 cut to make the cake in 2 same side so a[n] = a[n/2] + 1;

Sorry for my bad English

It's code

http://pastebin.com/PFhgFgCT

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

    Sorry, I think you were misunderstood the problem. We can not move the cake while we are cutting so the equation: an = an / 2 + 1 is wrong.

    Example:

    N = 11 your program returned 5 but we need at least 6 cuts: 3 horizontal cuts divide the cake into 4 pieces: 4/11 4/11 2/11 and 1/11 then vertical cuts divide the cake into 16 pieces: 8 pieces 1/11, 4 pieces 1/22 and 4 pieces 1/44. There isn't any solution with less than 6 cuts.

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

      We don't need to move the cake to apply his solution because even if one cut made some extra unwanted cuts , we can just assume that the unwanted cut is not done.

      for example consider the case when N=3 , it's clear that the solution is to make two vertical cuts or two horizontal cuts , but there's still another solution:

      we can make one vertical cut so the left side is 1/3 and the right side is 2/3 then we make one horizontal cut to the right side so it become two parts with size 1/3 but this cut will not only cut the right side ,it will cut the left side too!! but we can just assume that the left side is still one part when we continue the solution (even though it's actually two parts) because in the end we can give more than one part to one people.

      That's why we can apply tientmse610xx's solution , however , I still think his solution is not optimal.

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

        How do you cut the cake in case N = 11. I always think that there isn't any solution with number of cut needed < 6.

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

          actually tientmse610xx's algorithm doesn't give optimal results. furthermore , his code has a bug and doesn't apply his algorithm correctly because

          a[i] = a[i / 2] + 1

          should be

          a[i] = 2*a[i / 2] + 1

          because after making the first cut the cake will be two parts each part needs a[i/2] cuts. Now his code outputs 10 instead of 5 and it always outputs N - 1

          → Reply