For each element of the array, count how many times it is written down.

Sort the array A[] = {a₁, a₂, ..., a_n}

, we need to compute a_i^x_i

x_i is the number of subsequences in which a_i is included but not as the Min. nor the Max.

let's compute y instead, where y is the number of subsequences where a_i is the Min. or the Max.

which is choosing all other k - 1 numbers from left or right respectively.

brute force for every possible pair of number such that pair(a,b) is smallest and largest numbers in the sequence of length k and use the combnatorial formula as MeshOmarYasser mentioned. You can calculate nCr by precomputing binomial table by recurrence nCr = (n-1Cr-1+ n-1Cr)% (p-1) where p is 1e9+7

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).

The problem in simpler terms is the probability of forming an n-gon with n non-negative real side lengths such that their sum is constant(k).

Note: In order to form a polygon, the all side lengths must be less than k/2.

Ans: 1 — n/(2^(n-1))

Can you provide an explanation for your 50 point solution?

Consider the multinomial theorem. Try writing (A1+A2+...+An)^k as product of n polynomials.

This can be written as product of e^(Aix). The coefficient of x^k is what we are looking for. To handle A,B,C.. a little thinking gives us that answer is simply coefficient of x^k in product of ( sum of e^ix where i goes from Ai to Bi ).

The sum is a GP sum..the rest is just log,exp,inverse of polynomials.

You can use lagrange interpolation for computing it in O(N * K^2). Consider the function f(n, p) = 1^p + 2^p + ... + n^p. It can be proved that f(n, p) is a p + 1 degree polynomial in n. For example, 1 + 2 + .. + n = n(n + 1) / 2, 1^2 + 2^2 + ... + n^2 = n(n + 1)(2 * n + 1) / 6. Now for each p, you can interpolate this polynomial using only O(p + 1) values. And you can compute this value for n values in O(n * p). But still it won't solve your problem for large k.

Check this discussion in codechef