July 18- Problem Discussion

general
,
41

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
42

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

43

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
44

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
45

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
46

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: https://ideone.com/wY5eto

1 Like
47

Someone else answered your question at https://discuss.codechef.com/questions/131430/july-18-problem-discussion/131446

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.

48

@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
49

Got TLE in one subtask with this approach :frowning: ( one which @vijju123 shared)

50

@error_503_404 Check solution to 438 E in http://codeforces.com/blog/entry/12513

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.

51

https://www.codechef.com/viewsolution/19243665
https://www.codechef.com/viewsolution/19244713

Here are my implementation for pizza delivery… got TLE in only 1 subtask for 100 points… Can anyone help in making it more efficient to pass ???

I made a segment tree with each segment containing a Convex hull trick of lines which that segment contain…

Difference between these solution is cht…

1 Like
52

this is same as this comment’s solution I guess As discussed by @vijju123 too… people got AC with same logic…

1 Like
53

Thank you @sdssudhu

54

Can any one Explain NSA(No string attached) problem of july long challenge 2018?

1 Like
55

need explanation of problem statement or its 100 points soln ? Please clarify…

56

INTUITIVE APPROACH FOR EQUILIBR (with very basic maths) -

Couple of observations here -

  1. Forces are balanced when they form closed polygon

If a1, a2, … are sides of polygon and sum of sides is k,
the polygon is possible only when none of the sides is greater than k/2

***PROOF*** - 

*For n sides to form a closed polygon, sum of any n-1 sides should be greater than the remaining one side 

i.e, X1 < X2 + X3 + ... + Xn		

since X1 + X2 + ... + Xn = k, substituting value of RHS in above equation 

X1 < k - X1 

2X1 < k 

X1 < k/2
  1. Lets try to compute probability of loosing here

A key observation is that only one of the vectors can be given length greater than k/2

(thats because sum of other n-1 is itself less than k/2 because total sum is k)

  1. So if we fix vector 1 to have side greater than k/2 and probability of loosing turns out to be p,
    then,
    Probe of winning = 1 - n*p

(thats because there are n options to fix a vector that will have side greater than k/2)

So the problem can be solved if we find p in step 3

To find p, vector 1 needs to have magnitude greater than k/2. Lets give vector 1 a magnitude of k/2
After the we have k - k/2 = k/2 magnitude left to be divided into n vectors

This problem is equivalent of following -

Consider a number line of [0, k] with segment [0, k/2] being blocked (because given to first vector)
What is the probability of putting n-1 cuts such that all cuts lie in (k/2, k] segment

If we think logically putting each of these (n-1) cuts is independent of one another (infinitely many real numbers between any range)

Also probability of a cut lying in second half of a number line is 1/2

Hence p = (1/2) ^ (n-1)

Answer to problem = 1 - n * [ (1/2) ^ (n-1) ]

The answer here turns out to be independent of k which perfectly makes sense.

This is because k here is the length of our line segment here and the cuts are real numbers.
Since the number of REAL numbers between [a,b] and [c,d] is same (infinite), the length of line doesn’t matter here

12 Likes
57

I too did using integrals ,equlibrium.

evil(n integrals)

58

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

59

Regarding Pdeliv:

for case k_i=0,

for each i,

we want min(p_j+(x_j-x_i)^2)

1<=j<=m

where x_j is position of pizzeria,x_i is position of ith customer.

=min(p_j+x_j^2+x_i^2-2*x_j*x_i)

=x_i^2+min((p_j+x_j^2)+(-2*x_j)*x_i)

Ohk so this basically forms equation of line mx+c,where m=(-2*x_j),c=(p_j+x_j^2)

So this now becomes the basic convex hull trick.

Just add all lines(by taking all pizzerias),and lets say i want the ans for the i_{th} customer,so just query the convex hull ds with x_i,lets say it returns val,so ans for ith customer is x_i^2+val

Now when k_i!=0,it means we dont want to add these lines for calculating answer for i_{th} customer.

let m=7

let d[i]:2,5

So we ans for i_{th} customer is just min(ans for pizzerias from [1:1],[3:4],[6:7])

So basically now we would like to want to query for a range[l:r],like whats the minimum value for a particular x,when the set contains only lines from l to r.

This can be done using segment tree,where each node,contains a convex hull solver(just making up the name,dont know what i should call) for the lines in that range.

Note: Regarding TL,it was very strict,so Li-Chao segment tree,and set strategy didn’t work for me.There is an offline method of doing convex hull trick which works in O(1)(or rather O(n) summing all queries),which basically processes line in decreasing order of slopes or something like this,just google it ,u’ll find that.

my solution:

https://www.codechef.com/viewsolution/19134059

5 Likes
60

Can someone please provide me with the approach both brute and optimal for NSA problem or an algorithm for the same?
Thank you in advance

1 Like