 # CHEFWED - codechef.com/problems/CHEFWED

What’s wrong with this solution. I have used 2D dp table to solve it, with one state as number of tables used and another state represents index of the guest to be placed.

``````#include <bits/stdc++.h>
using namespace std;
#define int     int64_t
#define IOS     ios::sync_with_stdio(0); cin.tie(0);

const int inf = 1e10;

signed main() {
IOS;
int t; cin >> t;
while(t--) {
int n, k; cin >> n >> k;
vector<int> a(n);
int num_families = 0;
for(auto &num : a) {
cin >> num;
num_families = max(num_families, num);
num -= 1;
}
vector<vector<int>> count(num_families, vector<int>(n, 0));
for(int i=0;i<num_families;i++) {
for(int j=0;j<n;j++) {
if(j == 0) {
count[i][j] = (i == a[j]);
} else {
count[i][j] = count[i][j-1] + (i == a[j]);
}
}
}
// for(int i=0;i<num_families;i++) {
//     cout << "FAMILY " << i + 1 << " : ";
//     for(auto num : count[i]) {
//         cout << num << " ";
//     }
//     cout << "\n";
// }
vector<vector<int>> dp(n + 1, vector<int>(n + 1, inf));
/**
* @brief
* dp[i][j] - denotes the minimum cost associated to place first 'i' guests at 'j' tables.
* At every index 'i' we have two choices
*      1. Place the 'i'th guest with 'i-1'th guest
*      2. Place the 'i'th guest on a new table
*/
dp = k;
dp = inf;
dp = k;

for(int i=2;i<=n;i++) {
dp[i] = dp[i-1];
int count_of_quarell = count[a[i-1]][i-1];
if(count_of_quarell == 2) {
} else if(count_of_quarell > 2) {
}
}

for(int j=2;j<=n;j++) {
dp[j] = dp[j-1] + k;
}

for(int i=2;i<=n;i++) {
for(int j=2;j<=n;j++) {
// 1. cost associated with adding 'i'th guest to 'j'th table = count of index 'k' such that 0 <= k <= i-1 and a[k] == a[i] => count[a[i]][i]
// 2. cost associated with placing 'i'th guest on a new table => k

// STARTING A NEW TABLE AND PLACING GUEST 'i' AT THIS NEW TABLE
dp[i][j] = min(dp[i][j], dp[i-1][j-1] + k);

int count_of_quarell = count[a[i-1]][i-1];
if(count_of_quarell == 2) {
} else if(count_of_quarell > 2) {
}

// PLACING THE 'i'th GUEST WITH 'i-1'th GUEST
dp[i][j] = min(dp[i][j], dp[i-1][j] + to_add);
}
}
int ans = inf;
for(int j=1;j<=n;j++) {
// cout << dp[n][j] << " ";
ans = min(ans, dp[n][j]);
}
// cout << "\n";
cout << ans << "\n";
}
}
``````

Here is the submission link: Solution: 56754985 | CodeChef