PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: John Smith
Tester: Radoslav Dimitrov
Editorialist: Jelmer Firet
DIFFICULTY:
HARD
PREREQUISITES:
- Shortest path in tree via lowest common ancestor
- Binary search
- Using Heuristics
PROBLEM:
Consider the following graph:
The graph has a vertex for each pair (x,y) where x and y are odd co-prime integers, and y is positive.
A vertex (a,b) has four edges, namely:
- (a,b) - (a+2b,b),
- (a,b) - (a-2b,b),
- (a,b) - (a,b+2a) or (a,b) - (-a,-(b+2a)) depending on which has positive y-coordinate,
- (a,b) - (a,b-2a) or (a,b) - (-a,-(b-2a)) depending on which has positive y-coordinate.
Determine the minimum distance between two vertices of this graph.
QUICK EXPLANATION:
Define the value of a point (x,y) as |x|+y. Then each point has exactly one neighbor that has a smaller value than itself (except (\pm 1,1)). Therefore the graph is a tree, which we root at (1,1). We find the LCA of the two points using a binary search over the value of vertices along the path. This can be done fast by evaluating multiple edges at once. Finally we compute the distance between both via the LCA.
EXPLANATION:
Warning: 10^{15} will not fit into an 32-bit integer, so 64-bit integers need to be used. In my code ll is a 64-bit integer.
Redefining the problem
I find the definition of the north and south road confusing, especially since sometimes the north road goes down and the south road goes up. Instead I will use the following definitions:
- Road north leads to (x,y+2|x|)
- Road east leads to (x+2|y|,y)
- Road south leads to (x,y-2|x|)
- Road west leads to (x-2|y|,y)
Sometimes the south road ends up in a place with a negative y-coordinate. Instead of flipping the sign of both coordinates I will just consider (x,y) and (-x,-y) as equivalent. We can define this equivalence in C++ as follows:
struct pos
{
ll x,y;
// custom equality operator
friend bool operator==(const pos& lhs, const pos& rhs) {
if (lhs.x == rhs.x and lhs.y == rhs.y) return true;
if (lhs.x == -rhs.x and lhs.y == -rhs.y) return true;
return false;
}
// Custom inequality operator
friend bool operator!=(const pos& lhs, const pos& rhs) {
return not (lhs == rhs);
}
};
Shortest path to the center
We shall first look at a simplification, namely (x_2,y_2)=(1,1). This will allow us to develop techniques that we can extend to the full problem. Intuitively we only want to make moves that gets us closer to the center. I will use taxicab distance (|x|+|y|) as an estimate of how far we are from the centre, though other estimates may work as well. The points with an equal taxicab distance form a diamond. We then observe that for each point there is exactly one point that gets us a smaller taxicab distance.
As we can see from this image one of the roads goes into the diamond, two go the entire wrong direction and one jumps over the diamond. I’ll leave it up to you to check why this is always the case. You may also notice the two diagonal lines trough the center. These split the plane in 4 quarters, which decides which of the roads gets us inside the diamond. If we are in the north quarter, we need to take the south road. In east quarter → take west road etcetera. I will leave it as an exercise for the reader to explain why.
We now know how to find a path to the center, just follow the roads that get us closer to the center. Is this the shortest path? As it turns out it is the only simple path to the center. If we take a road from village u to v that increases the taxicab distance then v\to u is the only road from v that makes the taxicab distance smaller again. Therefore any roads that increase are taxicab distance also are going to be traversed the other way. But we can now make an interesting conclusion about the village graph: it is a tree!
Tracing optimisations
Knowing how to find the shortest path to the centre is not enough however, the maximum coordinate 10^15 is too big to go to the center road by road. We need to evaluate multiple roads at once. To figure out what we can speed up I encourage you to look at the following two starting villages: (1001,1) and (1001,999). These give us two ways to evaluate the paths quicker
The first way is rather obvious, if we go in the same direction multiple times after each-other, we can just simplify that into one operation. We only need to look at how far we could move in a particular direction. Suppose we start in the east quadrant and move west. By making only taking west roads while in the east quadrant we can reach any village in the blue shaded region of the image above. This allows us to calculate the number of steps west we can take: divide the distance between our point to the unshaded triangle by the size of each step:
\#\text{steps}=\frac{x+|y|}{2|y|}
The other way is less obvious, we can speed up when spiraling inwards. In the image above we see 4 spirals. Red is the original spiral, and yellow,green,blue are the same spiral but rotated 90°, 180° and 270° clockwise. As we can see from the black arrows the points of the spirals line up on diagonals. We can use this to predict where the point k moves in is, namely follow k diagonal arrows (each decreasing both coordinates by x-y) and then undo rotations by rotating k\cdot 90 degrees counter-clockwise. We can continue this spiraling optimization while y is positive, otherwise we need to start spiraling the other direction. So we can speed up for k at most 1+\lfloor\frac{y}{x-y}\rfloor.
As it turns out these two optimizations are enough. In the worst case we need to apply \log(10^{15}) times a linear or spiraling move, which will definitely fit within the time limit. Therefore we now can calculate the cost of traveling to (1,1) in logarithmic time. It’s time to look again at the original problem
Back to the original problem
In the previous sections we made two important conclusions:
- The graph is a tree
- We can speed up tracing the path to the center to logarithmic time
If you have experience with shortest path queries on trees, you would know that they often involve finding the lowest common ancestor. The lowest common ancestor is the first common point on the paths from (x_1,y_1) and (x_2,y_2) to the centre. Then the distance between (x_1,y_1) and (x_2,y_2) is exactly the distance from (x_1,y_1) to the LCA plus the distance from (x_2,y_2) to the LCA. Finding the LCA is often the most difficult part of such a problem.
I will reintroduce the taxicab distance from earlier. Note that if the LCA has taxicab distance d, then all points on the path (x_1,y_1)\to(1,1) with taxicab distance \leq d are also on the path (x_2,y_2)\to(1,1). Similarly the points with greater distance are not shared between the two paths. This suggests a binary search on d to find the LCA.
Let’s define this binary search more concretely. Define p_1(d) to be the first point on the path from (x_1,y_1) to (1,1) with taxicab distance \leq d. Similarly define p_2(d) for the path from (x_2,y_2). I will explain how to calculate these in logarithmic time later. Now if we consider the distance d. Then if p_1(d)=p_2(d) we will next consider every distance at least d. On the other hand if p_1(d)\neq p_2(d) we will only consider distances less than d as the paths have not converged yet. If you are observant you might note that we are not actually searching the taxicab distance of the LCA here, but of the villages just before.
How do we find p_1(d) and p_2(d)? We modify our fast tracing technique from last section so that we return the first village that ends up inside the diamond |x|+|y|\leq d. For the spiraling movements we reduce the number of steps we make so that we stay outside of the diamond, as we don’t want to accidentally skip past the first village in the diamond. For the linear moves we reduce the number of steps so that we also don’t skip past the first village in the diamond. Both modifications are simple because we can easily calculate the taxicab distances of where we would end up in k moves.
Summary of the algorithm
We binary search for the taxicab distance of the lowest common ancestor. For each distance d we check whether the paths from both villages to the center have merged before or after the boundary d. We do this by finding p_1(d) and p_2(d), the first village within the diamond |x|+|y|\leq d on the paths from (x_1,y_1) and (x_2,y_2) respectively. We find these in logarithmic time using the linear and spiraling optimizations we discovered in the simpler version. When we find the LCA we use the same optimizations to calculate the distances from both villages to the LCA, and add these together to find the distance from (x_1,y_1) to (x_2,y_2).
The complexity of this algorithm is \mathcal{O}(\log(\text{max coordinate})^2), which is fast enough.
ALTERNATE SOLUTIONS:
In this algorithm we use |x|+|y| as a distance from the center. Different distance formula’s work as well.
The setter (John) for example didn’t extend the plane and used y as the distance heuristic.
The tester (Radoslav) used a different approach for finding the LCA. Instead of using binary search to find the LCA you extract the “compressed” paths from the simpler problem. These compressed paths further subdivide the spiraling optimization to be able to consider single edges. Then remove the overlapping parts of those paths so that the paths to the LCA remain. Calculate the lengths of both remaining paths and you have the answer.
SOLUTIONS:
Setter's Solution
//
// Village Road Network
//
//
#include <bits/stdc++.h>
using namespace std;
// Each Village has co-ordinates (p,q), where q > 0 and (p,q) are odd and co-prime. p may be positive or negative.
//
// Each Village is connected to 4 neighbours
// North road to (p, q+2p) or (-p, -(q+2p)) chosen that the new q co-ordinate is positive
// South road to (p, q-2p) or (-p, -(q-2p)) chosen that the new q co-ordinate is positive
// East road to (p+2q, q)
// West road to (p-2q, q)
// These definitions lead to a undirected graph. But the Geometry is not a regular grid.
// The length of each road between two adjacent villages is always 1.
//
// The road system actually forms a tree, so there is a unique path between any two villages.
// The problem is to find the distance between two villages (p1,q1) and (p2,q2)
//
// We can write a table of village co-ordinates:
// (-9,1) (-7,1) (-5,1) (-3,1) (-1,1) (1,1) (3,1) (5,1) (7,1) (9,1)
// (-9,3) (-7,3) (-5,3) (xxxx) (-1,3) (1,3) (xxx) (5,3) (7,3) (9,3)
// (-9,5) (-7,5) (xxxx) (-3,5) (-1,5) (1,5) (3,5) (xxx) (7,5) (9,5)
// (-9,7) (xxxx) (-5,7) (-3,7) (-1,7) (1,7) (3,7) (5,7) (xxx) (9,7)
// (xxxx) (-7,9) (-5,9) (xxxx) (-1,9) (1,9) (xxx) (5,9) (7,9) (xxx)
//
// and identify the central triangle of villages (p,q) where |p| < q
//
// (-1,1) (1,1)
// (xxxx) (-1,3) (1,3) (xxx)
// (xxxx) (-3,5) (-1,5) (1,5) (3,5) (xxx)
// (xxxx) (-5,7) (-3,7) (-1,7) (1,7) (3,7) (5,7) (xxx)
// (xxxx) (-7,9) (-5,9) (xxxx) (-1,9) (1,9) (xxx) (5,9) (7,9) (xxx)
//
// The East-West roads connect across the table (though not adjacent villages in the table)
// At each village, one of the North-South roads connect up and down, the other connects diagonally
// across the table.
// Inside the central triangle, one North-South road leads down, one diagonally up and across.
// For example:
// South from (-3,5) leads to (-3,11)
// North from (-3,5) leads to ( 3, 1)
// Outside the central triangle, one North-South road leads down, one road is diagonally down and across.
// For example:
// South from (-5,3) leads to (-5,10)
// North from (-5,3) leads to ( 5, 7)
//
//
struct Village
{
int64_t p; // positive or negative
int64_t q; // is always positive
Village( int64_t pp=1, int64_t qq=1 ) : p(pp), q(qq) {
if (q<0) {
p = -p;
q = -q;
}
}
};
bool operator <(const Village &v1, const Village &v2)
{
if (v1.p < v2.p) return true;
if (v1.p > v2.p) return false;
if (v1.q < v2.q) return true;
return false;
}
bool operator !=(const Village &v1, const Village &v2)
{
if (v1.p != v2.p) return true;
if (v1.q != v2.q) return true;
return false;
}
bool operator ==(const Village &v1, const Village &v2)
{
if (v1.p != v2.p) return false;
if (v1.q != v2.q) return false;
return true;
}
/*
* Four functions to do n steps of North, south, east, or west
* but under the important assumption that we do not trigger
* the sign flip excpet possibly on the last step
*/
Village north( Village v, int64_t n=1 )
{
return Village( v.p, v.q+2*v.p*n );
}
Village south( Village v, int64_t n=1 )
{
return Village( v.p, v.q-2*v.p*n );
}
Village east( Village v, int64_t n=1 )
{
return Village( v.p+2*v.q*n, v.q );
}
Village west( Village v, int64_t n=1 )
{
return Village( v.p-2*v.q*n, v.q );
}
/*
* Do n steps of south, then east when starting and ending
* and always being in the central triangle with |p| < q
*/
Village south_east( Village v, int64_t n=1 )
{
if (0)
{
/* slow implementation */
while (n--)
{
v = south(v);
v = east(v);
}
return v;
}
else
{
int64_t d = v.q-v.p;
Village vv(v.p-2*n*d, v.q-2*n*d);
return vv;
}
}
Village north_west( Village v, int64_t n=1 )
{
if (0)
{
/* slow implementation */
while (n--)
{
v = north(v);
v = west(v);
}
return v;
}
else
{
int64_t d = v.q+v.p;
Village vv(v.p+2*n*d, v.q-2*n*d);
return vv;
}
}
/* Simple gcd function */
int64_t gcd( int64_t x, int64_t y )
{
if (x < 0) x=-x;
if (y < 0) y=-y;
if (x<y) return gcd(y,x);
if (x%y == 0) return y;
return gcd(y,x%y);
}
/*
* Really slow solver, and in most cases runs out of memory
*/
int64_t solve_slow( int64_t p1, int64_t q1, int64_t p2, int64_t q2 )
{
int64_t d=0;
set<Village> s;
s.insert( Village(p1,q1) );
while (s.find( Village(p2,q2) ) == s.end())
{
set<Village> ss;
for (auto v : s)
{
ss.insert( north(v) );
ss.insert( south(v) );
ss.insert( east(v) );
ss.insert( west(v) );
}
s=ss;
d++;
}
return d;
}
/*
* Faster solver: (but still too slow)
* we work upwards towards (p,q) where q=1, until the villages have the same q, and can reach
* one another using East-West moves
*/
int64_t solve_faster( int64_t p1, int64_t q1, int64_t p2, int64_t q2 )
{
Village v1(p1,q1);
Village v2(p2,q2);
int64_t d=0;
while (v1 != v2)
{
if (v2.q > v1.q) swap(v1,v2);
if (v1.q == 1 && v2.q == 1)
{
d += abs(v1.p-v2.p)/2;;
break;
}
if (v1.q == v2.q)
{
int64_t dd = abs(v1.p-v2.p)/2;
if (dd%v1.q == 0)
{
d += dd/v1.q;
break;
}
}
// v1 has the larger q value, so choose road to reduce q
if (v1.p > v1.q)
{
/* move towards central triangle */
v1 = west(v1);
d++;
}
else if (v1.p < -v1.q)
{
/* move towards central triangle */
v1 = east(v1);
d++;
}
else if (v1.p > 0)
{
/* move so as to reduce q */
v1 = south(v1);
d++;
}
else
{
/* move so as to reduce q */
v1 = north(v1);
d++;
}
}
return d;
}
/*
* Don't think this function gets used
*/
tuple<Village, int64_t> advance_to_triangle( Village v )
{
int64_t c=0;
while (v.p < -v.q)
{
v = east(v);
c++;
}
while (v.p > v.q)
{
v = west(v);
c++;
}
return make_tuple( v, c );
}
// step towards a village with v.q == 1
// stop on last occasion that v.q > q0;
// this is a slow implementation
tuple<Village, int64_t> find_last1( Village v, int64_t q0 )
{
int64_t c=0;
Village vv;
while (v.q > q0 && v.q > 1)
{
if (v.p > v.q)
{
vv = west(v);
}
else if (v.p < -v.q)
{
vv = east(v);
}
else if (v.p > 0)
{
vv = south(v);
}
else
{
vv = north(v);
}
if (vv.q <= q0) break;
v = vv;
c++;
}
return make_tuple( v, c );
}
// step towards a village with v.q == 1
// stop on last occasion that v.q > q0;
// this is a fast implementation
tuple<Village, int64_t> find_last2( Village v, int64_t q0 )
{
int64_t c=0;
Village vv;
while (v.q > q0 && v.q > 1)
{
/* if v.p is slightly less than v.q, then a south step followed by an east step
* will reduce v.p and v.q by 2(v.q-v.p)
* So we can do n steps very quickly
*/
if (v.p > 0 && v.p < v.q)
{
int64_t d = v.q - v.p;
int64_t n = (v.q - q0-1)/(2*d);
if (n > 1)
{
n--;
vv = south_east( v, n );
v = vv;
c += 2*n;
}
}
/* if v.p is negative, and slightly larger (closer to 0) than v.q, then do
* north and east steps */
if (v.p < 0 && -v.p < v.q)
{
int64_t d = v.q + v.p;
int64_t n = (v.q - q0-1)/(2*d);
if (n > 1)
{
n--;
vv = north_west( v, n );
v = vv;
c += 2*n;
}
}
int64_t n = 1;
if (v.p > v.q)
{
n = (v.p+v.q)/(2*v.q);
vv = west(v,n);
}
else if (-v.p > v.q)
{
n = (-v.p+v.q)/(2*v.q);
vv = east(v,n);
}
else if (v.p > 0)
{
n = (v.q-q0-1)/(2*v.p);
if (n == 0) n = 1;
vv = south(v,n);
}
else
{
n = (v.q-q0-1)/(-2*v.p);
if (n == 0) n = 1;
vv = north(v,n);
}
if (vv.q <= q0) break;
v = vv;
c += n;
}
return make_tuple( v, c );
}
tuple<Village, int64_t> find_last( Village v, int64_t q0 )
{
return find_last2(v,q0);
}
int64_t solve_fastest( int64_t p1, int64_t q1, int64_t p2, int64_t q2 )
{
// q1 and q2 should always be positive
assert(q1 > 0);
assert(q2 > 0);
Village v1(p1,q1);
Village v2(p2,q2);
int64_t cost = 0;
// v1 and v2 are are on a tree, which we think of as being rooted at (1,1)
// Move v1 and v2 up the tree towards the root until reaching (roughly) the lowest common
// ancestor. But because there may be many steps, we sort of do an interval
// bisection process
int64_t qmin = max(q1,q2);
int64_t qlo = 0;
int64_t qhi = qmin;
while ((v1.q != v2.q || abs(v1.p-v2.p)%(2*v1.q) != 0) &&
qhi != qlo)
{
int64_t m = (qhi+qlo)/2;
Village vv1;
Village vv2;
int64_t cost1;
int64_t cost2;
tie( vv1, cost1 ) = find_last( v1, m );
tie( vv2, cost2 ) = find_last( v2, m );
if (vv1 == vv2)
{
/* too far - increase lo limit */
qlo = vv1.q;
}
else if (vv1.q == vv2.q &&
abs(vv1.p-vv2.p) % (2*vv1.q) == 0)
{
/* same row, and villages now reachable by east-west roads */
cost += cost1+cost2;
v1 = vv1;
v2 = vv2;
break;
}
else
{
/* Not far enough - reduce qhi limit and try again */
v1 = vv1;
v2 = vv2;
cost += cost1+cost2;
qhi = m;
}
}
if (v1.q == v2.q &&
abs(v1.p-v2.p) % (2*v1.q) == 0)
{
cost += abs(v1.p-v2.p) / (2*v1.q);
return cost;
}
/* only a very few more steps will bring them onto the same row */
while (v1.q != v2.q)
{
if (v1.q > v2.q)
{
int64_t cost1;
tie( v1, cost1 ) = advance_to_triangle( v1 );
cost += cost1;
if (v1.p > 0)
{
v1 = south(v1);
cost++;
}
else
{
v1 = north(v1);
cost++;
}
}
if (v2.q > v1.q)
{
int64_t cost2;
tie( v2, cost2 ) = advance_to_triangle( v2 );
cost += cost2;
if (v2.p > 0)
{
v2 = south(v2);
cost++;
}
else
{
v2 = north(v2);
cost++;
}
}
}
/* and some east-west moves will bring the villages to the LCA */
if (v1.q == v2.q &&
abs(v1.p-v2.p) % (2*v1.q) == 0)
{
cost += abs(v1.p-v2.p) / (2*v1.q);
return cost;
}
cout << "Shouldnt get here" << endl;
exit(1);
return 0;
}
int64_t solve( int64_t p1, int64_t q1, int64_t p2, int64_t q2 )
{
// return solve_slow(p1,q1,p2,q2);
// return solve_faster(p1,q1,p2,q2);
return solve_fastest( p1, q1, p2, q2 );
}
int main( int argc, char ** argv )
{
ios_base::sync_with_stdio(false);
int64_t limit = 1e16;
uint32_t T;
cin >> T;
while (T--)
{
int64_t p1,q1,p2,q2;
cin >> p1 >> q1 >> p2 >> q2;
if (p1 % 2 == 0 ||
q1 % 2 == 0 ||
p2 % 2 == 0 ||
q2 % 2 == 0)
{
cerr << "Error something not odd" << endl;
exit(1);
}
if ( gcd(p1,q1) != 1 ||
gcd(p2,q2) != 1 )
{
cerr << "Error = not coprime" << endl;
exit(1);
}
if (q1 < 0 || q2 < 0)
{
cerr << "Error - q1 or q2 not positive" << endl;
exit(1);
}
assert( q1<limit );
assert( q2<limit );
assert( abs(p1)<limit );
assert( abs(p2)<limit );
int64_t d1 = solve(p1,q1,p2,q2);
//cout << T << " ";
cout << d1 << endl;
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define endl '\n'
#define SZ(x) ((int)x.size())
#define ALL(V) V.begin(), V.end()
#define L_B lower_bound
#define U_B upper_bound
#define pb push_back
#define y1 gdskjgisdjglksdjglksdj
using namespace std;
template<class T, class T1> int chkmin(T &x, const T1 &y) { return x > y ? x = y, 1 : 0; }
template<class T, class T1> int chkmax(T &x, const T1 &y) { return x < y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
int64_t x1, y1, x2, y2;
void read() {
cin >> x1 >> y1 >> x2 >> y2;
}
void erase_path_to_lca(stack<pair<int64_t, int64_t> > &p1, stack<pair<int64_t, int64_t> > &p2) {
while(!p1.empty() && !p2.empty() && p1.top().second == p2.top().second) {
auto e1 = p1.top();
auto e2 = p2.top();
p1.pop();
p2.pop();
// Might have only half an edge in common
if(e1.first < e2.first) {
p2.push({e2.first - e1.first, e2.second});
} else if(e1.first > e2.first) {
p1.push({e1.first - e2.first, e1.second});
}
}
}
// ~ Euclid complexity
stack<pair<int64_t, int64_t> > get_path_root(int64_t x, int64_t y) {
stack<pair<int64_t, int64_t> > ret;
bool need_swap_root = false;
if(x < 0) {
need_swap_root = true;
x = -x;
}
while(!(x <= 1 && y <= 1)) {
if(x >= y) {
if(x > 2ll * y) {
int64_t steps = x / (2ll * y);
x -= steps * (2ll * y);
ret.push({steps, 0});
} else {
int64_t delta = x - y;
int64_t steps = y / delta;
x -= delta * steps;
y -= delta * steps;
if(steps % 2 == 0) ret.push({steps, 2});
else {
ret.push({steps, 3});
need_swap_root ^= 1;
swap(x, y);
}
}
} else {
if(y > 2ll * x) {
int64_t steps = y / (2ll * x);
y -= steps * (2ll * x);
ret.push({steps, 1});
} else {
int64_t delta = y - x;
int64_t steps = x / delta;
x -= delta * steps;
y -= delta * steps;
if(steps % 2 == 0) ret.push({steps, 3});
else {
ret.push({steps, 2});
need_swap_root ^= 1;
swap(x, y);
}
}
}
}
if(need_swap_root) ret.push({1, 4});
return ret;
}
void solve() {
stack<pair<int64_t, int64_t> > path_1 = get_path_root(x1, y1);
stack<pair<int64_t, int64_t> > path_2 = get_path_root(x2, y2);
erase_path_to_lca(path_1, path_2);
int64_t ans = 0;
while(!path_1.empty()) {
auto x = path_1.top();
path_1.pop();
ans += x.first;
}
while(!path_2.empty()) {
auto x = path_2.top();
path_2.pop();
ans += x.first;
}
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while(T--) {
read();
solve();
}
return 0;
}
Editorialist's Solution
#include <iostream>
#include <algorithm>
using namespace std;
// int64_t to fit 10^15
typedef int64_t ll;
// Contains the two coordinates of a village
// Compares (x,y) and (-x,-y) as equivalent.
struct pos
{
ll x,y;
ll dist() {
return abs(x)+abs(y);
}
// custom equality operator
friend bool operator==(const pos& lhs, const pos& rhs) {
if (lhs.x == rhs.x and lhs.y == rhs.y) return true;
if (lhs.x == -rhs.x and lhs.y == -rhs.y) return true;
return false;
}
// Custom inequality operator
friend bool operator!=(const pos& lhs, const pos& rhs) {
return not (lhs == rhs);
}
};
// moves the variable at value a distance of diff towards zero
// goes past zero if diff > abs(value)
void moveToZero(ll &value, ll diff) {
if (value > 0) {
value -= diff;
} else {
value += diff;
}
}
// updates village to the first point on the path from village to (1,1)
// that is inside the diamond |x|+|y| <= d
// the number of steps from village to this point is returned
// (the village is updated as it is passed by reference)
ll moveInsideDiamond(pos &village, ll d) {
ll totalSteps = 0;
while (village.dist() > d) {
// --- Spiral movements ---
// Suppose x>y>0, then moving west and rotating the grid 90° clockwise
// results in a point on the same diagonal.
// So we calculate the point on the diagonal after $k$ steps, and undo rotation.
// calculate how much both coordinates change in each step
ll stepSize = abs(abs(village.x) - abs(village.y));
// Calculate distance we can move diagonally to the boundary
ll dist = min(abs(village.x), abs(village.y));
// Calculate how many diagonal moves after each other are on the path to the center
ll steps = 1 + dist / stepSize;
// Adjust steps so that we don't step into the diamond
steps = min(steps, (village.dist()-d) / (2 * stepSize));
// move to the new village
moveToZero(village.x, steps * stepSize);
moveToZero(village.y, steps * stepSize);
//rotate if an odd number of steps
if (steps % 2) {
swap(village.x, village.y);
village.y *= -1;
}
totalSteps += steps;
// --- Linear movements ---
// maximum steps in one direction before needing to turn
stepSize = 2*min(abs(village.x),abs(village.y));
// maximum distance before needing to turn
dist = village.dist() - 1;
// calculate the number of steps we can take before needing to stop
steps = dist/ stepSize;
// if we encounter the diamond we need to stop after stepping into/over it
if (stepSize <= d) {
steps = min(steps, (dist-d+stepSize) / stepSize);
}
// move to the new village
if (abs(village.x) > abs(village.y)) {
moveToZero(village.x, steps*stepSize);
} else {
moveToZero(village.y, steps*stepSize);
}
totalSteps += steps;
}
return totalSteps;
}
int main() {
int numCase;
cin >> numCase;
while (numCase--) {
ll x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
pos p1 = {x1,y1}, p2 = {x2,y2};
// binary search to find the least common ancestor
ll low = 2, high = 2e15;
ll steps = 0;
while (low+1 < high) {
// this formula is more overflow-resistant than (low+high)/2
ll middle = low + (high-low)/2;
pos lca1 = p1, lca2 = p2;
ll steps1 = moveInsideDiamond(lca1, middle);
ll steps2 = moveInsideDiamond(lca2, middle);
if (lca1 == lca2) {
// paths to center have joined → LCA is higher
low = middle;
} else {
// paths to center have not joined → LCA is lower
high = middle;
// updating steps and p1,p2 now makes future binary search iterations quicker
steps += steps1;
steps += steps2;
p1 = lca1;
p2 = lca2;
}
}
// Find the lengths of the paths to the LCA
steps += moveInsideDiamond(p1, low);
steps += moveInsideDiamond(p2, low);
// crossover (1,1) - (-1,1)
if (p1.dist() == 2 and p1 != p2) {
steps++;
}
cout << steps << endl;
}
return 0;
}