http://codeforces.com/contest/685/problem/C
Summary:
Find the minimum point M (x, y, z) in Z^3 such that the maximum Manhattan distance between M and a set of points {(x[i], y[i], z[i]) in Z^3} of size <= 100000 is the minimum. Manhattan distance between two points (x, y, z) and (a, b, c) is defined as |x-a| + |y-b| + |z-c|. Furthermore, x, y and z is in [-10^18, 10^18].
Solution:
The crazy thing about this problem is that it is solvable using binary search! It is always surprising to learn that such a fundamental technique can be applied in non-obvious ways.
The binary search idea is this: for a given V, if |x - x[i]| + |y - y[i]| + |z - z[i]| <= V for all i [where (x[i], y[i], z[i]) is a point in the block] is satisfiable for some (x, y, z), then it will also be satisfiable for larger V. Furthermore, if it is not satisfiable for a certain V, then it is also not satisfiable for lower values of V. This monotonic property can be exploited by cutting in the middle of the search space of V and check if we can eliminate the lower half or upper half of the search space depending whether current value of V is satisfiable. If we can check for the satisfiability in O(n) for a given V, we can solve the problem in O(n log V).
The hard part is now to check for the satisfiability of the inequality. The main observation to tame the absolute terms is to look at the lower dimension |x- a| + |y - b| <= V. If you draw the graph you will notice that the region that satisfies that inequality is inside a square defined by 4 points (a-V, b), (a, b-V), (a+V, b), and (a, b+V). This square also be seen as the area of intersection of 4 half spaces defined by the 4 lines along the sides of the squares. Equipped with this intuition, we can see that for the case of |x-a| + |y-b| + |z-c| <= V, the set of points that satisfy the inequality is nothing more than an octahedron defined by 8 half spaces defined by the sides of the octahedron. We can combine the inequalities for each pair of parallel sides of the octahedron into an inequality, and we can rewrite the original inequality into the following form:
a+b+c-V <= x + y + z <= a+b+c+V and
-a+b+c-V<= -x + y + z <= -a+b+c+V and
a-b+c-V <= x - y + z <= a-b+c+V and
a+b-c-V <= x + y - z <= a+b-c+V.
If we rewrite A = x+y+z, B = -x+y+z, C = x-y+z, and D = x+y-z, we can rewrite the above as
a+b+c-V <= A <= a+b+c+V and
-a+b+c-V<= B <= -a+b+c+V and
a-b+c-V <= C <= a-b+c+V and
a+b-c-V <= D <= a+b-c+V,
where x = (C+D)/2, y = (B+D)/2, and z = (B+C)/2.
Using this formulation, we can check for satisfiability in a linear time. First, we iterate through all the points in the block and for each point we update the ranges of A, B, C, and D that can possibly satisfy the original inequality. Eventually we will arrive at a final range of values for each of them. Next we see if the ranges are actually valid, i.e. each of them are non-empty. If any of them are empty, we conclude that the original inequality |x-a| + |y-b| + |z-c| <= V for all (a, b, c) points in the block is not satisfiable. Otherwise, we have to check further. Since A = B+C+D, we must make sure that the minimum and maximum possible value for B+C+D have some intersections with range of values of A. We will be done if x, y, z are allowed to be real number, however since we are working in integer space, we must check further. since x = (C+D)/2 can only be integer if C and D are of the same parity, we must have C = D mod 2. Similarly for y and z, we can conclude that B = C = D mod 2. Furthermore, A will also have the same parity with B, C and D since A = B+C+D = D mod 2. Hence we have two cases, either A, B, C, D are even or odd. For each cases, we check the ranges of A, B, C, and D that is of that parity and see if A and B+C+D intersect. If they intersect, we can conclude that the original inequality is satisfiable.
Now, since the problem requires as to output a point that could gives us the minimum V, we have to add one more logic. Given the ranges of A, B, C and D that can satisfy the inequality, first pick the smallest possible B, C and D. Then from B to D, we increase its value to maximum possible until we see that B+C+D is larger than or equal to lower bound of A, but not larger than its upper bound. We can then output x, y and z based on the final B, C, and D.
One thing to note, you may have to perform additional rearrangement and checks in order to avoid arithmetic overflow in the problem. Hence the implementation can get a little bit obscure.
Implementation:
#include <cstdio> #include <algorithm> #include <iostream> using namespace std; constexpr int64_t MLLONG_MIN = -4e18; constexpr int64_t MLLONG_MAX = 4e18; int n; int64_t a[100010][3]; int64_t c[4][3] = { {1, 1, 1}, {-1, 1, 1}, {1, -1, 1}, {1, 1, -1} }; inline int Mod2(int64_t v) { return (v%2LL + 2) % 2; } bool IsSatisfiable(int64_t v, bool get_point=false, int64_t* result=nullptr) { int64_t ranges[4][2]; for (int i=0;i<4;++i){ ranges[i][0] = MLLONG_MIN; ranges[i][1] = MLLONG_MAX; } for (int i=0;i<n;++i){ for (int j=0;j<4;++j){ ranges[j][0] = max(ranges[j][0], c[j][0]*a[i][0]+c[j][1]*a[i][1]+c[j][2]*a[i][2]-v); ranges[j][1] = min(ranges[j][1], c[j][0]*a[i][0]+c[j][1]*a[i][1]+c[j][2]*a[i][2]+v); } } for (int i=0;i<4;++i){ if (ranges[i][0] > ranges[i][1]) return false; } for (int res=0;res<2;++res){ int64_t filter[4][2]; for(int i=0;i<4;++i){ filter[i][0] = MLLONG_MIN; filter[i][1] = MLLONG_MAX; } bool is_consistent = true; for(int i=0;i<4;++i){ filter[i][0] = max(filter[i][0], Mod2(ranges[i][0]) == res ? ranges[i][0] : ranges[i][0]+1); filter[i][1] = min(filter[i][1], Mod2(ranges[i][1]) == res ? ranges[i][1] : ranges[i][1]-1); if (filter[i][0] > filter[i][1]) { is_consistent = false; break; } } if (!is_consistent) continue; if (filter[0][1]-filter[1][0]<filter[2][0]+filter[3][0] || filter[1][1]+filter[2][1]<filter[0][0]-filter[3][1]) continue; if (get_point) { int64_t sum = 0; int64_t point_out[3]; for(int i=0;i<3;++i){ point_out[i] = filter[i+1][0]; sum += point_out[i]; } if (filter[2][0]+filter[3][0]>=filter[0][0]-filter[1][0]) { result[0] = (point_out[1]+point_out[2])/2LL; result[1] = (point_out[0]+point_out[2])/2LL; result[2] = (point_out[0]+point_out[1])/2LL; return true; } for(int i=0;i<3;++i){ if (sum >= filter[0][0]) break; sum -= point_out[i]; if (sum > filter[0][1] - filter[i+1][1]) { int64_t X = filter[0][1]; if (Mod2(X) != (Mod2(filter[i+1][0])+Mod2(sum))%2) { X--; } point_out[i] = X-sum; sum = X; break; } else { point_out[i] = filter[i+1][1]; sum += point_out[i]; } } result[0] = (point_out[1]+point_out[2])/2LL; result[1] = (point_out[0]+point_out[2])/2LL; result[2] = (point_out[0]+point_out[1])/2LL; } return true; } return false; } void Solve() { int64_t lo=0, hi=4e18, mid; while (lo<=hi){ mid = lo + (hi-lo)/2LL; if (IsSatisfiable(mid)) { hi=mid-1LL; } else { lo=mid+1LL; } } int64_t ans[3]; IsSatisfiable(lo, true, ans); for(int i=0;i<3;++i){ cout << ans[i] << " "; } cout << endl; } int main(){ int tc; scanf("%d",&tc); for(int t=0;t<tc;++t){ scanf("%d",&n); for(int i=0;i<n;++i){ cin >> a[i][0] >> a[i][1] >> a[i][2]; } Solve(); } return 0; }
No comments:
Post a Comment