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
http://codeforces.com/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.
I guess you've misunderstood the problem you mentioned. They are not similar.
Yes thats right. Anyone please explain the better approach for it.
Thanks
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?
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.
what is the source of the problem?
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.
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
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.
So we want to pick N slices with maximum sum and we can't pick adjacent slices. My O(n^2) DP implementation