I need help in the problem : problem B — center
Someone please share idea on how to solve it.
Thanks
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | adamant | 155 |
4 | cry | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
I need help in the problem : problem B — center
Someone please share idea on how to solve it.
Thanks
Name |
---|
Note : When weight is 1.
and
. ![](https://espresso.codeforces.com/697bda9c42bbff81a82ebddf3d5ba4ea7cab6b48.png)
You can do the transformation from X = A + B and then Y = A - B, then
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
I know there are 2 approaches:
Do 2 ternary searches. The outer for x coordinate and the inner for y (or vice versa).
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.
Can you share the code for the second approach? I got WA using the 2nd one on large dataset during the contest.
https://ideone.com/IYRunA