RED0-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Arun Sharma
Tester: Lavish Gupta, Abhinav sharma, Takuki Kurokawa
Editorialist: Devendra Singh

DIFFICULTY:

1627

PREREQUISITES:

None

PROBLEM:

Chef has two integers X and Y. Chef wants to perform some operations to make both X and Y zero simultaneously. In one operation, Chef can either:

  • set X := 2 \cdot X
  • or set Y := 2 \cdot Y
  • or set X := X - 1 and Y := Y - 1

Chef is a little busy with preparing the contest. Help him find the minimum number of operations required to make both X and Y equal to 0 simultaneously. If it is impossible to do so after any number of operations, print -1.

EXPLANATION:

First of all let X\leq Y (since the operations are symmetric with respect to X and Y we can swap them if we want). Now there are several cases in this problem. Let us deal with them one by one:

  • X=0 and Y=0: No more operations are needed as we have already achieved the goal of making both X and Y equal to 0 simultaneously.
  • X=0 and Y>0: X can’t be increased by multiplying it by 2 and if we perform an operation of type 3, X will become negative and always remain negative and thus X and Y can’t be made 0 simultaneously in this case. The answer for this case is -1.
  • X>0 : It is always possible to make X and Y equal to 0 simultaneously in this case. The answer for this case cannot be less than Y as Y only decreases in the third operation and each operation of type 3 decreases Y by just 1. The number of operations of type 3 decrease X and Y by same value. Therefore X has to be made equal to Y at least once during all the operations. Now It can be shown that its always better to increase X using the first operation until X becomes equal to Y or X<Y<2\cdot X.
Increase X using the first operation until X becomes equal to Y or X<Y<2*X

Let us suppose we perform K operations of type 3 before we perform an operation of type 1 and let D=Y-X, we want to make D=0 as soon as possible, After K operations of type 3 and then an operation of type 1, D decreases by (Y-X)-(Y-K-2*(X-K)) = X-K, Suppose we perform the operation of type 1 before these K operations of type 3, then D decreases by Y-X-(Y-2*X) = X. Thus it is optimal to first perform operations of type 1 as much as possible and then perform operations of type 3.

Let a be the number of operations of type 1 performed until X>=Y. The answer can not be less than a+Y. If X becomes equal to Y after a operations then the answer is exactly a+Y. Otherwise we increase X to first a value such that X<Y<2\cdot X.

We can observe that after some operations of type 3 we can make (new Y)=2*(new X)

Analytically: Let b be number of operations of type 3 such that new values of Y becomes twice of new value of X, then we have Y-b=2*(X-b)
This gives us b=2\cdot X-Y which is positive and also less than X (so X does not become 0 after applying these operations)
Intuitively: X<Y<2\cdot X. After each operation of type 3, Y and X decrease by 1 and 2\cdot X decreases by 2, overall the difference Y and 2\cdot X decreases by 1 after each operation and hence they must become equal after some operations.

We perform a-1 operations of type 1 on X and then perform b(=2\cdot X-Y) operations of type 3 and then 1 more operation of type 1 to make X and Y equal and then keep performing operations of type 3 until they are simultaneously 0.
Answer in this case is a-1+b+1+Y-b=a+Y.

TIME COMPLEXITY:

O(log(max(X,Y)) for each test case.

SOLUTION:

Setter's solution
#include <bits/stdc++.h>


using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>

#define ll long long int

#define ld long double
#define forn(i, x, n) for (ll i = x; i < n; i++)
#define fornb(i, n, x) for (ll i = n; i >=x; i--)
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
#define MOD 1000000007
#define MAX 300007
#define endl "\n" // REMOVE in lleraction problem
#define debug cout << "K"
vector<ll> visited(MAX), color(MAX), dist(MAX, -1);
vector<ll> graph[MAX];
vector<ll> parent(MAX);
vector<pii> graph2[MAX];


bool sortbysecasc(const pair<ll, ll> &a,
                   const pair<ll, ll> &b)
{

    if (a.first == b.first)
    {
        return a.second > b.second;
    }
    else
        return a.first < b.first;
}



struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

ll isKthBitSet(ll n, ll k)
{
    if (n & (1ll << (k)))
        return 1;
    else
        return 0;
}

// Function to return LCM of two numbers
long long lcm(ll a, ll b)
{
    return (a / __gcd(a, b)) * b;
}

ll log_a_to_base_b(ll a, ll b)
{
    return log(a) / log(b);
}



bool isPrime(ll n)
{
    // Corner case
    if (n <= 1)
        return false;

    // Check from 2 to square root of n
    ll v = sqrt(n);
    for (ll i = 2; i <= v; i++)
        if (n % i == 0)
            return false;

    return true;
}

long long moduloMultiplication(long long a,
                               long long b,
                               unsigned long long mod)
{
    long long res = 0; // Initialize result

    // Update a if it is more than
    // or equal to mod
    a %= mod;

    while (b)
    {
        // If b is odd, add a with result
        if (b & 1)
            res = (res + a) % mod;

        // Here we assume that doing 2*a
        // doesn't cause overflow
        a = (2 * a) % mod;

        b >>= 1; // b = b / 2
    }

    return res;
}

ll largestPower(ll n, ll p)
{   ll x = 0;

    while (n)
    {
        n /= p;
        x += n;
    }
    return x;
}

ll power(ll x, ll y, ll p)
{
    ll res = 1; // Initialize result
    x = x % p;  // Update x if it is more than or
    // equal to p
    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res * x) % p;

        // y must be even now
        y = y >> 1; // y = y/2
        x = (x * x) % p;
    }
    return res;
}



