Yellow.Flash's blog

Help needed in google kickstart Round B problem
By Yellow.Flash, history, 8 years ago, In English

I need help in the problem : problem B — center
Someone please share idea on how to solve it.
Thanks

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

»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Note : When weight is 1.
You can do the transformation from X = A + B and then Y = A - B, then and .
Now, we can see that doing this max(X - Xi,  Y - Yi) = max(A' - Ai + B' - Bi, A' - Ai - (B' - Bi)) [where A', B' are the transformations for center given in the problem]. Now we can see that this value is nothing but |A' - Ai| + |B' - Bi|. So this effectively means that we have to find the median of A's, B's independently.
When weight is not necessarily one, what we can do is multiply it by 100 as it given that it's accurate upto 2 decimal places, and can make a pair array of  < Ai, Wi > , sort it and using find the prefix sum, find the first i where prefix sum(i) is

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I know there are 2 approaches:

  1. Do 2 ternary searches. The outer for x coordinate and the inner for y (or vice versa).

  2. Transform the Chebyshev distance to Manhattan distance by rotating and scaling. The find the answer in Manhattan distance. Actually, it is the median, and in the large dataset it is the weighted median.

I used the second approach the solve both cases in the real contest.

→ Reply