i found the formula of COUNTIT thats solve the Problem in O(k) but i cant simplify it in O(n) or something like that… so 100 marks obtain…
tell me the real solution how to simplify the formula or tell me the correct approach…
my solution:- CodeChef: Practical coding for everyone
1 Like
Not the toughest mathematical problem if you know FFT
1 Like
@anon55659401
Can u share something so that i can read it and understand how to solve this problem.
I was also unable to turn o(k) into O(m+n). Please somebody discuss their O(m+ n) approach.
1 Like
I’ve seen the interpolation solution but how do you do it with fft?
Isn’t COUNTIT a problem totally based on combinatorics.However,I tried to build up some matrices but couldn’t figure out any pattern or so.PLEASE HELP!!!
1 Like
Use lagrange interpolation (its O(n^2) but you can make it O(n) for this special case)
Lagrange's Interpolation - GeeksforGeeks
https://www.codechef.com/viewsolution/24832230
3 Likes
can you explain how to use fft ??
PS : I see lots of factorial and stuff so think its still tough maths in @jtnydv25 soln
Congratulations for those 6-stars <3 …As I already said you will be 6 this time B-) . Now, please write a post for us newbies on how to improve
1 Like
XD I am still a newbies like you
Guys, @l_returns haS turned 6, dream has come true <3
1 Like
I found O(k) formula using pattern XD
1 Like
Please can you tell me the category under which such topics fall so as to study them or should i learn by going through such questions only.
2 Likes
Since the formula is \sum _{k=0} ^{K} (k^m-(k-1)^m)(k^n-(k-1)^n)
If we write the inner part as a polynomial in k (Which we can do by just expanding it from the binomial theorem formula) we just need to find \sum _{k=0} ^{K} k^i for all i from 0 to m+n.
The fft is used for \sum _{k=0} ^{K} k^i part as we can find that using bernoulli numbers (Faulhaber’s formula). The formula and method for the same is mentioned here. Counting sums of powers - Codeforces. I used the method he mentioned in his reply to the first comment which convolves A and B (can use fft again for this, refer the post for what’s A and B). For the code to find Bernoulli numbers fast you can refer to MAY18A editorial for the problem SERSUM : SERSUM - Editorial (reupload). This is mentioned in the codeforces blog but this editorial has a clearer and longer explanation.
Interpolation solutions seem way simpler though.
6 Likes
In my submission I have put up a comment about how to solve the problem, I did it with FFT. The links there will be good enough. Give it a read, here. CodeChef: Practical coding for everyone
2 Likes