@vijju123 yes, you are right about tom and jerry
I will share my approach to PFRUIT.
The answer can be written as \displaystyle \frac{nu}{de} where de = \displaystyle \prod_{i=1}^n (b_i-a_i+1)^{c_i}
I found a relatively nice closed form for a function g(z) where the coefficient of z^i is \displaystyle \frac{nu_i}{i!} where nu_i is nu for k = i.
\displaystyle g(z) = \frac{\displaystyle \prod_{i=1}^n (e^{(b_i+1)z} - e^{a_iz})^{c_i} }{(e^z-1)^m}
What I did was just calculate this function till k terms to find nu.
However my solution got TLE for the very last test file in subtask 3.
I also am convinced that the intended solution is one where neither m nor any c_i is used to calculate the complexity. Only their value modulo the given prime matters I guess.
If anyone knows this other solution or got AC using my approach please share. 
Also, @vijju123, is this codechefâs way to collect alternate solutions before the editorials are released? 
Oh and did anyone even solve an integral like I did or did you just guess the solution for EQUILIBR ?
2 Likes
Problem :- NMNMX No Minimum No Maximum
My Solution :- https://www.codechef.com/viewsolution/19152448
Verdict :- AC (100)
Execution Time :-0.07 sec.
Explanation :- Question says we need to find product of all subsequences of length k without (max && min) in each of them.Now first of all letâs think to solve the question in required time if it is just to find product of all subsequences of length k.The approach is to find exponent of every number in the final product. Letâs say array ={10,4,8,6,2} & k=3. So,power of 2 = 4 = 6 = 8 = 10 = 4C2 . We can think this as you have to make array of size 3 where one element is fixed whose power you have to calculate. So,out of remaining 4 elements you can choose 2 elements.
Now,the actual problem was not including maximum and minimum in subsequence. So, basically for every number you have to find number of subsequence it will be maximum and minimum.
Letâs go back to same array ={2,4,6,8,10} & k=3.First of all sort the array as it wonât make difference to the answer. Now take element 6.
6 can be maximum only for those subsequence which will lie to the left of 6 in sorted array and similarly 6 can be minimum only for those subsequence which will lie right to 6 in sorted array.
So, in array = {2,4,6,8,10}, power of 6 in maximum case = 2C2 && minimum case = 2C2. Similarly power of 2 in maximum case = 0 & minimum case = 4C2. So,total power of 6 = 4C2-(2C2+2C2) ,2 = 4C2-4C2.
So,you can find all powers of element in O(n) traversal. Now question demand answer modulo(10^9+7).
One thing to know before computing modulo is in x^y modulo M if y is very large then you have to do
y = y modulo (M-1).{I can prove this but you will get detailed info about this on net so please refer to it}. Here, y is power of every element which will be in terms of nCr which will be very large for large test cases. Since M-1 is not prime so you can not apply Fermat theorem directly.
To compute this, I have applied Chinese Remainder Theorem. It basically says in context to nCr that in order to find nCr%p where p is not prime then factorize p into its prime factors and take modulo of each with nCr which is called remainders and apply the theorem. Now if you notice M-1=1000000006 is 500000003*2 ( both primes ). So, our task is easy and just find nCr modulo for both of them and apply the remainder theorem in it. I would suggest to look at my code whose link I have attached above to get better idea how to implement remainder theorem after finding the remainders.
This was my approach, if you find any difficulty in understanding or any suggestion then please do comment.
4 Likes
Thanks for your insight @psaini72 . Lol no, its not a way to collect alternate solutions. Its just a mix of factors which prompted me to make this thread. Like, problem discussion after CF is cool, why not have it at CC as well? Then, editorials arent out and its just after the contest- many high rated coders surf discuss at this time for editorials. I think theyâd love to hear and share approaches as well. The igniting point was, hearing from a friend that âI feel shy sharing my approach - people will feel I am self-publicizing.â- So there you are, why not have a fun thread with alt. soln?
My solution for NMNMX -
First, try solving this problem - https://www.hackerrank.com/challenges/tower-3-coloring/problem
Now, look at my version of problem-
What is the contribution of each element?
Simple! {A_i}^{k} where k= Number of sub-sequences in which A_i is neither max nor min
Now problem boils down to calculating k - which is very easy. To make sure that A_i is neither maximum nor minimum of the sequence, find number of âbad waysâ. If A_i is maximum, it means all elements are picked from elements < A_i, and if A_i is minimum, then it means that all elements are picked from elements >A_i. Count of these elements can be easily obtained by frequency-prefix array.
Now, K=Total Ways-Bad Ways
={n-1 \choose k-1} -{a\choose k-1}-{b \choose k-1}
where a and b are count of elements < A_i and >A_i respectively. Product of contribution of all elements is the answer .
Solution link: https://www.codechef.com/viewsolution/19111524
5 Likes
Can anyone tell me the approach to solve NSA (No String Attached) problem from division 2? Thanks.
modulo is wrong. Refer to my solution.
@vijju123, that is a nice thought and a nice effort on your part. You should also add some of these answers on the actual editorial page ( if you feel they should be ) just to help anyone trying out these problems in the future, because I donât think many people will write another answer on the editorial page.
An unrelated question:
Do you get a notif everytime someone writes @vijju123, or do you just regularly check the forums everyday?
2 Likes
Also, why arenât the editorials released just after ( or a few minutes after ) the contest is over, if, according to https://www.codechef.com/problemsetting, the editorials are finished even before the contest starts?
AFAIK its 50 karma for commenting on otherâs answers. Yes, I will add it in editorial part via links, i.e. something like "Many interesting approaches are also discussed here - ". I cant copy paste their answers - else thatâd mean me getting karma which ideally belongs to them. I can give links to make sure everyoneâs effort is seem
Top solutions will be marked as accepted so that they remain at top always
At every index of the string, if u have the count of each alphabet before and after the current index, you should be able to calculate the cost of replacing current index with 25 other characters.
Now the problem is computing the count. This can be done using partial sums. Think about it.
Time complexity - 26 * O(N)
@psaini72 could you please share your integration idea. I was kind of thinking on similar lines.
I started with n = 2 and tried to find a pattern. For n = 2 the required region is the circumference of a circle centered at origin and of radius k/2. But I was stuck with the denominator. I was thinking like choosing 2 circles whose radii sum upto k. I was stuck on constructing the integral as I was modelling them as discrete structures.
I donât understand your approach that you described in your answer but maybe you should check out my answer to this because I have used the series of e^x there. I can give a brief explanation if you want.
ooooooops . Sorry for typo. Thanks!
Sort pizzerias by position, and construct a segment tree of CHT (each node [L, R] contains a CHT of lines between L and R).
To get the answer for a consumer, you don't need to remove a line from your structure.
Now, supose there are 11 pizzerias, and consumer i doesn't like 3, 7 and 9. To answer this, you should get the minimum of 4 queries: [1, 2], [4, 6], [8, 8] and [10,11]. This works because the sum of forbidden pizzerias is at most 4 * 10^5 and the number of queries is about (N + M). The complexity of the query is log(N)^2 (one log from segment tree and one from CHT).
i had the same idea. but didnt code âŚdamn