EQUALNUMBERS - Editorial

editorial
,
1

Problem link : EQUALNUMBERS

Solution:

[theorem] We are given a set of natural numbers from 1 to N. We can always express any value between 1 and N*(N+1)/2 as sum of elements from 1 to N.
Eg. Given set S = {1,2,3,4,5}. We can express any value from 1 to 15, as a sum of an subset of elements in set S.

Lets say, the absolute difference between A and B be D.
D = |A - B|.

Let the sum of set of first n natural numbers be X.
From the above theorem we can always split the set into two subsets of sum (X - Y) and Y respectively. Y can take any value in the range of [0,X].

So, that being said,
We might go with a solution as,
Find the smallest possible value of N(N+1)/2 which is greater than or equal to D, where N is a natural number.

Does this work? Lets check…

Lets say A = 10, B = 22. Then, D = 12.

Smallest value of N(N+1)/2 which is greater than or equal to 12 is 15(N = 5).
We divide 15 into 13 and 2.
A = 10 + 13 = 23
B = 22 + 2 = 24.
ok, now we divide 15 into 14 and 1
A = 10 + 14 = 24
B = 22 + 1 = 23.

As you might have observed that we are unable to make them equal.An important oberservation to make here is that we can make them equal if both D and N(N+1)/2 have same parity(If D is even, N(N+1)/2 should be even, if D is odd, N(N+1)/2 should be odd).

Lets Try with 28 (N=7).

We divide 28 into 20 and 8.

A = 10 + 20 = 30.
B = 22 + 8 = 30.

A = B. → (N = 7)

Solution:

Let X = N(N+1)/2
D = |A - B|

  1. X > D (From theorem)
  2. X%2 == D%2 (Observation)

Solution Code:
int A,B;
cin >> A >> B;
int X = 1;
int D = abs(A - B);
while((X*(X+1)/2) < D || ((X*(X+1)/2)%2 != D%2 )
{
X++;
}

cout << X << “\n”;

Complete Code: C++14

#include<bits/stdc++.h>
using namespace std;

void solve()
{
	int a,b;
	cin >> a >> b;
	int x = 0;
	int n = 0;
	while(n < abs(a-b) || n%2 != abs(a-b)%2){
		x++;
		n += x;
	}
	cout << x << "\n";
	return;
}

int main()
{
	int t;
	cin >> t;
	while(t--){
		solve();
	}
	return 0;
}

Thank you! : )