Hello Guys, I’m back once again with editorials, hoping you would like them. 
Note: This time, i have put all problems in serial order. 
This is the part 1 of three posts of unofficial editorials for December Long Challenge.
This part would be a bit more detailed than strictly necessary, just to make it crystal clear to new programmers, so i won’t mind if you just skimmed over my editorial without reading line to line.
For editorials of problems CHEFHAM and CHEFEXQ, [click here][1].
For editorial of problem REDBLUE, [click here][2].
This post has editorials for problems GIT01, CPLAY, and VK18.
Problem [GIT01][3]
Problem Difficulty : Cakewalk
Problem Explanation
Given an N*M cake of red and green cherries, find out the minimum cost to make the cake beautiful.
Beautiful cake is the one, where each cherry share side with a cherry of different color.
Solution
The only thing we need to know is that, whatever N and M are given, there exist only two beautiful cakes, both of them having red and green cherries arranged in form of a chess board, with:
- Top left cherry is of green color.
- Top left cherry is of red color.
Once we fix color of top left color, whole cake is determined.
That’s all.
This problem can be solved in O(N*M) time and O(1) extra space. I just used two integers, sum1 for first pattern and sum2 for second pattern. Then i checked if given cherry match pattern for both cases, and where it didn’t match, added replacement cost as given in problem.
Checking for required color is easy. For pattern 1, grid[0][0] = G. So, all grid[i][j] are required to be green if (i+j)%2 == 0. otherwise grid[i][j] should be red.
Similar way goes for Second pattern.
After all this, I guess my solution is straight forward to understand. In case you feel i should clarify any doubt, Just drop a comment.
Here’s a link to my
[4].
### Problem [CPLAY][5]
#
### Problem difficulty: Simple
#
#### Problem Explanation
Given a binary string of length 20 denoting the results of penalty shoot out between chef and his friend, tell who won and also report number of penalty shoot outs required to determine the winner.
#### Solution
The most simple to solve this problem is to just implement as the problem statement explains.
Maintain four variables A = 0 (Number of successful penalties by Team A), B = 0 (Same goes for B), Aturn = 5 and Bturn = 5. (Denoting number of turns left for both teams during first five goals.)
loop for i = 0 to s.length
if(i%2==0){check if s.charAt(i) == '1', A++ and Atrun--, else Aturn--;}
else {if(s.charAt(i) == '1', B++ and Bturn--, else Burn--;}
Now, check if(A > B+Bturn) {Meaning A already scored more goals than B even if B scores in all his remaining turns.} A is the winner and (i+1) is the required turn in the answer. (i+1 due to 0-based indexing).
Same check for B.
if(A == B) we enter sudden death part.
Now, read two characters simultaneously, one for each team and increment if win for respective teams. If, at any time, A != B, Greater of A and B is the winner and 20 - Number of turns is the required answer.
Note, be careful in output format, especially space between Team name and number of turns.
Link to my
[6]
Problem [VK18][7]
Problem Difficulty : Easy
Problem Explanation
We are just given an integer N. We are required to output Total number of diamonds in N*N rooms of Chef’s home (quite big i must say) where number of diamonds in a room is defined as Absolute difference between odd digits and even digits of room Number.
Solution
I am gonna explain this problem Sub-task wise.
First Sub-task: T<=10, N<=1000.
We can simply run two nested loops from 1 to N, getting each room number and finding number of diamonds for each room individually using a sum function like below.
public int sum(int X){
int odd = 0, even =0;
while(X > 0){
if(X%2==0)even+=X%10 else odd += X%10;
X/=10;
}
return Math.abs(odd-even);
}
Add No of diamonds for all rooms and print answer. Time complexity O(N^2).
Second Sub-task: T <= 10, N <= 1e6.
Above solution will give TLE. But just a small observation will give us 20 points.
Observe the way room numbers are defined. if (i,j) denote room location, then (i+j) is the room number (1-based indexing).
For N = 4, all rooms are row 1 => 2,3,4,5; row 2 => 3,4,5,6; row 3 => 4,5,6,7; row 4 => 5,6,7,8
Just see, 2 appear one time, 3 appear two time, 4 appears three times and so on.
A number from 2 to 2N appears min(i-1, 2N - i + 1) for i from 2 to 2*N.
So, just run a loop from 2 to 2*N, calculate no of diamonds in that room number, multiply with number of rooms with that room number and add it to answer. and output. (Don’t forget mod).
Third Sub-task: T<=1e5, N<=1e6
For this sub-task, we need O(1) time for each query, so here comes pre-processing all answer beforehand.
Let us calculate special value V for each i from 2 to 2*1e6, V means Number of diamonds in room number i.
Now, create a sum array of this V array. Just see the following grid for N = 2 and N = 3
N = 2
2 3
3 4
N = 3
2 3 4
3 4 5
4 5 6
See, first four elements remain the same. Just
if ans[i] denote answer when N = i,
ans[i] = ans[i-1] (first four elements in above case) + 2*( sum[2i-1] - sum[i]) (for added row and column, except last element) + V[2i] (last element added only once).
Using this relation and ans[0] = 0, calculate beforehand all solutions and print. We got 100 points.
Here’s a link to my
[8].
I hope you enjoy my editorials as much as you all do like coffee in winters (though i don't) and warm cuddling in quilt in December. :)
Enjoy coding.
[1]: https://discuss.codechef.com/questions/119323/unofficial-editorials-december-long-challengr-part-2
[2]: https://discuss.codechef.com/questions/119325/ds-quad-tree-unofficial-editorials-december-long-challenge-part-3
[3]: https://www.codechef.com/problems/GIT01
[4]: http://codechef.com/viewsolution/16411313
[5]: https://www.codechef.com/problems/CPLAY
[6]: https://www.codechef.com/viewsolution/16402419
[7]: https://www.codechef.com/problems/VK18
[8]: https://www.codechef.com/viewsolution/16410605