Problem Link : Deathly Hallows
Author : Ritesh Gupta
Tester : Romit Kumar
Editorialist : Ritesh Gupta
Pre-Requisite : FFT, GCD, Seive Theory.
Problem : You are given two parallel lines. The first line contains n distinct points on it and the second line contains m distinct points on it. You have to connect each point of the first line to every point of the second line. Now in all the line segments, you have to count the number of pair of segments which satisfy the below-given property.
Let P_{xy} be a line segment which connects a_x point of the first line with b_y point of the second line. Similarly, P_{uv} be a line segment which connects a_u point of the first line with b_v point of the second line. The pair of interaction (P_{xy}, P_{uv}) will favor Harry if they follow certain conditions:
- P_{xy} is parallel to P_{uv}.
- GCD(a_x, b_y) \neq MIN(a_x, b_y) \space or \space GCD(a_u, b_v) \neq MIN(a_u, b_v)
Explanation : First forget about the second condition and find the answer which satisfies the first condition. The two line segment P_{xy} and P_{uv} are parallel when (a_x - b_y == a_u - b_v). Thus all pairs (a_x, b_y) whose difference a_x - b_y will be parallel to each other. For a given difference d, if there are k pairs, number of parallel lines for that difference will be n*(n-1)/2.
All that’s required is to consider all pairs of the given form and count the number the number of pairs for every difference. This could be done naively, however, the time complexity will be O(n^2).
To do this effectively, we need to consider two polynomial corresponding to given parallel lines. First polynomial will be of the form A(x) = a_1x^1 + a_2x^2 + ... + a_nx^n, where a_i is 1 if i_{th} point is an energy point in the orange jet. Similarly, the other polynomial will be of the form B(x) = b_1x^{-1} + b_2x^{-2} + ... + b_nx^{-n}, where b_i is 1 if ith point is an energy point in green jet.
If we multiply these two polynomials, the power of x represents the difference between certain pairs of point and the coefficients represent the count of those pairs. Using this information we can find the required answer. Multiplication of polynomial can be done by fft in O(nlogn).
Now let us consider the second condition in two phases.
-
First, we consider all the line segments P_{xy} in which a_x divide b_y where a_x and b_y belong to first and second line respectively. But we also need to find the count of k-difference line segments for every k from (0,2e5). For that, we create an array A of length 2e5 with the initial value of the elements is zero. Now what we have to do is iterate over points of the first line in increasing order and for every element, we run an inner loop over starting from twice the value of the first line element up to 2e5 with increment it by the integer value of the first line element. If we find a point that corresponds to the positions visited by inner loop then we increment the (x-y) position of the array A where x is the point on the first line and y is the current value of inner loop. After this, we decrease our current answer by k*(k-1)/2 for all k in the array A where k treated as an element.
-
Similarly, we consider all the line segments P_{xy} in which b_y divide a_x where a_x and b_y belong to first and second line respectively and perform the same algorithm as above mentioned.
for(int i=1;i<=200000;i++) { if(a[i]) { for(int j=2*i;j<=200000;j+=i) { if(b[j]) cnt1[j-i]++; } } if(b[i]) { for(int j=2*i;j<=200000;j+=i) { if(a[j]) cnt2[j-i]++; } if(a[i] == b[i]) cnt1[0]++; } } for(int i=0;i<=200000;i++) ans -= (cnt1[i]*(cnt1[i]-1))/2, ans -= (cnt2[i]*(cnt2[i]-1))/2;
Here array a treated as points on the first line and b treated as points on the second line and array cnt1 and cnt2 are used as array A in first and second part respectively. Apart from it, we have to also exclude the count of the pair of line segments in which both line segments are perpendicular to the lines. For which we use third if statements shown in above code sniping.
Time Complexity : O(nlogn + NloglogN) where N = 2e5.
Setter Solution : Link