CHEFWED - Editorial

editorial
, , , , , ,
132

https://www.codechef.com/viewsolution/36818853

Can anyone help me find what is wrong in this solution?

134

I used the same logic shown in the video editorial in Python but it’s still showing TLE :frowning: Help.

135

for subtask 1, should the answer be not equal to maximum number of member from single family

136

Can anyone explain why greedy is NOT working here?

My Approach-

  1. I calculated the maximum possible inefficiency (answer) by assigning single table to everyone ie N*K

  2. Then I traversed the array from index = 1.
    I have 2 possibilities here-

    1. new family member in the current table. (simply add it to map and reduce k from ans ie ans -=k)
    2. If the member is not new. we can remove the element table here based on the val = -k+1+same
      if val is negative then remove the table by ans = ans + val.
      otherwise don’t remove the table .

Please review my code - CodeChef: Practical coding for everyone

137

Can you tell me greedy approach for subtask 1? It is another interesting problem, if anyone has proof of correctness of their approach then only reply.

138

You haven’t considered if there are arguments on some of the tables that you use

139

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[1][1] = k;
        dp[1][0] = inf;
        dp[0][1] = k;

        for(int i=2;i<=n;i++) {
            dp[i][1] = dp[i-1][1];
            int count_of_quarell = count[a[i-1]][i-1];
            int to_add = 0;
            if(count_of_quarell == 2) {
                to_add = 2;
            } else if(count_of_quarell > 2) {
                to_add = 1;
            }
            dp[i][1] += to_add;
        }
        
        for(int j=2;j<=n;j++) {
            dp[1][j] = dp[1][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];
                int to_add = 0;
                if(count_of_quarell == 2) {
                    to_add = 2;
                } else if(count_of_quarell > 2) {
                    to_add = 1;
                }

                // 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";
    } 
}
140

Hello Friend

i know its inappropriate to ask for other threat answer here but i have posted a question 3 days ago but no luck till now