Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Problem Link - http://www.iarcs.org.in/zco2013/index.php/problems/ROUNDTABLE

It's dinner time in Castle Camelot, and the fearsome Knights of the Round Table are clamouring for dessert. You, the chef, are in a soup. There are N knights, including King Arthur, each with a different preference for dessert, but you cannot afford to make desserts for all of them.

You are given the cost of manufacturing each Knight's preferred dessert-since it is a round table, the list starts with the cost of King Arthur's dessert, and goes counter-clockwise.

You decide to pick the cheapest desserts to make, such that for every pair of adjacent Knights, at least one gets his dessert. This will ensure that the Knights do not protest. What is the minimum cost of tonight's dinner, given this condition?

I used the Dynamic Programming approach, considering the smallest of i-1 & i-2, & came up with the following code -

#include<cstdio>
#include<algorithm>
using namespace std;

int main() {
int n,i,j,c,f;
scanf("%d",&n);
int k[n],m[n][2];
for(i=0;i<n;++i) scanf("%d",&k[i]);
m[0][0]=k[0]; m[0][1]=0;
m[1][0]=k[1]; m[1][1]=1;
for(i=2;i<n;++i) {
                 c=1000;
                 for(j=i-2;j<i;++j) {
                                    if(m[j][0]<c) { c=m[j][0]; f=m[j][1];}
                 }
                 m[i][0]=c+k[i]; m[i][1]=f;
}
if(m[n-2][0]<m[n-1][0] && m[n-2][1]==0) printf("%d\n",m[n-2][0]);
else printf("%d\n",m[n-1][0]);   
}

I used the second dimension of the m array to store from which knight the given sequence started (1st or 2nd). I had to do this because of the case when m[n-2]<m[n-1] but the sequence started from knight 2, since that would create two adjacent knights without dessert. The problem arises because of the table's round shape.

Now an anomaly arises when I consider the case - 2 1 1 2 1 2. The program gives an answer 5 when the answer should be 4, by picking the 1st, 3rd & 5th knight. At this point, I started to doubt my initial algorithm (approach) itself!

Where did I go wrong?

share|improve this question
1  
Flagged as off-topic. Per programmers.stackexchange.com/faq , implementation issues are better asked on stackoverflow.com . Note that this question may not be accepted on stackoverflow, as you are putting a bit too much of the effort on stackoverflow instead of yourself. –  Brian Nov 7 '12 at 19:55
4  
@Brian The question is about the algorithm (or algorithmic programming). StackOverflow is about implementation based programming, rather than algorithmic programming. –  7Aces Nov 7 '12 at 20:00
1  
If it's about the algorithm, why don't you present it in a more readable pseudocode? –  Peter Taylor Nov 7 '12 at 21:47
1  
@PeterTaylor I would've initially itself if this were a non-programming site, but it isn't. Still I will try and come up with the pseudo-code, if possible... –  7Aces Nov 7 '12 at 22:28
1  
@7Aces - I'm late to this, but it doesn't matter if it's real code or pseudocode, so long as it's readable code. –  Bobson Apr 8 '13 at 15:01
add comment

3 Answers

I dont understand the usage of c and f in your code. It would be great if you could explain a bit on that. Also i dont find the need to iterate i-2 and i-1 for every i. ( I am not able to comment on posts yet) Now i ll give you my algorithm to solve this problem similar to your approach.

Maintain a dp[n][2]. dp[i][0] is for cases starting from 0 and dp[i][1] for the ones starting from 1. Now for each i, you could just get the dp[i][0]th element as dp[i-2][0] + k[i] and dp[i][1] as dp[i-2][1] + k[i]. Trick is to do this only when appropriate. Here for cases where i%2 is equals 0, you can assume that those are the ones that will be covered when we start from 0 and rest of elements goes for the other case. Corner case will be to avoid the last element for the case of starting from 0 as the table is circular.

Here is my working code. It works for the case you just mentioned. Am not a member of the site so am not able to test for other cases though.

#include<vector>
#include<iostream>
#include<cmath>
using namespace std;

