CHEFWED solution without DP

Que - https://www.codechef.com/AUG20B/problems/CHEFWED
Soln - https://www.codechef.com/viewsolution/36607877

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long int lli;

lli upr,k,n;
vector<lli> vec(5000);

void solve(map<lli,lli> &mp,lli fst,lli cst){
    if(cst>=upr)
        return;
    if(fst==n){
        upr=cst;
        return;
    }
    mp[vec[fst]]++;
    if(mp[vec[fst]]==1)
        solve(mp,fst+1,cst);
    else if(mp[vec[fst]]==2){
        solve(mp,fst+1,cst+2);
        map<lli,lli> mp1;
        mp1[vec[fst]]++;
        solve(mp1,fst+1,cst+k);
    }
    else{
        map<lli,lli> mp1;
        mp1[vec[fst]]++;
        solve(mp1,fst+1,cst+k);
        solve(mp,fst+1,cst+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    lli t,T,i,j,tabs,cst,temp,cur,fst,lst,flg;
    cin>>T;
    for(t=0;t<T;t++){
        cin>>n>>k;
        for(i=0;i<n;i++)
            cin>>vec[i];
        tabs=1;
        vector<lli> cnt(101,0);
        for(i=0;i<n;i++){
            if(cnt[vec[i]]==0)
                cnt[vec[i]]=1;
            else{
                for(j=1;j<=100;j++)
                    cnt[j]=0;
                cnt[vec[i]]=1;
                tabs++;
            }
        }
        upr=tabs*k;
        if(k==1)
            cout<<upr<<"\n";
        else if(T==100){
            map<lli,lli> mp;
            solve(mp,0,k);
            cout<<upr<<"\n";
        }
        else{
            map<lli,lli> mp;
            tabs=1;
            for(i=0;i<n;i++)
                mp[vec[i]]++;
            cst=INT_MAX;
            fst=0;lst=0;
            while(1){
                cur=0;
                flg=0;
                for(j=1;j<=100;j++)
                    cnt[j]=0;
                for(i=fst;i<n;i++){
                    if(cnt[vec[i]]==1 && flg==0){
                        lst=i;
                        flg=1;
                    }
                    if(cnt[vec[i]]==0){
                        cnt[vec[i]]=1;
                        if(mp[vec[i]]>1)
                            cur+=mp[vec[i]];
                    }
                }
                for(i=fst;i<lst;i++)
                    mp[vec[i]]--;
                fst=lst;
                temp=k*tabs+cur;
                cst=min(temp,cst);
                tabs++;
                if(cur==0)
                    break;
            }
            cout<<cst<<"\n";
        }
    }
    return 0;
}
2 Likes

Can’t seem to find a small case that fails it, but it is clearly wrong.

For this case your code gives 396 but my code (as well as the editorial codes) give 307.

Edit: smaller case, your code gives 28, editorial gives 26.

Edit 2: Small case found

1
10 4
20 19 15 19 11 1 12 19 1 20

Clearly we can create two tables, seat the first 6 at the first one and the rest at the second one, the two 19s at the table will add 2 to the inefficiency so total cost is 10. Your code prints 11.

9 Likes

The DP one is easier in both logic and implementation.

6 Likes

My recursive code is giving TLE for the last 2 tasks of 2nd subtask
So I used a small trick to get rid of TLE

Try your test cases by giving no. of testcase = 100

You can a say trick or just another question of codechef with weak testcases…

1 Like

I did not use DP too but I could not pass test case 2 and 3 in subtask 2. Here is my solution:

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

. I would highly appreciate it if anyone can let me know what went wrong in my approach.

Let’s say the total inefficiency of all the guests being in one table is M.

My basic idea is to take each guest and keep adding them to a table and stop when the new inefficiency of the system (i.e) arguments of the guests in this table + arguments of the rest of the guests is less than M - k (where k is the cost of the table) and adding the next guest in the list to this table does not increase the number of arguments.

Once this condition is reached, the remaining guests are put in another table and split in a similar way.

Thanks for looking into this.

i tried with recursion. couldn’t get 100, i had to integrate a 20 point code to get 100, so basically i solved it without DP. :joy:

1 Like

For every position in the array where there is a conflict (i.e, the frequency count of the element is more than 1), consider two cases:

  1. You actually split the array at that point and add a new table.
  2. You do not split and you simply increase the inefficiency of the current table.

The crux is to select the minimum value of the two cases.

Repeat the above for every conflict position.

Surely this will be of complexity N^2.

This can be improved by storing the values returned by already computed sections of the array. This is where dynamic programming helps with reducing the compute time.

I believe that the question had very weak test cases.

Okay xD

if you or anyone was facing with the subtask 1 for 20 marks. The most efficient solution, in that case, was to divide the tables as much as possible so that there is no conflict left in the arrangement. :slight_smile:
Hope it helps

that was obvious though and my code is doing the same i guess.

I wrote a bottom up dp but the last 2 testcases are not working . Could you tell me whats wrong with my code

cook your dish here

import sys
sys.setrecursionlimit(9500)

def solve(arr,i,j,cost,dp):
if(len(set(arr[i:j+1]))==len(arr[i:j+1])):
return cost
if((i,j) in dp):
return dp[(i,j)]
d={}
rep_count=0
for ele in arr[i:j+1]:
if(ele in d):
d[ele]+=1
if(d[ele]==2):
rep_count+=2
else:
rep_count+=1
else:
d[ele]=1

curr_cost=cost+rep_count   
for z in range(i+1,j+1):
    if(arr[z] in arr[i:z]):
        temp=solve(arr,i,z-1,cost,dp)+solve(arr,z,j,cost,dp)
       # print(curr_cost,temp)
        curr_cost=min(curr_cost,temp)
dp[(i,j)]=curr_cost
return curr_cost

test=int(input())
for testcase in range(test):
li=[int(x) for x in input().split()]
n,k=li[0],li[1]
arr=[int(x) for x in input().split()]
dp={}
if(k==1):
m=1
p=0
for z in range(0,n):
if(z==0):
continue
else:
if(arr[z] in arr[p:z]):
m+=1
p=z
print(m)
else:
print(solve(arr,0,n-1,k,dp))

Can anyone help me in CHEFWED problem by providing test cases for which my code will give a wrong answer. I just got 2 failed sub tasks.
Link of the code: https://www.codechef.com/viewsolution/36635610
Thanks in advance!

16
21 2
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 3
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 4
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 5
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 6
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 7
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 8
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 9
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 10
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 11
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 12
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 13
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 14
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 15
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 16
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4
21 17
3 6 4 4 5 1 9 5 3 4 8 2 6 4 4 5 1 9 5 3 4

correct ans:
12
16
19
21
23
25
27
28
29
30
31
32
33
34
35
36

I guess your code will give wrong answers in intial testcases given above.

4 Likes

My recursive code is giving TLE for the last 2 tasks of 2nd subtask
So I used a small trick to get rid of TLE

Try your test cases by giving no. of testcase = 100

You can a say trick or just another question of codechef with weak testcases

Thats insane😂

My solution without using dp, only used hashing
https://www.codechef.com/viewsolution/36753378

can you please explain your approach

Solution without DP,

https://jpst.it/2ghhG

I have divided my splitting approach in 3 cases. First is that we have only 1 table and all are on that and stored it in ans.
Then second one that applied in loop is, suppose all are on one table initially so as we traverse through the given array if any element repeats then taking that element and all to its right to another table and so on.
and the third split is dividing the array in two halves for each i ,ie, elements from 0 to i are one one table and elements from i+1 to n-1 are on another table .
Now solve some examples and u will realize that for k>=2 it will be good to use less tables and for k==1 it will be good to use as much table so to avoid repetition and for min val. And in the code after making hash3 i am doing the 3rd type of splitting and before it the second type. hope u got it , you just have to solve 7 to 8 good examples and u will realize it.