You are not logged in. Please login at www.codechef.com to post your questions!

×

GIT01 - Editorial

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.

This question is marked "community wiki".

asked 12 Dec '17, 20:20

kefaa's gravatar image

6★kefaa
1138
accept rate: 0%

edited 16 Dec '17, 16:31

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.

link

answered 15 Dec '17, 22:27

montycs's gravatar image

0★montycs
1057
accept rate: 0%

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: https://www.onlinegdb.com/SJUSBbtmf

link

answered 02 Jan '18, 18:46

thegreatluka's gravatar image

1★thegreatluka
1
accept rate: 0%

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

link

answered 19 Jan '18, 21:54

rishitha123's gravatar image

2★rishitha123
1
accept rate: 0%

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.

link

answered 05 Apr '18, 16:31

ankush_953's gravatar image

4★ankush_953
657
accept rate: 8%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,680
×1,652
×188
×10

question asked: 12 Dec '17, 20:20

question was seen: 3,419 times

last updated: 05 Apr '18, 16:31