PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: krrishmath
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given two points A and B in 3D space.
Find the minimum number of moves needed to start at A and reach B, changing one coordinate at a time, but with the same number of move performed at most K times in a row.
EXPLANATION:
Let d_1 = |x_1 - x_2| be the distance that needs to be traveled in the x coordinate.
Similarly define d_2 and d_3 for the other two coordinates.
Note that a lower bound on the answer is certainly (d_1 + d_2 +d _3).
However, this might not always be achievable because of the constraint on moving at most K times in one direction.
Let d_1 \geq d_2 \geq d_3 without loss of generality.
Intuitively, it seems like it’d be a good idea to move in the direction of d_1 several times in a row (up to k), then change direction once by moving either d_2 or d_3, then go back to moving in d_1, and so on.
The number of “direction resets” available to us in this manner is exactly d_2 + d_3.
With d_2 + d_3 resets, d_1 can be reduced by a maximum of (d_2 + d_3 + 1) \cdot k.
This comes from k steps before each reset, followed by k steps after the final reset.
If d_1 \leq (d_2 + d_3 + 1)\cdot k then it is indeed possible to use exactly d_1 + d_2 + d_3 moves and reach the destination.
Proof
There’s a fairly simple construction to do this.
Repeat the following:
- If d_1 - k \gt d_2, move k steps in the direction of d_1.
Then, move one step in d_3 (if it’s positive) or d_2 otherwise.- If d_1 - k \leq d_2, instead move just enough so that d_1 and d_2 become equal, after which simply alternate between d_1 and d_2.
Eventually these two will also equal d_3, at which point you can cycle between all three of them to get everything to 0.If we reach the second stage, we’re all done - so the only concern is how long the first stage will last.
But note that each time d_2 + d_3 is reduced by 1, d_1 is reduced by K.
So, if we ever run out of d_2 + d_3, d_1 must’ve reduced by at least k\cdot (d_2 + d_3).However, we assumed d_1 \leq (d_2 + d_3 + 1)\cdot k, and k\cdot (d_2 + d_3) of that is gone - so at most k steps can remain in the d_1 direction.
These can be taken, and we’re done, as claimed.
If d_1 is too large though, some extra resets are needed.
Note that if we make an extra move in either the d_2 or d_3 directions, we’ll always need one more move to return.
So, each ‘extra move’ made gives us two more resets, but also in reality requires two more moves.
Now, if we want r extra resets, r must satisfy d_1 \leq (d_2 + d_3 + r + 1)\cdot k, to make performing all d_1 moves viable. This gives us a lower bound on r - specifically, the minimum valid value of r will be
where \left\lceil \ \ \right\rceil denotes the ceiling function.
Alternately, this minimum valid r can be found using binary search.
Since the number of extra moves made must be even as noted above, if r_{min} is odd then the number of extra moves made will in actually be r_{min} + 1.
More generally, the answer in this case is
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
int t;
cin>>t;
while(t--){
ll x1,y1,z1,x2,y2,z2,k;
cin>>x1>>y1>>z1>>x2>>y2>>z2>>k;
ll x=abs(x1-x2);
ll y=abs(y1-y2);
ll z=abs(z1-z2);
vector<ll> arr={x,y,z};
sort(arr.begin(),arr.end());
ll a=arr[2],b=arr[0]+arr[1];
if (a<=(b+1)*k) cout<<a+b<<endl;
else{
ll extra_moves=2*((a-(b+1)*k+2*k-1)/(2*k));
cout<<a+b+extra_moves<<endl;
}
}
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll x1,y1,z1,x2,y2,z2,k; cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2 >> k;
ll x = abs(x1-x2), y = abs(y1-y2), z = abs(z1-z2);
vector<ll> v = {x,y,z};
sort(all(v));
x = v[0], y = v[1], z = v[2];
ll s = x+y;
ll ans = x+y+z;
// for every k ops in z, do 1 op in s
ll ops = (z-1)/k;
ll times = (z-1)/k;
s -= times;
if(s < 0){
s = abs(s);
s = ceil2(s,2)*2;
ans += s;
}
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
x1, y1, z1, x2, y2, z2, k = map(int, input().split())
d1, d2, d3 = abs(x1 - x2), abs(y1 - y2), abs(z1 - z2)
mx = max(d1, d2, d3)
have = d1 + d2 + d3 - mx
if mx <= k * (have + 1): print(d1 + d2 + d3)
else:
extra = (mx - k * (have + 1) + k - 1) // k
if extra%2 == 1: extra += 1
print(d1 + d2 + d3 + extra)