void SieveOfEratosthenes(ll n, set<ll> &st)
{
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));

    for (ll p = 2; p * p <= n; p++)
    {

        if (prime[p] == true)
        {
            for (ll i = p * p; i <= n; i += p)
                prime[i] = false;
        }
    }
    for (ll p = 2; p <= n; p++)
        if (prime[p])
            st.insert(p);
}




ll CeilIndex(std::vector<ll>& v, ll l, ll r, ll key)
{
    while (r - l > 1) {
        ll m = l + (r - l) / 2;
        if (v[m] >= key)
            r = m;
        else
            l = m;
    }
 
    return r;
}


ll LongestIncreasingSubsequenceLength(vector<ll>& v)
{
    if (v.size() == 0)
        return 0;
 
     vector<ll> tail(v.size());

    ll length = 1; // always polls empty slot in tail
 
    tail[0] = v[0];
    for (size_t i = 0; i < v.size(); i++) {
 
        if (v[i] < tail[0])
            tail[0] = v[i];
        else if (v[i] > tail[length - 1])
            tail[length++] = v[i];
        else
            tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
        }

    return length;
}



bool isPowerOfTwo(ll x)
{
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x & (x - 1)));
}

ll node_cnt(ll node)
{
    if (visited[node])
        return 0;

    visited[node] = true;

    ll a = 0;

    for (auto child : graph[node])
    {
        // cout<<node<<" "<<child<<" ";
        if (!visited[child])
            a += node_cnt(child) + 1;
    }

    return a;
}
unsigned long long modInverse(unsigned long long n,
                              ll p)
{
    return power(n, p - 2, p);
}

unsigned long long nCrModPFermat(unsigned long long n,
                                 ll r, ll p)
{
    // If n<r, then nCr should return 0
    if (n < r)
        return 0;
    // Base case
    if (r == 0)
        return 1;

    // Fill factorial array so that we
    // can find all factorial of r, n
    // and n-r
    unsigned long long fac[n + 1];
    fac[0] = 1;
    for (ll i = 1; i <= n; i++)
        fac[i] = (fac[i - 1] * i) % p;

    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}

ll modFact(ll n, ll p)
{
    if (n >= p)
        return 0;

    ll res = 1;

    // Use Sieve of Eratosthenes to find all primes
    // smaller than n
    bool isPrime[n + 1];
    memset(isPrime, 1, sizeof(isPrime));
    for (ll i = 2; i * i <= n; i++)
    {
        if (isPrime[i])
        {
            for (ll j = 2 * i; j <= n; j += i)
                isPrime[j] = 0;
        }
    }

    // Consider all primes found by Sieve
    for (ll i = 2; i <= n; i++)
    {
        if (isPrime[i])
        {
            // Find the largest power of prime 'i' that divides n
            ll k = largestPower(n, i);

            // Multiply result with (i^k) % p
            res = (res * power(i, k, p)) % p;
        }
    }
    return res;
}

ll log22(ll n)
{
    ll a = __builtin_clzll(n);
    return 63-a;
}

ll Ispalindrome(string &s)
{
    ll n = s.size();
    ll fl = 0;
    forn(i, 0, n / 2)
    {
        if (s[i] != s[n - i - 1])
            return 0;
    }

    return 1;
}

ll isSorted(vector<ll> A)
{

    ll n = A.size();
    forn(i, 0, n - 1)
    {
        if (A[i] > A[i + 1])
            return 0;
    }
    return 1;
}
ll BinarySearchUminus(ll val, vector<ll> &A)
{
    ll low = 0, high = A.size() - 1;

    while (high > low)
    {
        ll mid = (low + high + 1) / 2;
        if (A[mid] == val)
            low = mid; // high = mid-1 for lower_bound-1
        else if (A[mid] < val)
            low = mid;
        else
            high = mid - 1;
    }
    if (A[low] > val)
        return -1;
    return low;
}

ll Ceil(ll a, ll b)
{
    ll ans = a / b;
    if (a % b != 0)
        ans++;
    return ans;
}



void bfs(queue<ll> &q )
{


    while (!q.empty())
    {
        ll v = q.front();

        q.pop();
        for (ll e : graph[v])
        {
            if (dist[e] == -1)
            {

                dist[e] = dist[v] + 1;

                
                q.push(e);
                
            }
        }
    }
    
}

