CHEFWED - Editorial

poulami21 · August 17, 2020, 7:15pm

for _ in range(int(input())):
n,k=map(int,input().split())
f=list(map(int,input().split()))
dp=[]
dp.append(0)
for i in range(1,n):
    dp.append(k+dp[i-1])
    dic={}
    c=0
    for j in range(i,0,-1):
        if f[j] not in dic.keys():
            dic[f[j]]=1
        else:
            dic[f[j]]+=1
        
        if(dic[f[j]]==2):
            c+=2
        elif dic[f[j]]>2:
            c+=1
        dp[i]=min(dp[i],dp[j-1]+k+c)
print(dp[-1])

can someone tell me why my code is not giving the correct answer in all the test cases?its showing WA.

algorithmics_1 · August 17, 2020, 7:17pm

I found this one to be easier than the KMP problem, since I got a bunch of annoying WAs for a logical greedy.

#include <iostream>
#include <vector>
#include <cstdio>
#include <set>
#include <algorithm>
#include <queue>
#include <cmath>
#include <map>
using namespace std;


int dp[1001];
int a[1001];
int tot_sum[1001][101];
int tot_res[1001][1001];



	int main(){
	int T;
	cin >> T;
	while(T--){
		int N, K;
		cin >> N >> K;
		int mx_fi = 0;
		for(int i = 0; i < N; i++){
			cin >> a[i];
			mx_fi = max(mx_fi, a[i]);
		}
	
		for(int i = 0; i < N; i++){
			dp[i] = 1000009;
		}
		for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){ tot_res[i][j]=0;}}
		for(int i = 0; i < N; i++){for(int j = 1; j <= mx_fi; j++){tot_sum[i][j]=0;}}

		for(int i = 1; i <= mx_fi; i++){
			tot_sum[0][i] = (a[0] == i ? 1 : 0);
			for(int j = 1; j < N; j++){
				tot_sum[j][i] = tot_sum[j-1][i] + (a[j] == i);
			}
		}

		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				for(int k = 1; k <= mx_fi; k++){
					if(j<i){
						continue;
					}
					int amt = 0;
					if(i-1<0){
						amt = tot_sum[j][k]==1?0:tot_sum[j][k];
					} else {
						amt = (tot_sum[j][k] - tot_sum[i-1][k]) == 1 ? 0 : (tot_sum[j][k] - tot_sum[i-1][k]);
					}
					tot_res[i][j] += amt;
				}
			}
			
		}
		dp[0] = K;
		for(int i = 1; i < N; i++){
			for(int j = 0; j < i; j++){
				dp[i] = min(dp[i], dp[j] + K + tot_res[j+1][i]);
			}
			dp[i] = min(dp[i], K + tot_res[0][i]);

		}
		cout << dp[N-1] << endl;
	
	}
}

taking sums along prefixes optimizes overall solution.

mukesh153 · August 18, 2020, 5:09am

please!!explain your logic.

divansh123 · August 18, 2020, 5:13am

zephxr · August 18, 2020, 5:46am

Try this test case:
1
6 4
1 2 3 4 5 1 2 2 3
Output Should be 10.
What’s Your Output?

mathslover_crj · August 18, 2020, 5:55am

It should be
1
9 4
1 2 3 4 5 1 2 2 3

Ans should be 10

adarsh08x · August 18, 2020, 5:58am

assume 1 guest sits in one table(n guests on n tables) find the answer for it ,then assume 2 guests sit on one table(n guests on n/2 tables) find answer for it … keep doing this uptill n guests sit on one table and keep track of the minimum inefficiency you can do the same from back of the array.

mathslover_crj · August 18, 2020, 6:03am

@daniel_1999
@rishup_nitdgp

May I have the Test Case for Sub-Task 2, Task# 2 for the problem with its answer for which my following code shows ‘WA’ ? It would be a great help for me.

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

mukesh153 · August 18, 2020, 6:14am

