COLARR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Hiroto Sekido, Gerald Agapov
Editorialist: Ajay K. Verma

DIFFICULTY:

Easy

PREREQUISITES:

Ad-hoc, Sorting

PROBLEM:

We are given a list of N cells, and a set of M colors, with each cell having a color initially (specified by array A). If a cell has a given color, it fetches some points which are specified by a two-dimensional matrix B. It is also possible to recolor a cell with a different color, but it has a cost which is specified by a two-dimensional matrix C. The goal is perform at most k recolorings for a given k such that the gain (the points obtained from cell colors - cost of recolorings) is maximum.

QUICK EXPLANATION:

If we do not perform any recoloring, the gain would be the sum of B[i][A[i]] values (The contribution of i-th cell is B[i][A[i]]). For each cell, compute the maximum increment in its contribution that can be obtained by recoloring, and pick the k cells with highest increments.

EXPLANATION:

Assume that we do not perform any recolorings, in that case there will be no cost for recolorings, and the gain would be the sum of points obtained from cell colors.
Since the color of i-th cell is A[i], it will fetch B[i][A[i]] points. We will call this value as the contribution of i-th cell. The total gain will be the sum of the contributions of all cells.

Now, it is possible that we can increase the contribution of a cell by recoloring it. For example, if we recolor i-th cell with color j, it will cost us C[i][j], and the points that it will fetch will be B[i][j], which could be so large that it may compensate the cost of recoloring. More formally,

old contribution = B[i][A[i]],
cost of recoloring = C[i][j],
new contribution = B[i][j],
net gain = (B[i][j] - B[i][A[i]]) - C[i][j].

Now if the net gain is negative, then there is no point of recoloring the i-th cell with j-th color, however, if it is positive, recoloring this cell would bring us more points. For each cell i, try all possible recoloring of it, and pick the one which maximizes the net gain. We denote the maximum net gain of i-th cell as delta[i]. The following code computes the delta values for all cells.

for (int i = 0; i < N; ++i) {
    delta[i] = 0;
    for (int j = 0; j < M; ++j)
        delta[i] = max(delta[i], B[i][j] - B[i][A[i]] - C[i][j]);
}

Once we have the maximum net gains of all cells, we need to pick the k cells which have the highest net gains. This could be obtained by sorting or using a more efficient selection algorithm.

TIME COMPLEXITY:

O (NM + N lg N)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.
Tester’s solution will be put up soon.

3 Likes

Can one cell be repainted multiple times?

@chandan721:

Your code fails with input from problem statement when 1 1 2 2 is changed to 2 1 2 1, and it returns 6 instead of 5.

1
4 2 1
2 1 2 1
1 1
1 1
1 1
3 1
0 1
0 1
1 0
1 0

@rishabh1994: your code returns 7

@yagyank: your code returns 6 too

@shanu333: your code returns 6 also

PLEASE GIVE A VALID TEST CASE FOR WHICH THIS SOLUTION FAILS…
http://www.codechef.com/viewsolution/3436859

This approach worked for me:

Make sure you read the input values correctly.

I. sum points for the initial colors of every cell

II. find net gain/loss for every cell

III. sort net gain/loss - array

IV. add k net gain/loss values, starting from the highest value

Try the test cases given here.

Answer should be

46
39
17

PS: I created these test cases by using this program.

4 Likes

I think there is no possible solution for Python, http://www.codechef.com/viewsolution/3444255 . The time limit is too strict. Authors, Testers and Admin please look into this!

i did this one using DP… thought Greedy might give a WA :confused:

http://www.codechef.com/viewsolution/3479478
I have tried the given test cases and its giving the Correct answer in my pc . But submitting here it is giving me a WA.please help!!

I was thinking of a modified version of this problem,where instead of atmost ‘k’ re-colourings, we are allowed to spend atmost ‘k’ amount on repainting(not including the amount we may gain by repainting )
What would be the approach to solving this problem? Any ideas?

1 Like

@admin please tell the problem in my solution…

#include<iostream>
using namespace std;

void Merge(int* left,int* right,int* arr,int nl,int nr)
{
    int i=0;
    int j=0;
    int k=0;
    while(i<nl&&j<nr)
    {
        if(left[i]<=right[j])
        {
            arr[k]=left[i];
            i++;
        }
        else
        {
            arr[k]=right[j];
            j++;
        }
        k++;
    }
    while(i<nl)
    {
        arr[k]=left[i];
        i++;
        k++;
    }
    while(j<nr)
    {
        arr[k]=right[j];
        j++;
        k++;
    }
}

void MergeSort(int *a,int len)
{
    if(len<2)
        return;
    int mid=len/2;
    int* left=new int[mid];
    int* right=new int[len-mid];
    for(int i=0;i<mid;i++)
        left[i]=a[i];
    for(int i=mid;i<len;i++)
        right[i-mid]=a[i];
    MergeSort(left,mid);
    MergeSort(right,len-mid);
    Merge(left,right,a,mid,len-mid);
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,m,k;
        cin>>n>>m>>k;
        int* a=new int[n+1];
        for(int i=1;i<n+1;i++)
            cin>>a[i];
        int b[n+1][m+1];
        for(int i=1;i<n+1;i++)
        {
            for(int j=1;j<m+1;j++)
                cin>>b[i][j];
        }
        int c[n+1][m+1];
        for(int i=1;i<n+1;i++)
        {
            for(int j=1;j<m+1;j++)
                cin>>c[i][j];
        }
        int* p=new int[n+1];
        for(int i=1;i<n+1;i++)
        {
            p[i]=0;
            for(int j=1;j<m+1;j++)
            {
                int q=b[i][j]-b[i][a[i]]-c[i][j];
                p[i]=max(p[i],q);
            }
        }
        p[0]=0;
        MergeSort(p,n+1);
        int sum=0;
        for(int i=1;i<n+1;i++)
            sum+=b[i][a[i]];
        for(int i=0;i<n+1;i++)
        {
            if(p[i]>0)
                sum+=p[i];
        }
        cout<<sum<<endl;
    }
}

I implemented exactly the same algorithm…still was getting WA
Someone give some test case where my soln fails

http://www.codechef.com/viewsolution/3432735

please tell the test cases for which the solution fails…i am new to programming
http://www.codechef.com/viewsolution/3415420

i also implemented the same algo but wa…any test case for which my algo fails?

http://www.codechef.com/viewsolution/3412995

Hi, I can’t tell why would this approach fail. Anyone could provide a test case for it please.
http://www.codechef.com/viewsolution/3407171

I also implemented exactly the same algorithm…still was getting WA Someone give some test case where my soln fails…This Really frustrated me .:wink:

http://www.codechef.com/viewsolution/3415802

It can, but you want to do it?

Repainting cell i to color c gain[i][c] and costs[i][c], so if you repaint it multiple times C1 - > C2 -> C3, there is additional cost[i][C2] which you won’t pay if you paint it from C1 -> C3…

As you can see, you can do it, but it won’t be the max result.

1 Like

http://www.codechef.com/viewsolution/3367262 well this is one of the AC solutions and returns 6 too

Yes, but what if it costs less to do c1->c2->c3 than c1->c3?

I don’t think so. In your given test case there’s no need of repainting.Initial colors itself would give maximal points(6)