sourabh912's blog

Please suggest a better approach to solve this problem.

By sourabh912, 10 years ago, In English

Hi All,

I came across the following problem recently and could not figure out an efficient way to solve it (other then backtracking). Can anyone please help.

Problem Statement:

A circular cake has 3*N slices. Each slice has a size given. Person X, on his birthday, has to eat the whole cake along with his friends Y and Z. Because its X's birthday, he is made to choose a slice everytime, and the slice immediate to the left and right of what X has picked will be picked by Y and Z. What is the maximum cake X can eat?
Given: An array representing the cake slice size.

Example 1: Input: {4,8,3} Output : 8
Explanation: X will simply pick 8

Example 2: Input: {6,11,14,22,20,3} Output: 34
Explanation: X will pick 14 & 20 sized slices

Example 3: Input: {14,11,6,3,22,20} Output: 36
Explanation: X will pick 14 & 22 sized slices.

Note: X cannot pick 14 & 20 as they are adjacent.

Thanks

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

Comments Comments (10)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

http://codeforces.net/problemset/problem/456/C

It's very similar to this problem, without taking in consideration the circular property. To bypass this you could just do 2 DPs, in one you take the first piece, in the other you leave it.

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

    I guess you've misunderstood the problem you mentioned. They are not similar.

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

      Yes thats right. Anyone please explain the better approach for it.

      Thanks

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

you either take the biggest number, or take the two numbers next to it(there is no reason to take only 1 of them since you could have chosen the big number and get more pizza) (the order of taking the 2 pieces do matter though) now you get a 3 sub problems that are simillar to the first one. The relation is T(3n)=T(3n-3)+2T(3n-6). so you can solve the original problem in O(2^n). I don't see how to get further with the problem. what are the limits on N?

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

    Limits were not mentioned. And yes the solution with exponential time complexity is easily approachable. Solution with better time complexity (if possible) is what I am looking for.

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

      what is the source of the problem?

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

        It was asked by one of my friend. Not sure how he got access to it. I don't think source of the problem matters as I don't find anything wrong with the problem statement.

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

There is DP solution. The idea is to select best order for braces.
(1(234)56)(789)
(1(23(456)7)89)
Each pair of braces have to contain three numbers and possibly have some inner braces. sample code is not tested

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

    goo.gl_SsAhv: The approach seems to be correct. Though I tested the code on the 2nd example and the output returned is 66 but the correct output is 34.

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

So we want to pick N slices with maximum sum and we can't pick adjacent slices. My O(n^2) DP implementation

→ Reply