Given an undirected graph which is a tree with N nodes (N >= 3). You have to select an internal node (nodes with degree >= 2) and calculate the sum of the distance of all non-internal nodes (nodes with degree 1) from that node. You have to print the minimum possible value of the sum. And if possible also print the internal node number which gives you the minimum value. If there are multiple internal nodes which give the same minimum sum to all non-internal nodes print any of them. Can we solve this question in less than O(N^2) time complexity??

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.

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

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 !!

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.

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.