C++ – Round Table – Minimum Cost Algorithm

algorithmscdynamic programming

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?

Best Answer

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]);
 }
Related Topic