COLARR - Editorial

editorial
, , ,
1

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.

2 Likes
2

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

3

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

4

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

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

5

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

6

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

7

Can one cell be repainted multiple times?

8

@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

9

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
10

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

11

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

12

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

13

Call it bad luck, weak test cases whatever, but you agree, that 5 is correct, right?

14

and this is an invalid test case too which doesn’t follow the last constraint

15

in C1 -> C2 -> C3 the cost is a + b, in C1 - > C3 cost is b, how can a + b be less than b if a, b >= 0 ?

16

@betlista no the correct answer is 6 because no repainting is required
P.S. you solution also returns 6

17

Sorry, my bad, I’ll do it better…

18

Oh, my bad. Misunderstood the whole thing. Thanks, mate. :slight_smile:

1 Like
19

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

20

I’m not able to find the smaller one for now only for N = 50 and M = 25 with K = 625. Recently I’m not able to upload to pastebin, will let you know later today.