Unofficial editorial December long challenge

Hello Guys, I’m back once again with editorials, hoping you would like them. :slight_smile:

Note: This time, i have put all problems in serial order. :smiley:

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:

  1. Top left cherry is of green color.
  2. 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. :slight_smile:

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
6 Likes

How did you decide on O(1) time query in the third sub-task, which naturally points to pre-processing ?
BTW, Nice and explanatory editorial!
Thanks a lot.

Thankyou for your post, happy coding.
Cheers!!

output of
1

3 4

RRGG
RGRG
GGRR

output -

GRGR

RGRG

GRGR

According to me must be 8 (5+3)
but all top solution is 16

EXPLANATION -

In fist row ,replace first R by last G gives 5

then In third row ,replace second G by third R gives 3,
Hence 5+3=8

I DONT UNDERSTAND WHY ?

@taran_1407 can you explain the third subtask where you added 2( sum[2i-1] - sum[i]) I understood adding of the first and the third term but why the above one?

1 Like

@taran as a beginner i want to know how you compared the cake in GT101 with chess board ? i mean there is no word of chess board used in question ? i submitted around 5 to 7 solutions but WA . What made you thing it is a chess board ? again thanks in advance

@taran_1407 i have implemented vk18 as stated but i am getting WA for 2 and 3 test case

link to My solution:-https://www.codechef.com/viewsolution/16556308

I tried doing a similar approach but don’t understand where I went wrong. Can you help?
The link is https://www.codechef.com/viewsolution/16530358

Nicely explained!
I was stuck on the problem Total Diamonds [VK18]. I kept looking for patterns to develop a formula in order to establish my O(1) solution; apparently I was looking in the wrong direction altogether.

For CHEFEXQ: Chef and easy XOR Queries, i wrote a blog post which can help you guys understand square root decomposition. Blog post link.

I wonder, but I have WA in VK18 and still can’t catch where are principial differ of my code and solution idea, except I has’t optimaze it.
I try different kinds of debug output, but cannot fix what’s wrong. Its seems correct, but WA appears anyway.

Here is link to my solution https://www.codechef.com/viewsolution/16540692.

Can you explain why you used the condition ((i + j)&1 == 1) in GIT01

For pre-processing you will need to declare array of size V[2000000], but my compiler (C++11) gives segmentation fault. How to solve this issue?

This is my solution for CPLAY. https://www.codechef.com/viewsolution/16567845 Can someone check and tell me why its giving Wrong Answer?

I was stuck on the Vk18 since 2 days, I had solved the question as you did in subtask-2, but I always wondered about finding a formula or pattern to get a O(1) solution for the 3rd subtask. So as a beginner is it always allowed to pre-process answer or only when there is no other way (how to find that there is no other way and you need to preprocess??)
btw thanks for the editorial!

1 Like

@taran_1407 can u please check this code https://www.codechef.com/viewsolution/16521944
FOR GIT01

I can’t believe but I used the exact same approaches for all the 3 problems and in 3rd question, I solved it subtask wise only, i.e. the same approaches explained for each subtask by you.

When you have 1e5 test cases to answer, you would find it really common to pre-process in such a way that we can answer our queries in O(1) or O(logN). Otherwise we’ll get TLE.

I just solved the problem for all values from 1 to 1e5, answering queries int O(1).

Cheers!! Happy Coding…

Well, I’m glad that we are not in for plagiarism accusation then… :smiley:

3 Likes