CHEFWED - Editorial

PROBLEM LINK:

Division 1
Division 2
Video Editorial

Author: Aryan Agarwala
Tester: Данило Мочернюк
Editorialist: Ritesh Gupta

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

You are given N guests numbered 1 to N. You have to arrange the guests on some tables where each table cost K unit such that if two guests i and j (i < j) present on some table then guest from i+1 to j-1 also present on that table. Every guest i has a number F_i assigned to it. If two guest with the same F value are present on one table then it is called an argument for both of them.

You have to find the ideal arrangement where sum of the cost of tables used and numbers of guest has argument is as minimum as possible.

QUICK EXPLANATION:

Simply consider all the possibilities of adding tables where on each table, the guests seated must have consecutive numbers and find the minimum inefficiency among all. This can be solved using Dynamic Programming.

  • Assume M guests on a single table (M would be equal to N initially).
  • Now divide them into two tables such that the first table contains the first k guests and the second table contains the remaining M-k guests (consider all values of k from 1 to M inclusive).
  • Let the first k guests stay on the first table itself, and add another table for remaining guests.
    • The inefficiency for the first table can be calculated using a loop.
    • For finding the minimum inefficiency for the second table, assume the second table to be a single table and find the inefficiency using steps above (hint: use recursion).
  • Find the minimum possible efficiency among all considered values of k.

EXPLANATION:

Subtask 1:

Given that K is equal to 1.

Lemma: If any two guests are likely to fall in an argument, seating them on different tables would give the minimum inefficiency.

Proof: Assume that there are two guests who are from the same family. Now consider two situations:

  1. Seating them on the same table Inefficiency = cost of table + number of guests likely to fall in an argument = 1 + 2 = 3
  2. Seating the guests on different tables Inefficiency = cost of tables + number of guests likely to fall in an argument = 2 + 0 = 2

Hence, seating the guests who are likely to argue on different tables yields the minimum inefficiency if K = 1.

Subtask 2:

The first thing to observe is that for every guest, we have a choice of adding a new table. In other words, we can have at least 1 and at most N tables.

Assume that there’s just one table initially which has all the guests sitting on it. Now, this arrangement might not have the minimum inefficiency. So, we consider all the possible arrangements and choose the one with the minimum inefficiency.

Basically, we minimize the inefficiency by splitting the guests into two parts and assigning one table to the first part. Then, for the second part, we again try to minimize the inefficiency by following the same steps until we have no guests remaining.

Formally, Start with just one table and add guests from pos to j on this table (where pos would be 1 initially), and add another table for remaining guests (from j+1 to N). Consider all positions for j between pos and N inclusive. For the second part, i.e, from j+1 to N, recurse with i = j+1. Lastly, make sure not to add a table that has 0 guests on it.

dp(pos) = 0, if pos>=N
dp(pos) = min ( \{ cost of seating i guests starting from pos \} + dp(i+1) ) for all i from pos to N-1

TIME COMPLEXITY:

TIME: O(N^2)
SPACE: O(N)

SOLUTIONS:

Setter's Solution
Tester's Solution
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define sz(a) (int)(a.size())
using namespace std;
const int MAX = 1005;
int dp[MAX];
int f[MAX];
int cnt[MAX];
int main()
{
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    assert(1 <= T && T <= 100);
    while(T--)
    {
        int n , K;
        cin >> n >> K;
        assert(1 <= n && n <= 1000);
        assert(1 <= K && K <= 1000);
        for(int i = 0; i < n; i++)
        {
            cin >> f[i];
            assert(1 <= f[i] && f[i] <= 100);
        }
        for(int i = 1; i <= n; i++)
                dp[i] = 1e9;
        dp[0] = 0;
        for(int i = 0; i < n; i++)
        {
            memset(cnt , 0 , sizeof cnt);
            for(int j = i; j < n; j++)
            {
                cnt[f[j]]++;
                int g = 0;
                for(int k = 1; k <= 100; k++)
                    g += cnt[k] == 1 ? 0 : cnt[k];
                dp[j + 1] = min(dp[i] + g + K , dp[j + 1]);
            }
        }
        cout << dp[n] << endl;
    }
    return 0;
} 
Editorialist's Solution
#include<bits/stdc++.h>
 
#define int long long
#define pb push_back
#define ff first
#define ss second
 
using namespace std;
 
int n, k;
vector<int> arr;
vector<int> memo;
 
int dp(int l)
{
    if(l>=n)
        return 0;
 
    int &ans=memo[l];
 
    if(ans!=-1)
        return ans;
 
    ans=INT_MAX;
    int g=0, tmp=0;
    unordered_map<int, int> f;
 
    for(int i=l; i<n; i++)
    {
        if(f[arr[i]]==1)
            tmp++;
 
        f[arr[i]]++;
 
        if(f[arr[i]]>1)
            g++;
 
        ans=min(ans, g+tmp+((i+1<n)?k:0)+dp(i+1));
    }
 
    return ans;
}
 
