Now the question becomes, what is the probability that n vectors form a chain ( or a polygon, to be specific ). One necessary condition ( with reasoning similar to the triangle inequality ) is that no segment is greater in length than the sum of the lengths of the other segments. It turns out that this is also a sufficient condition. Just imagine placing the segments one by one. I don’t really have a formal proof here.
Here, if a segment has length l, then the sum of lengths of the other segments is k-l. So, l <= k-l, l <= k/2.
1 Like
Well, I have given you the pattern you wanted to know. I won’t give you the details of the integration I’m afraid :(. Mine was too convoluted comparedd to others Ive seen. Just search for broken stick problem because it is the same as this.
The comment character limit was short so I wrote 3 comments.
1 Like
Insteadd of parabolas, we can transform problem to linear functions. Once we have done that we do CHT sqrt(n) times removing the lines that are in lower envelope. For each query if k_i>=sqrt(n) just iterate through all pizzerias, otherwise iterate through k_i+1 first lower envelopes, find the optimal position without removal and move right and left till we have pizzeria that we can use. Complexity will be O(nsqrt(n)) if we use sqrt(n) pointers and do queries offline. My AC code: wY5eto - Online C++0x Compiler & Debugging Tool - Ideone.com
1 Like
Someone else answered your question at July 18- Problem Discussion - #9 by brij_raj - general - CodeChef Discuss
My approach: If you are considering all subsequences of a sequence, you are also considering subsequences of length 1 i.e. each element. That means, that in a good subsequence, all elements are multiples of m. Also, if every element is divisible by m, then every subsequence is also divisible by m. We have found the sufficient condition: all elements are divisible by m.
If there are c elements in the array divisible by m, answer is all sequences of these elements = 2^c-1.
@vijju123 Yeah it is a maximum clique. Actually maximum cliques can be solved only in exponential time. However this is a special type of graph called chordal graph. Here it is easier to find maximum clique. Refer this page for more details.
1 Like
Got TLE in one subtask with this approach 
( one which @vijju123 shared)
@error_503_404 Check solution to 438 E in Codeforces Round #250 Editorial - Codeforces
One other thing I thought of to deal with this but didn’t implement is to calculate Bernoulli numbers some other way because their generating function is \frac{z}{e^z-1}. Another advantage of doing this is that all other ntt’s I did were of the same size. This can speed up the first ( rearranging ) part of the NTT.
this is same as this comment’s solution I guess As discussed by @vijju123 too… people got AC with same logic…
1 Like
need explanation of problem statement or its 100 points soln ? Please clarify…
I too did using integrals ,equlibrium.
evil(n integrals)
@vijju123 thanks for your efforts, but I’m the same guy who asked it in CF also. BTW could you please ask codechef admins to increase the character limit for comments if possible.
why didn’t u do try to submit using pypy?
my 20 pts solution submitted in pypy fetched me 50 pts 
This problem can also be solved by binary search.
1 Like
Could u please explain your solution?
I didn’t expect pypy to be faster that’s why.
The reason it passed is because the slow speed of pypy has been overcompensated by the time limit increase, but that didn’t come to my mind while solving.
Also, I would have to write A LOT of pypy code from scratch having never written NTT in python before. I think my NTT in c was too slow to pass so I want to improve that first.
yeah no problem , sorry can not comment there a upvote would help 
1 Like
I guess ik the mistake…
#(a-b)%mod != a%mod - b%mod in c++…
use (( a%mod - b%mod)%mod + mod)%mod
retval = (((n + 1 - i) * retval) / i) % (mod - 1);
Are you sure that this product will be completely divisible by i?
1 Like
Because even if we place all vectors ideally (in exact opposite direction to the one with magnitude greater than 1/2), we cannot obtain 0 sum.