Thanks brother…it was very helpful.

mukesh153 · August 18, 2020, 6:21am

Thanks brother…it was helpful.

ankit0038 · August 18, 2020, 7:27am

I have done this using greedy and I got 100 marks,maybe the test cases were weak.
Here’s my approach:-
–> initially use 1 table for each person(i.e N tables for N persons) and I stored this information in a vector called ‘table’ and table.size() represents the number of table I have been using.
–> now run a loop while(table.size()>=1)
–> in each while loop iteration check whether we can merge 2 table or not, In a single loop iteration check all the possibility of merging two adjacent table and choose one which results in minimum total cost.
–> doing this we will be decreasing number of table used by one(merging 2 table into 1) in each iteration.
–> our ans will be the minimum of all the iteration.
NOTE: this version of my solution was not working when the optimal ans will consist of using exactly 2 table So i handled that separately(just dividing the whole array into two segment in all possible manner first try to divide at index 1 then 2 then 3 and so on… and choose the optimal out of those O(n) possibility).

anki1_2_3 · August 18, 2020, 8:12am

Can we solve this question without using dp ???
I tried but 2 testcase of subtask 2 are failed !!
Please tell me where it’s going wrong!!
https://www.codechef.com/viewsolution/36585127

csk03012 · August 18, 2020, 9:34am

plz, anyone helps me out to find my mistake.
only one test case not passing.
https://www.codechef.com/viewsolution/36727202

goldenfeather · August 18, 2020, 10:11am

Hello everyone!

I got 8 of 10 subtasks correct. Got wrong on test case 2 and 3.

So my approach was to calculate first inefficiency for one table with all members and also the overall frequency of members from each family.

Then I iterated through the list of members, adding one to a variable say NOS whenever I encountered the first member from a family which would have an argument. I iterated till i encountered the second member from a family, at which i checked whether NOS would be greater or equal than cost of a table (since its feasible to split only when no. of arguments are less than cost of adding a table). If it was less than cost of table, i continued until another such condition took place. Then whenever i found a member which is second last, i added one to NOS. And when i encountered the last member from a family, i checked whether NOS was greater than or equal to cost of table.
Any good soul could spend some time to help out?

Code to my submission

#include <bits/stdc++.h>
using namespace std;    
int main() {
    	long long int t,n,k,f[1000],i,fam[101],che[101],ans,no,j,flag=0;
    	cin>>t;
    	while(t--)
    	{
    	    flag=0;
    	    memset(fam,0,sizeof(fam));
    	    memset(che,0,sizeof(che));
    	    cin>>n>>k;
    	    ans=k;
    	    no=0;
    	    for(i=0;i<n;i++)
    	    cin>>f[i];
    	    reverse(f,f+n);
    	    for(i=0;i<n;i++)
    	    fam[f[i]]++;
    	    for(i=1;i<=100;i++)
    	    if (fam[i]>1) ans+=fam[i];
    	    for(i=0;i<n;i++)
    	    {
    	        che[f[i]]++;//cout<<no<<" "<<che[f[i]]<<" "<<fam[f[i]]<<"\n";
    	        if (che[f[i]]==1)
    	        {
    	            if (fam[f[i]]==che[f[i]]+1)
    	            no+=2;
    	            else if (fam[f[i]]==che[f[i]])
    	            ;
    	            else
    	            no++;
    	        }
    	        else if (che[f[i]]==2)
    	        {
    	                if (flag==2)
    	                {
    	                if (fam[f[i]]==che[f[i]])
    	                no-=2;
    	                if (fam[f[i]]==che[f[i]]+1)
    	                ;
    	                else no--;
                        flag=0;	                }
    	               else if (flag==0) flag=1;
    	            
    	        }
    	        else if (che[f[i]]>2)
    	        {
    	            if (fam[f[i]]==che[f[i]]+1)
                    no++;
                    if (che[f[i]]==fam[f[i]])
                    {
                        if (flag==0) flag=1;
                    else if (flag==2)
                    {
                        no--;
                        flag=0;
                    }
                }
	        }
	        //if (flag!=1) cout<<f[i]<<" ";
	        if (no>=k)
	        {
	            if (flag==1)
	            {for(j=1;j<=100;j++)
	            {fam[j]-=che[j];
	            if (f[i]==j) fam[j]+=1;
	            }
	            memset(che,0,sizeof(che));
	            ans-=no;
	            ans+=k;
	            no=0;
	            flag=0;
	            i--;
	            //cout<<" | ";
	            //cout<<i<<" "<<ans<<"\n";
	            }
	            else;
	            
	        }
	        else
	        {
	            if (flag==1) 
	            {flag=2;che[f[i]]--;i--;}
	        }
	    }
	    
	    //cout<<che[5]<<che[1]<<che[3]<<"\n";
	    cout<<ans<<"\n";
	}
	return 0;
}

