back_slash's blog

By back_slash, history, 3 months ago, In English,

Hello Everyone, Chef And Interval Painting was one of the most interesting problem of March Long. I am writing this blog for 2 main reasons listed below.

  1. I am having a hard time in understanding the editorial. And the interesting thing is I haven't even reached to the harder part of the editorial yet i.e. the NTT part. I can't understand the DP relation that they have written in the first statement. How can we say that the number of ways for exactly r colors to be visible at the end won't depend on the choice of colors which are visible? According to me because we are coloring in a specific order which can't be changed, I think it should depend on the choice of colors. It would be great if someone can provide a better approach to arrive at the solution or if someone has a different DP relation that can be used to solve the problem.

  2. The second reason is during the contest I was able to figure out a DP relation which can be used to solve the problem in O(N^2) time. But obviously, I was not able to convert that approach to a better complexity. So, I wanted to share my approach and if anyone can provide a suggestion on is it possible to apply NTT to my approach or not.

So basically, the approach which I used was dp[N][K] will denote the number of distinct coloring of an array of size N after K rounds and the only twist is coloring a subarray of size 0 is also a valid round.

So, the relation would be fairly simple

The basic logic used is same that start from reverse and coloring a subarray of any size in some round X won't affect the coloring in the previous i.e. (X-1)th round. And the final answer for some value of N,K will be

Ans[N][K] = dp[N][K] - dp[N][K - 1];

I don't know if the above relation can be solved in less time complexity or not. But any suggestion related to the problem are welcomed.

Thanks !!

Read more »

  • Vote: I like it  
  • +11
  • Vote: I do not like it  

By back_slash, history, 6 months ago, In English,

I need help with the following question.

UPD: There is a misprint in the question. For the second constraint, it is the constraint of K. That is, the value of 0 <= K <= 2*10^10.

UPD2: It would be great if someone can provide a correct approach to the question, codechef has not published any official editorial for the regional questions.

Read more »


By back_slash, history, 9 months ago, In English,

I am writing this blog mainly for 2 reasons. One is to discuss the problems. I want to know what is the logic behind C Large. And also if we can get a count of how many people got full points in the round.

Read more »

  • Vote: I like it  
  • +25
  • Vote: I do not like it