Help with ACCBIP [RESOLVED]

[chenreddy]

In August Long Challenge, I wasn’t able to solve the ACCBIP problem (CodeChef: Practical coding for everyone). Today, I went through the editorial (ACCBIP - Editorial) to gain some hints and implemented my solution. It passes for the first 3 subtasks but not the last. I have looked at the complete methodology in the editorial and tried to debug it with giving parallel lines as input but could not find the issue. Can someone please help me understand any gap in my logic. Thanks in advance.

I was able to fix the issue. The issue was with the while loop inside calculate_triangles method. I wasn’t updating the inner_ptr correctly. (Note: I am not correcting the issue in the code below.)

My Code

#include <bits/stdc++.h>
using namespace std;

#define int long long int

int N,C,K;

//calculates the triangles remaining vs deleted lines for each color
vector<int> calculate_triangles(unordered_map<int,int> umap, int cost)
{
    vector<int> cnt;
    
    for(auto&x:umap)
    {
        cnt.push_back(x.second);
    }
    
    int n=cnt.size();
    
    if(n==0)    return {0};
    
    sort(cnt.begin(),cnt.end());
    
    //for each index i(parallel lines bunch labelled i),
    //I calculate the number of triangles formed using a line from group i,
    //some group j and group k such that j,k>i,
    //that can be removed by deleting a line from this group
    //I store suffix sum and sqaure it. Then I remove the cases where j=k
    
    int sum[n];
    sum[n-1]=0;
    int sum_squares[n];
    sum_squares[n-1]=0;
    int total=cnt[n-1];
    int tgles[n];
    tgles[n-1]=0;
    
    int all_tgles=0;
    
    for(int i=n-2;i>=0;i--)
    {
        sum[i]          =   sum[i+1] + cnt[i+1];
        sum_squares[i]  =   sum_squares[i+1] + cnt[i+1]*cnt[i+1];
        total           =   total + cnt[i];
        tgles[i]        =   (sum[i]*sum[i] - sum_squares[i])/2;
        all_tgles       =   all_tgles + cnt[i]*tgles[i];
    }
    
    
    vector<int> arr(1);
    
    arr[0]=all_tgles;
    
    int outer_ptr=0,inner_ptr=1;
    int pos=1;
    
    //store the possible ways till we don't have any more lines or eraser
    while(pos<=total and cost*pos<=K)
    {
        arr.push_back(arr.back()-tgles[outer_ptr]);
        
        pos++;
        if(inner_ptr==cnt[outer_ptr])
        {
            inner_ptr=1;
            outer_ptr++;
        }
    }
    
    return arr;
}


//solving the knapsack problem
void solve_knapsack(vector<int> cost_vs_triangles[],int cost_color[])
{
    vector<int> DP(K+1,0);
    
    for(int i=1;i<C;i++)
    {
        vector<int> DP_new(K+1,1e12);
        
        //for all possible cost combinations, we minimise the triangles
        for(int j=0;j<cost_vs_triangles[i].size();j++)
        {
            for(int p=0;p<K+1;p++)
            {
                int total_cost=j*cost_color[i]+p;
                int total_tgls=cost_vs_triangles[i][j]+DP[p];
                
                if(total_cost>K)    break;
                
                DP_new[total_cost]=min(DP_new[total_cost],total_tgls);
            }
        }
        
        for(int p=0;p<K+1;p++)
        {
            DP[p]=DP_new[p];
        }
    }
    
    int min_ans=1e12;
    
    for(int p=0;p<K+1;p++)
    {
        min_ans=min(min_ans,DP[p]);
    }
    
    cout<<min_ans<<endl;
}


void solve()
{
    cin>>N>>C>>K;
    C++;//to directly store the given color instead of decreading it by 1
    
    unordered_map<int,int> color_group[C];
    
    for(int i=0;i<N;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        color_group[c][a]++;
    }
    
    int cost_color[C];
    for(int c=1;c<C;c++)
    {
        cin>>cost_color[c];
    }
    
    vector<int> cost_vs_triangles[C];
    
    for(int c=1;c<C;c++)
    {
        cost_vs_triangles[c]=calculate_triangles(color_group[c],cost_color[c]);
    }
    
    solve_knapsack(cost_vs_triangles,cost_color);
}


signed main() {
    
    int t;
    cin>>t;
    
    while(t--)
    {
        solve();
    }
}