PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: munch_01
Preparation: iceknight1093
Tester: mridulahi
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Binary search
PROBLEM:
There are two integers A and B.
You will perform a series of moves on them. On the i-th move:
- If i is odd, add i to either A or B.
- If i is even, subtract i from either A or B.
Is it ever possible to make A equal B?
If so, find the minimum number of moves necessary.
EXPLANATION:
Let D = A-B denote the difference between A and B.
A and B are equal if and only if this difference is 0.
Let’s look at how our operations affect this difference.
- Adding i to A increases D by i.
- Adding i to B decreases D by i.
- Subtracting i from A decreases D by i.
- Subtracting i from B increases D by i.
In other words, on the i-th move we always have the option of either increasing or decreasing D by i; making the even and odd cases symmetric!
Our aim is now to find the smallest integer N such that there’s a way to assign either + or - to every integer from 1 to N such that the resulting expression evaluates to D.
For example, if D = 6, we have N = 3 because 6 = 1 + 2 + 3, whereas if D = 5 we have N = 5 because 5 = 1+2+3+4-5.
First, note that it’s enough to work with non-negative values of D, since if we’re able to attain a sum of D we can also attain -D (by flipping every sign).
So, let’s have D = |A-B|.
Now, with the integers 1, 2, \ldots, N, we get a maximum sum of 1+2+\ldots + N = \frac{N\cdot (N+1)}{2}.
If this is \lt D then it’s obviously impossible to get to D at all.
So, we need to consider only those integers N such that \frac{N\cdot (N+1)}{2} \geq D.
The smallest such N can be found in \mathcal{O}(\log D) using binary search.
However, this N isn’t always enough: as the example with D = 5 above shows, even though 1+2+3 \geq 5 it’s not possible to get to exactly 5 with just those three numbers, and we need to go all the way to N = 5.
If you analyze why, you’ll see that this is because of parity.
Specifically, our aim is to start with 1+2+\ldots + N, then flip some of the signs to negative to reach D.
However, if we change +x to -x, the overall change in the sum is -2x, an even number.
So, if D has a different parity from (1 + 2 + \ldots + N), it’s definitely impossible to reach D by flipping some signs.
On the other hand, if they have the same parity it’s always possible to do so.
So, our objective is to find the smallest integer N such that:
- \frac{N\cdot (N+1)}{2} \geq D and
- D has the same parity as \frac{N\cdot (N+1)}{2}.
Let N_0 be the smallest integer such that \frac{N_0\cdot (N_0+1)}{2} \geq D (as noted earlier, this can be found using binary search).
The answer is then one of \{N_0, N_0 + 1, N_0 + 2\} so just test the parity criterion for all three and take the smallest one that works.
TIME COMPLEXITY:
\mathcal{O}(\log |A-B|) per testcase.
CODE:
Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
#define int long long
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) {
int a, b;
cin >> a >> b;
int d = abs(a - b);
int l = 0, r = (int)1e5;
while (l < r) {
int m = (l + r) / 2;
int x = m * (m + 1) / 2;
if (x >= d) r = m;
else l = m + 1;
}
int x = l;
if (x * (x + 1) / 2 % 2 == d % 2) {
cout << x << "\n";
continue;
}
x++;
if (x * (x + 1) / 2 % 2 == d % 2) {
cout << x << "\n";
continue;
}
x++;
if (x * (x + 1) / 2 % 2 == d % 2) {
cout << x << "\n";
continue;
}
}
}
Editorialist's code (Python)
def calc(n): # smallest x such that 1+2+...+x >= n
lo, hi = 0, 10**5
while lo < hi:
mid = (lo + hi)//2
if mid*(mid+1)//2 < n: lo = mid+1
else: hi = mid
return lo
for _ in range(int(input())):
a, b = map(int, input().split())
d = abs(a - b)
ans = calc(d)
while d%2 != (ans*(ans+1)//2)%2: ans += 1
print(ans)