COLARR - Editorial

editorial
, , ,
21

please please help me find a test case for which my solution doesnt work
http://www.codechef.com/viewsolution/3437870

22

@yagyank : Without coloring the grid, you can score a maximum of 4 not 6.

you must have made mistake in code : especially in this part B[i][j] - B[i][A[i]] - C[i][j] ā€¦ But, if you code as B[i][j] - B[i][A[i]] - C[i][A[i]] => you will get 6 which is incorrect.

23

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

24

@zmmloser if you are talking about the case given by betlista then asnwer is 6. All the AC solutions also return 6! and i have coded like B[i][j]-B[i][A[i]]-C[i][j]ā€¦not like the other way

25

Try the test cases given here.

Answer should be

46
39
17

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

4 Likes
26

Guys, take a look at my answer. I have seen that almost all programs given above fail in one or two test cases given by me.

1 Like
27

thanks a lot ā€¦i corrected one mistake in the code but it still shows wrong answer
http://www.codechef.com/viewsolution/3443912

28

hi please look at my solution, i am not able to identify where it is failingā€¦tried several test cases and still got required answer
http://www.codechef.com/viewsolution/3371975

29

@rishabh1994 Your sorting method has some bug. I used built in sort method and got TLE. But after converting cin/cout to scanf/printf I could get it AC -> http://www.codechef.com/viewsolution/3444158

1 Like
30

@rishabh1994 I changed your ā€œpartitionā€ method to something that I know and got AC -> http://www.codechef.com/viewsolution/3444179

31

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!

32

thank you so much for the help

33

i did this one using DPā€¦ thought Greedy might give a WA :confused: ā€¦

34

@unavowed Yeah, you are right. Your solution is perfect, but it fails whenever there is at least one extra space or newline character. Fix your get_number() method and you will get AC -> http://www.codechef.com/viewsolution/3449451

1 Like
35

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!!

36

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
37

read about knapsack 0-1. I think it will help

38

I know about 0-1 knapsack. But you canā€™t apply it here because of large constraints

39

@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;
    }
}
40

hello all, shouldnā€™t the delta be like
delta[i]=max(B[i][j],B[i][A[j]]-C[i][j]). I didnā€™t get why is is
B[i][j] - B[i][A[i]]) - C[i][j]. Please help. Thanks