Round Table - Minimum Cost Algorithm
- by 7Aces
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?
