atlasworld's blog

By atlasworld, history, 11 months ago, In English,

Maroof is visiting a new city. Being a Mathematician, he does not like to visit different places but visit places differently. The city has N places to visit. We are given the (X,Y) co-ordinates of the places to visit. Maroof wants to start from a random place i and want to go to a random place j. But he involved a little maths in his procedure. Following are his demands:

He will give a number A. Now, the place i and place j should be such that the line connecting these two points must have the Ath maximum slope (There are total N*(N-1)/2 possible slopes among all the unordered places pairs).

Input arguments to your function:

  1. Integer A

  2. B : An integer array containing X-coordinates of the places

  3. C : An integer array containing Y-coordinates of the places

Note that the length of B (= N) will be equal to the length of C and the ith point is represented by (B[i], C[i]).

Output: An array having exactly 2 elements : numerator and denominator of the slope (fraction should not be further reducible).

Additional instructions:

  1. Places can be overlapping (Two places can have same (X,Y) co-ordinates)

  2. Overlapping places must not be considered as same places.

  3. In case the line joining the places is vertical, slope is -INF.

  4. Two overlapping places have slope -INF.

Constraints:

1 <= A <= 70

1 <= N <= 100,000

-10^9 <= B[i], C[i] <= 10^9 (Also X and Y coordinates can only be Integers)

Example:

Input: A = 2

B = [1, 2, 3, 1, 2] //X coordinates of the places

C = [2, 4, 6, 2, 3] //Y coordinates of the places

Output:

ans = [2,1].

Sorted Points = [(1,2), (1,2), (2,4),(2,3),(3,6)]

SortedSlopes: [3, 2, 2, 2, 2, 2, 1 , 1, -INF, -INF]

Output instructions:

  1. Output fraction should not be further reducible [e.g. Reduce (6,4) to (3,2) before returning the answer]

  2. In case the answer is negative infinity, return (-1,0)

  3. In case the answer is zero, return (0,1)

  4. In case the answer is negative, numerator must be negative. [e.g.: (-3,2) not (3,-2) ]

Any idea how to solve it in linear or linear log time.

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Instead of copying the problem Statement, copy the problem link and paste here. Otherwise how will the community know it's not from an ongoing Contest.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its not from any contest. Its an interview problem.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any approaches for it, how should i proceed?

»
11 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Lmao. If no one wants to answer your post, what makes you think that bumping will help? It is just going to annoy people into giving you downvotes.

»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

You can binary search it. To count how many pairs are before some ratio $$$\frac{a}{b}$$$, sort points in increasing order by both $$$x$$$ and $$$ax - by$$$. Keep a segment tree for changing value at position and prefix sum. Initialize the segment tree to the number of different values of $$$ax - by$$$, and initialize the $$$j$$$'th position to the number of points that have $$$ax - by$$$ equal to the $$$j$$$'th value.

Loop points by x-coordinate. If the current point is the $$$j$$$'th value in the array sorted by $$$ax - by$$$, decrement the value at the $$$j$$$'th position in the segment tree, then add the prefix sum up to $$$j$$$ to your answer. This counts the number of points s.t. the angle to them from the current point is at least $$$\frac{a}{b}$$$.

Once you have an accurate enough estimate for the angle (rational number with divisor larger than it can be for any of the actual ratios), do the same again, but also check for every point the previous active one in the segment tree, and take the ratio to that point as the offer, then return the minimum of the offers.

Time complexity is $$$O(n log^{2} n)$$$ since you binary search and do $$$n log n$$$ work inside it. This doesn't use the fact that $$$A \leq 70$$$ so there might be better ways to do this.

Note that some specifics could be wrong, geometry problems often have a ridiculous amount of corner cases and it's hard to know without coding the solution whether it works for sure.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks, i will implement your solution. i understood the approach.

»
11 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Another way of solving this problem is using point-line duality. In particular, mapping (a, b) -> y = ax — b turns lines connecting two points into points at the intersection of two lines, and vice versa. This means that your problem becomes: given an envelope of lines, find the intersection between a pair of lines that has the k-th smallest x coordinate.

To solve this new problem, we can once again binary search on the answer, but now our task becomes to find the number of pairwise intersections between N lines that occur before some given x coordinate. This can be reduced to inversion counting, so the total time complexity is O(N log^2 N).

»
7 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Hint: **** What if the question is to find the maximum slope? How would you find the maximum slope in O(nlogn) ?

Spoiler: It is not related to using any special data structure or algorithm. There is a special property about the maximum slope that you can exploit.

Come on, draw a diagram and figure it out!

Solution Approach **** Let’s say we sort the points according to their X coordinates (sort by decreasing Y coordinates in case of a tie). Now, it so is the case that maximum slope would always be between two adjacent points (This can be proved by contradiction where you can assume that the maximum slope is not between adjacent points and then show that there exist at least one adjacent point pair that has slope greater than our calculated slope).

Note that we sorted by decreasing Y-coordinates in case of a tie so that the slope between two adjacent points Pi and Pi+1 would always be -Infinity and not Infinity. Thus our slope varies between (-INF <= slopes < INF).

Exercise: Can you prove that if we take K continuous points in the sorted order and find all the slopes (of all the pairs in those K points) then Kth maximum would be one among those values (Kth maximum value among all such slopes).

e.g. K = 3, sortedPoints = [P1, P2, P3, P4, P5] In this case, it would suffice if we find the 3rd max value among the all the slopes between pairs in the point sets [P1,P2,P3], [P2,P3,P4], [P4,P5,P6]. In other words, slope between (P1 and P4) or (P1 and P5) can never be 3rd maximum.