GIT01 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Gitesh Narula
Tester: Mugurel Ionut Andreica
Editorialist: Kirill Gulin

PROBLEM

You’re given a cake in a form of the N \times M matrix. Each cell of the cake can be either red or green. The cake is considered correct if any two adjacent cells of the matrix are different. You can change any green cell of the given cake to red in 3 units of penalty and red to green in 5 units. Determine the minimum penalty you need to make your cake correct.

QUICK EXPLANTION

Notice there are only two different correct cakes. Try each one and choose the one with the minimum penalty.

EXPLANATION:

Look at the top left cherry. It can be either red or green. If the color of the top left cherry is determined then it is easy to see the first row of the cake is determined uniquely, or more precisely, two adjacent cherries have different colors. Again, if the cherries of the first row are determined, then the second row is also uniquely determined. Moreover, if the cherry in a certain column of the first row is determined, then the cherry in the same column of the second row has a color different from the color of the cherry in the first row. In the same way, the remaining rows of the cake can be uniquely restored.

Therefore, there are only two different correct cakes: the first one with a green top left cherry and the second one with a red top left cherry. Try each one, count the penalty required and choose the best one.

The implementation itself is not hard. Firstly, read the input cake as two-dimensional array of characters. Create another one such array and fill it in the next way. Set its top left cell as green, for example. After that, fill the remaining characters of the first line in such a way that each two adjacent cherries are different. In the similar way, fill the remaining rows of the cake, with the cherry in the first column different from the cherry in the row above. Set variable for penalty and initialize it as zero. Then go over each cell of the created cake and check whether the corresponding cell of the input cake has different color. If so, add 3 or 5 to the penalty depending whether the input cell is green or red respectively. Do the same one more time, setting the top left cell as red.

There is a shorter implementation without creating any extra matrixes, but using the parity of the cell’s row and column sum.

Total time and memory complexity: O(NM).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

2

Why is there no solution from either author or editorialist? Can anyone post their solution along with required comments. I am feeling a bit ashamed of not able to understand this simple problem.

3

Can anyone please tell me what am i missing here. I’m creating 2 posssible matrices based on the input and comparing them while iterating row-wise and column-wise.

Here’s my code:

4

#include<stdio.h>
int main()
{
int T,n,m,i,j;
scanf("%d",&T);
while(T–)
{
int cost1=0,cost2=0;
scanf("%d%d",&n,&m);
char str[n][m];
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if((i+j)%2==0)
{

if(str[i][j]==‘G’)
{
cost 1++ = 3;
}
else
{
cost 2++ = 5;
}
}
else
{
if(str[i][j] ==‘R’)
{
cost 1+=5;
}
else
{
cost 2+=3;
}
}}}
if(cost1<cost2)
{
printf(’%d\n",cost 1);
}
else
{
printf("%d\n",cost 2);
}
return 0;
}

5

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

int main()
{
ll t,m,n,i,ans,diff1,diff2,sumR,sumG;
scanf("%lld",&t);
char a;
while(t–)
{
sumR = 0,sumG = 0;
scanf("%lld %lld",&m,&n);
for(i=0;i<m*n;i++)
{
cin >> a;
switch(i%2)
{
case 0:
if(a==‘G’)
sumR += 3;
else if(a==‘R’)
sumG += 5;
break;
case 1:
if(a==‘G’)
sumG += 3;
else if(a==‘R’)
sumR += 5;
break;
}
}
printf("%lld\n",min(sumR,sumG));
}

return 0;

}

Can you please spot the error in my program ?? I think it’s good to go but getting wrong answer.