CHEFWED - Editorial

[wiseman_123]

Oh sorry my bad. Edited the comment, now there are 26 integers.

[mathslover_crj]

My code does not show 10, it shows output as 14. Check it.

The arrangement is (1 2 3 1 4 5), (2 3 4 5)
Total inefficiency =(6+2) + (6) = 14.

[mathslover_crj]

Here also my code gives output = 22.

[skrstv123]

I solved this question without DP, my approach is very different
So were the testcases weak?
Here’s my submission CodeChef: Practical coding for everyone

[algorithmics_1]

Firstly, the idea of the state is that if we consider up to some prefix i, we can get an optimal answer by asking the question of “if i start a new sequence at this point and continue onward, will my answer be improved”

This implies a state of: dp[i] = max( j <= i : dp[j] + (number of numbers which recur in a[j+1:i])).
(by number of numbers which recur, i mean that for example in the array (3,3,3,4,4), there are 5 repetitions, since 3 recurs 3 times and 4 recurs twice)

Of course, we could solve this with a brute force and simply find that value, but that will give TLE. Therefore, we optimize with some precomputation and use some 2 dimensional prefix sums to cache the values for us, giving a resultant O(N^2) complexity.

Sorry for late reply, also!

[nikiitp18]

mine is 9,
you can have only one table
incov = 4 +1+3+1

[nikiitp18]

what should be the ans for this tc:
5 2
3 5 4 5 1

mine output is 3, all guest on one table

[codedontlie]

No the ans is not 3 but it’s 4 ( two 5 and one cost of table) -> (2 + 2) -> 4

[mathslover_crj]

OK, let us consider the test cases were not weak and gave wrong answer as per tester’s solution. But I don’t understand, is it out of policy to provide the test cases (in question/doubt) with their respective answers even after completion of the competition? I think not so. It will enable the learners to know their faults/mistakes. Isn’t it?

I had just wanted to know any one test case where my code fails, but nobody till now can provide me the same.

[mathslover_crj]

When two persons of a same family involved in argument, the total inefficiency increases by 2 and not by 1(as per given conditions).

[agarwaltanmay]

Can anyone please tell me a test case which is failing my code.

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

void solve(ll *arr, ll n, ll k, ll maximum){
    ll dp[maximum + 1], ans = k;
    memset(dp, 0, sizeof(dp));

    for(ll i = 0; i < n; i++){
        if(dp[arr[i]] == 0){
            dp[arr[i]]++;
            continue;
        }
        else{
            ll tempAns1 = dp[arr[i]] == 1 ? ans + 2 : ans + 1;
            ll tempAns2 = ans + k;
            if(tempAns1 < tempAns2){
                dp[arr[i]]++;
                ans = tempAns1;
            }
            else{
                ans = tempAns2;
                memset(dp, 0, sizeof(dp));
                dp[arr[i]]++;
            }
        }
    }
    cout<<ans<<endl;
}

int main(){
    ll t;
    cin>>t;
    while(t--){
        ll n, k;
        cin>>n>>k;
        ll arr[n], maximum = INT_MIN;
        for(ll i = 0; i < n; i++){
            cin>>arr[i];
            maximum = max(maximum, arr[i]);
        }
        solve(arr, n, k, maximum);
    }
}

Thanks in advance

[zephxr]

No Check Once,You are calculating conflicts wrong.

[prakalpxj]

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

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

[shikha_bhat]

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

[phoenixsoul]

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

[aman941]

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

[emotiological]

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.

[george_ogden]

@satyam_patidar

int n,k;
cin>>n>>k;
int s[n];
bool visited[101];
fill(visited,visited+101,false);
int family[101];
fill(family,family+101,0);
for(int i=0;i<n;i++){cin>>s[i]; family[s[i]]++;}
int reqtable=1;
visited[s[0]]=true;
for(int i=1;i<n;i++){
if(!visited[s[i]]){
visited[s[i]]=true;
}
else{ reqtable++; fill(visited,visited+101,false); visited[s[i]]=true; }
}
int argue=0;
for(int i=0;i<101;i++){
if(family[i]>1) argue+=family[i];
}
int ans=min(k+argue,reqtable*k);
cout<<ans<<endl;
}

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

[hacker325]

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

[dharm8149]

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

Relevel Access the Algo Question

You have integer array of length n ([1 2 1 2 1 3 1 3]).Remove all occurance of 1(array become [2 2 3 3]).Now you can append this resulting array to initial array , any number of time ([1 2 1 2 1 3 1 3 2 2 3 3]). Given a resulting array print the initial array eg. input 1 2 1 2 1 3 1 3 2 2 3 3 2 2 3 3 output: 1 2 1 2 1 3 1 3 if no initial array possible print -1 if multiple ans possible print lexicographically smaller array.