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).
Above comment taken from here - Invitation to CodeChef July Long Challenge 2018! - Codeforces had run out of chars.
i had the same idea. but didnt code …damn
Idea is if one of the magnitude is greater than k/2 => then there is no way to get sum of vectors to zero.
Alternatively, if all the magnitude is less than k/2 => There is always a way to get sum to zero.
Since the values can be real magnitude and there is a constraint, the possible values will form a hyperplane. So we need to find, what fraction of this possible solution space will have atmost one dimension greater than k/2.
For first dimension to violate the condition, it can be caluculated using integrals to be 1/2^(N-1), N different directions are there. So answer is 1 - N*(1/2^(N-1))
2 Likes
@psaini72, my approach and formula is same as yours. How do you calculate the terms in denominator of g(z) where the denominator is polynomial? The doubt is what is inverse of polynomial and how to calculate it.
First, I thought of: What is the (geometric ?) condition that given n vectors ( both magnitude and direction ) that their sum is the 0 vector.
Looking at the case for n=3, they can be arranged into a triangle when placing the tail of each at the head of another. Similarly, if n vectors sum to 0, they form a sort of chain. From the head of one to the tail of the next.
1 Like
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
( one which @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.