Thanks @taran_1407.
@nik_84 There is a trick to verify if the error caused is because of Stackoverflow Error or error in your logic. Catch the Stackoverflow error and write the infinite loop in catch block. If you get TLE it is Stackoverflow error else something is wrong with the code. (Assuming your code is not producing TLE before this test).
I tested this on your code and verified that your error is because of StackOverflowError. CodeChef: Practical coding for everyone
I got to learn this trick from my friend @suparsh14.
1 Like
You fill find a lot of problem getting solutions accepted for harder problems, especially if they require recursion. Study python, make sure you are able to utilise the languages pros according to the Q. Eg- in one of the question I was suffering from overflow despite long long (had to use unsigned long long, but it didnt strike), so I switched to python to get an easy AC.
In harder problems, even correct algo gets TLE. Sometimes the only thing is, you must know and sue the faster languages.
Regarding karma, google out codechefs “New Karma System” blog.
I have trouble understanding the optimization part. Can you correct me where I am wrong?
Let A = \sum_{i=0}^n {a_i x^i} and B = \sum_{i=0}^n {b_i x^i}.
Then coefficient of x^j in A \times B would be \sum_{i=0}^j{a_i b_{j-i}}. and required value is \sum_{j=0}^k{\sum_{i=0}^j{a_i b_{j-i}}}.
Now say A' = \sum_{j=0}^n ({\sum_{i=0}^j{a_i}) x^j} and B' = \sum_{j=0}^n ({\sum_{i=0}^j{b_i}) x^j}.
Now coefficient of x^k in A' \times B' would be \sum_{j=0}^k((\sum_{i=0}^j{a_i})(\sum_{i=0}^{k-j}{b_i})) \neq \sum_{j=0}^k{\sum_{i=0}^j{a_i b_{j-i}}}
@nilesh3105. Thanks for asking a question. I was wrong in my intuition. It is actually A’ X B and not A’ X B’. Also remember to expand A upto kth power where k is the max hamming distance by appending zeros and then form A’. Thanks for asking question. I have edited my answer.
@aayushkapadia Looks consistent now. Nice approach! May I ask, how did you come up with this?(The optimization part).
@nilesh3105 Actually idea of optimization came to my mind when I read official editorial. The FFT part I had already derived during contest. And it will also work because it is just O(NlogN) but when I read official editorial after the contest (especially definitions they have given for fixed and non fixed), it suddenly striked me to optimize using the prefix sum.
thanks again i have implemented it and successfully get AC 
thanks a lot !