Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

back_slash's blog

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

You are given two natural numbers N and K. You need to represent the number N as a product of K numbers such that all the K numbers are >= 2 and the sum of the K numbers is minimum. The constraints on the value of N <= 10^12. Given such values of K for which the answer always exist.

My Solution:- After finding the prime factorization of the number N. Insert the factors in a multiset and then solve the problem greedily. Take the first 2 elements of the multiset, remove them and then insert their product in the multiset. Keep on repeating this process until the size of multiset becomes equal to K.

I don't know whether the above approach is correct or not and also I am not sure whether the answer will be unique or not.

Any suggestions for the given approach or some new approach are welcomed.

UPD:- I know my approach is incorrect but still I am unable to figure out anything about uniqueness. Whether the answer will be unique or not.

Read more »

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

By back_slash, history, 9 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, 12 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, 14 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