anon26334743 · August 18, 2020, 10:22am

I solved it without DP and just with maps. It passed every test cases except two(2 AND 3). Can anyone help me with this? CodeChef: Practical coding for everyone

havoic · August 18, 2020, 10:25am

i have solved this question without using dp…just greedy approach
#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
int a[n];
for(int i=0;i<n;i++) cin>>a[i];
set s;
vector vect;
int count=0,ans=0;
if(k==1){
for(int i=0;i<n;i++){
count++;
s.insert(a[i]);
if(s.size()!=count){
ans++;
s.clear();
count=1;
s.insert(a[i]);
}
}
cout<<ans+1<<endl;
}
else{
map<int,int> m;
map<int,int> m1;
map<int,int> m2;
map<int,int> m3;
for(int i=0;i<n;i++){
count++;
s.insert(a[i]);

       if(s.size()!=count){
           ans++;
           s.clear();
           count=1;
           s.insert(a[i]);
           int hello1=k;
           for(int j=0;j<i;j++){
               m1[a[j]]++;
           }
           for(auto x:m1){
            if(x.second>1)
            hello1=hello1+x.second;
            }
            for(int j=0;j<=i;j++){
               m2[a[j]]++;
           }
           int hello2=k,hello3=k;
           for(auto x:m2){
            if(x.second>1)
            hello2=hello2+x.second;
            }
            for(int j=i+1;j<=n;j++){
               m3[a[j]]++;
           }
           for(auto x:m3){
            if(x.second>1)
            hello3=hello3+x.second;
            }
           for(int j=i;j<n;j++){
               m[a[j]]++;
          }
           int hello=k;
           for(auto x:m){
            if(x.second>1)
            hello=hello+x.second;
        }
        vect.push_back(ans*k+hello);
        vect.push_back(hello1+hello);
        vect.push_back(hello2+hello3);
        m.clear();
        m1.clear();
        m2.clear();
        m3.clear();
       }
   }
   vect.push_back((ans+1)*k);
    
    int temp=k;
    for(int i=0;i<n;i++) m[a[i]]++;
    for(auto x:m){
        if(x.second>1){
            temp=temp+x.second;
        }
    }
   vect.push_back(temp);
   cout<<*min_element(vect.begin(),vect.end())<<endl;
   }
}

return 0;

}

uhateme · August 18, 2020, 12:29pm

Happy to help!

h_sh · August 18, 2020, 12:48pm

But as testcase is weak you can solve uisng this trick;
I found that answer can be found from two calculation

Try to arrange in one table
Try to arrange in two table with all possibilities .
and min(1,2) will be answer.

divansh123 · August 18, 2020, 1:36pm

This is my code
…
I have one question, instead of passing one index to getAns() function, I passed two indices, a start and an end and then did two recursive calls but that gives a TLE, why is it redundant to pass two indices. Can you explain?

anon33859954 · August 18, 2020, 2:07pm

Can you explain a little bit please…