void dijkstra(ll s, vector<ll> & d, vector<ll> & p , ll n) {
    d.assign(n, 1e17);
    p.assign(n, -1);

    d[s] = 1e17;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push({1e17, s});
    while (!q.empty()) {
        ll v = q.top().second;
        ll d_v = q.top().first;
        q.pop();
        if (d_v != d[v])
            continue;

        for (auto edge : graph2[v]) {
            ll to = edge.first;
            cout<<to<<" "<<d[v]<<" "<<edge.second<<endl;
            ll len =min(d[v] , edge.second);

            if (len < d[to]) {
                d[to] =len;
                p[to] = v;
                q.push({d[to], to});
            }
        }
    }
}

void primeFactors(ll n , vector<ll> &Cnt)
{
    // Prll the number of 2s that divide n
    while (n % 2 == 0)
    {
        Cnt.push_back(2);
        n = n/2;
    }
 
    // n must be odd at this poll. So we can skip
    // one element (Note i = i +2)
    ll v = sqrt(n);
    for (ll i = 3; i <= v; i = i + 2)
    {
        // While i divides n, prll i and divide n
        while (n % i == 0)
        {
            Cnt.push_back(i);
            n = n/i;
        }
    }
 
    // This condition is to handle the case when n
    // is a prime number greater than 2
    if (n > 2)
    Cnt.push_back(n);
}
void printDivisors(ll n ,  vector<ll> &a)
{
    // Note that this loop runs till square root
    ll sqr = sqrt(n);
    for (ll i=1; i<=sqr; i++)
    {
        if (n%i == 0)
        {
            // If divisors are equal, print only one
            if (n/i == i)
            a.push_back(i);
                // cout <<" "<< i;
 
            else // Otherwise print both
            {
            a.push_back(n/i);
            
            a.push_back(i);
            }
                // cout << " "<< i << " " << n/i;
        }
    }
    sort(all(a));
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   
    ll t=1;
    cin>>t;
    while (t--)
    {
    ll a , b;
    cin>>a>>b;

    if(a>b)
    swap(a , b);

    if(a==0)
    {
        if(b==0)
        cout<<0<<endl;
        else
        cout<<-1<<endl;
        continue;
    }
    ll cnt =0;
    ll Tmp = a*2ll;
    while(Tmp < b)
    {
    a*=2;
    Tmp*=2;
    cnt++;
    }

    if(a==b)
    {
    cout<<cnt+a<<endl;
    continue;
    }
    ll A = a*2;
    ll tmp = A - b;
    a-=tmp;
    b-=tmp;
    cnt+=tmp;
    cnt+=b+1;
    cout<<cnt<<endl;
    }


}

Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
  ll x, y, ans = 0;
  cin >> x >> y;
  if (x > y)
    swap(x, y);
  if (x == 0)
  {
    cout << ((y == 0) ? y : -1) << '\n';
    return;
  }
  while (x < y)
  {
    x *= 2;
    ans++;
  }
  cout << ans + y << '\n';
  return;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL), cout.tie(NULL);
  int test = 1;
  cin >> test;
  while (test--)
    sol();
}

2 Likes

Same solution as the editorial, just a bit more code-focused for those that prefer that.

Step 0 - handle edge cases that can be solved in O(1):

if(x==y) return x
if(x==0) return -1
if(y==0) return -1

Example: x: 42, y: 88, operations: 0
Step 1 - we ensure x >= y is always true:

if (y > x) swap(x,y)

Example: x: 88, y: 42, operations: 0
Step 2 - multiplying y by 2, as long as it will be lower than x, is the most effective way of using operations. Feel free to try to find a counter proof, it does not exist :stuck_out_tongue:

while(y * 2 <= x){
	y = y * 2
	operations = operations + 1
}

Example: x: 88, y: 84, operations: 1
Step 3a - edge case handling:

if(x == y) return x + operations

Step 3b - now reduce x and y by one until x == y * 2
O(n) - Bruteforce approach (too slow but a good start)

while(x != y * 2){
	x--
	y--
	operations = operations + 1
}

O(1) - Math formula (fast enough for the problem):

long toSubtract = 2 * x - y;
x = x - toSubtract;
y = y - toSubtract;
operations = operations + toSubtract;

Example: x: 8, y: 4, operations: 81
Step 4 - we know that x == y * 2 and neither x nor y are 0. So we multiply y by 2 once

y = y * 2
operations = operations + 1

Example: x: 8, y: 8, operations: 82
Step 5 - we know x == y

return x + operations

Output: 90

I can prove that it is not possible to do less than y + \text{ceil}(\log_2(y-x+1)) (assuming y > x) but I cannot prove the upper bound.

Taking that leap of faith (that there do not exist solutions with the number greater than the lower bound), the solution ends up being very simple:

for _ in range(int(input())):
	x, y = sorted(map(int, input().split()))
	if x==y: print(x)
	elif 0 in (x, y): print(-1)
	else:
		ans = y
		while x<y:
			ans += 1
			x *= 2
		print(ans)

I think that the proof given for the part “Increase X using the first operation until X becomes equal to Y or X<Y<2*X” is insufficient. Making D=0 as soon as possible is not exactly equivalent to making X and Y both 0 at the same time. I feel that a more nuanced argument is needed.

1 Like