void solve()
{
    cin>>n>>k;
 
    arr.clear();
    memo.clear();
    arr.resize(n);
    memo.assign(n, -1);
 
    for(auto &x:arr)
        cin>>x;
    
    cout<<k+dp(0)<<endl;
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t=1;
    cin>>t;
 
    while(t--)
        solve();
    
    return 0;
} 

Video Editorial

35 Likes

https://www.codechef.com/viewsolution/36822725
what is wrong in the soln

Did any one of y’all solved it without using DP ?

4 Likes

can it be possible without dp,

getting AC for 8 out of 10 test cases

one test case is
1 2 3 2 1 2 3 and k=3
for this ans should be 8 but getting 9 here

#include <bits/stdc++.h>
using namespace std;
int main(){
int t; cin>>t;
while(t–){
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;
}
return 0;
}

1 Like

I am getting AC in 5 test cases out of 10. I didn’t use dp, I have used hashing.
https://www.codechef.com/viewsolution/36649275

6 Likes

Yes i also try this approach. But due to recursion limit it will give tle

1 Like

Many have wrote the solution seeing from youtube video… firstly uploaded by @raahul_garg which i think is an act of breaking contest rules and what the need of having this question in the contest if many are submitting same solution and getting all cleared.
I think some action would be taken considering plagiarism.

33 Likes

can anyone give testcases for subtask 2 - 2&3 … with answer please

1 Like

This was my own solution. Used dynamic programming to calculate the cost of each possible table, then use a priority queue. reduced it to a graph problem

import heapq


def min_efficiency(no_of_people, cost_of_table, families):
    table_costs = [[None for _ in range(no_of_people)] for _ in range(no_of_people)]
    for i in range(no_of_people):
        table_costs[i][i] = cost_of_table

    for i in range(no_of_people):
        # print(i)
        seen_once = set([families[i]])
        seen_more_than_once = set()
        cost = table_costs[i][i]
        for j in range(i + 1, no_of_people):
            if families[j] in seen_once:
                cost += 2
            if families[j] in seen_more_than_once:
                cost += 1
            if families[j] in seen_once:
                seen_once.remove(families[j])
                seen_more_than_once.add(families[j])
            elif families[j] not in seen_more_than_once:
                seen_once.add(families[j])
            # print(seen_once, seen_more_than_once)
            table_costs[i][j] = cost
        # print()
    # print(table_costs)
    heap = [(table_costs[0][j], -j) for j in range(no_of_people)]
    heapq.heapify(heap)
    # print(heap)
    seen_costs = set()
    while heap:
        # print(heap)
        cost, person = heapq.heappop(heap)
        person = -person
        while heap and heap[0][0] == cost:
            heapq.heappop(heap)

        # print(cost, person)
        seen_costs.add(cost)
        if person == (no_of_people - 1):
            return cost
        for next_person in range(person + 1, no_of_people):
            if (cost + table_costs[person+1][next_person]) not in seen_costs:
                heapq.heappush(
                    heap,
                    (cost + table_costs[person+1][next_person], -next_person)
                )


if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        no_of_people, cost_of_table = map(int, input().split())
        families = list(map(int, input().split()))
        print(
            min_efficiency(
                no_of_people=no_of_people,
                cost_of_table=cost_of_table,
                families=families,
            )
        )
1 Like

we have to arrange guest according to given sequence(or order) only
for ex:
n=5 and k=1
1 2 3 4 5

we can’t do like
one table for {1 4 5 }guests
and another table for{ 2 3}

but we can do like
one table for {1 2 3}
and another table for { 4 5}

HOPE you get that. thank you

2 Likes

Am I the only one who didn’t get this editorial??

10 Likes

Nice Question!
Here is my Top-Down Dp approach
https://www.codechef.com/viewsolution/36543088

1 Like

I did it by forming a tree of costs for all the possibilities of arranging the guests, but got a TLE error as it was quite expensive for bigger arrays.Worked for 3 test cases in subtask 2.

Thank you.

I did not use DP 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.

1 Like

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

Can anyone please explain wha is wrong in this solution. It is getting 20 marks and for remaining 80 points it is passing one subtask. I don’t understand the test case which is not passing.

My logic was I will keep all people having same Fi at same table until their number is less than or equal to cost of new table

Thanks in advance

Quite easy approach. Thanks.

for the test
n=9 k=3
1 2 3 2 2 2 1 2 3
getting 11

but ans should be 10
1 2 3 2 2 2 in one table
1 2 3 in second table
(3+4)+3=10

@rishup_nitdgp Setter’s solution is empty.

1 Like