int main() {
int n, i, j, temp;
vector<int> k;
cin>>n;
for(i=0;i<n;i++) {
cin>>temp;
k.push_back(temp);
}
int dp[n][2];
/* 0 will contain the case of starting from 0
* 1 will contain the case of starting from 1 */
dp[0][0] = k[0];
dp[0][1] = 0;
dp[1][0] = k[0]; // assign the previous value itself 
dp[1][1] = k[1];

for(i=2;i<n;i++) {      
    if(i%2 == 0) {
        // case of strting from 0 . 


        dp[i][0] = dp[i-2][0] + k[i];
        dp[i][1] = dp[i-1][1];              
    }
    else{ // case of starting from 1
        dp[i][0] = dp[i-1][0];
        dp[i][1] = dp[i-2][1] + k[i];           
    }       
}
cout<<min(dp[n-1][0], dp[n-1][1]);
 }
share|improve this answer
add comment

So I've looked at your code, and I have to be honest, it will take me quite a bit longer to get into your frame of mind and code then I'm willing to put in. But I can suggest an alternative way of dividing the sub problems that I think will be easier to understand and write.

Define a 4x(n+1) array. At index i,j the j index corresponds to the sub-problem of the first n knights. The last spot is the first one repeated again. The 4 array locations correspond to 4 different cases, corresponding to whether or not the very first knight got his dessert, and whether the jth knight got his dessert.

The base case is easy to do because we have restricted whether or not the first knight gets dessert. So it's even more trivial than usual. To solve the current case in terms of previous cases is fairly straightforward: the cases where the first knight does or doesn't get dessert are completely separate. For each case, the value for the case where the current knight gets dessert is the min of the previous entries, plus the current cost of dessert. The case where he doesn't is the sum of the previous solution where the last knight did get dessert, plus the current cost of dessert.

To wrap up the algorithm: out of the 4 rows, only 2 are relevant, because only 2 correspond to cases where the beginning and end (which is the beginning repeated) are consistent. Take the smallest out of these two.

share|improve this answer
add comment

I think your algorithm does not work because the table is circular. But we can solve this using a different dynamic programming approach.

Let array 'C[]' store the costs of the desserts of each knights. We have to consider two things:

  1. W[i], The cost of including the ith knight
  2. _W[i], The cost of not including the ith knight, in this case we have to include its neighbours.

Let us forget about the table being circular for a while. As we are moving forward in each iteration _W[i] stores only the cost of including the left neighbour of 'i'.

For a particular knight 'k', we can compute W[k] and _W[k] in constant time by using the already computed values of W[k-1] and _W[k-1].

If we dont include knight 'k', we have to include knight 'k-1' so that at least one of them gets his dessert. Therefore _W[k] will be equal to the cost of including knight 'k-1', which is W[k-1].

If we choose to include knight 'k', we have two choices, either include 'k' and 'k-1' both, or include 'k' and not 'k-1'. We take the minimum of the two.

Now we have:

  • _W[k] = W[k-1]
  • W[k] = C[k] + min(W[k-1],_W[k-1])

So, if we know the value of _W[0] and W[0] then we can compute the W, and _W values for all knights upto N.

We know W[0] will be equal to C[0]. _W[0], the cost of not including knight 0, will be the cost of including its left neighbour which, if we come back to the original problem is C[N-1].

But what will happen if W[1] is chosen as _W[0] + C[1] where _W[0] is C[N-1]? We might consider knight N-1 twice.
To overcome this problem we check if C[N-1] < C[0], if it is then we know that knight N-1 will be chosen so we decrease N by one and therefore delete the last knight.

The final answer will be the minimum of W[N-1] and _W[N-1]

If you need the pseudocode:

 W[0] = C[0]
_W[0] = C[N-1]

   if C[N-1] < C[0]:
         then N = N-1

   for i from 1 to N-1:
       W[i] = C[i] + min(W[i-1],_W[i-1])
       _W[i] = W[i-1]


   return min(W[N-1],_W[N-1])

As you do constant amount of time in each iteration the time complexity is O(N), which will run well within the time limits of your problem.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.