APP_BAL_SCA - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: emptypromises
Tester: udhav2003
Editorialist: iceknight1093

DIFFICULTY:

1736

PREREQUISITES:

Observation

PROBLEM:

You have M kilograms of crushed apples, and want to measure out exactly N of them.
To achieve this, you have a balance, which can only tell you whether the weights of both sides are equal or not.

Is it possible to measure out exactly N kilograms?

EXPLANATION:

First, if N \gt M then obviously it’s impossible to measure out N kilograms from M.

Now, let’s try to figure out what can be measured out.

  • If M is odd, there’s nothing we can do: the balance can’t be made equal, so we can’t split the M kilograms any further.
  • If M is even, then we can only get two batches of \frac{M}{2} kilograms each.
    After this, we can recursively apply the same strategy to try and subdivide the \frac{M}{2} kilograms further.

Putting these together, it’s not hard to see that the parts we can get are of weights M, \frac{M}{2}, \frac{M}{4}, \ldots, \frac{M}{2^k}, where k is the largest integer such that 2^k divides M.
Going any further would be impossible since \frac{M}{2^k} is odd.

Of course, we can also combine these parts together to form others: for example \frac{M}{2} + \frac{M}{4} = \frac{3M}{4} can be formed.

Since \frac{M}{2^k} is the smallest part we can form, and also divides all the other weights we form along the way, clearly any combination of weights we create will also be divisible by \frac{M}{2^k}.

So, it’s necessary that N is a multiple of \frac{M}{2^k}, otherwise clearly measuring out N is impossible.
In fact, this condition is also sufficient!

Proof

Notice that we can form 2^k independent units of weight \frac{M}{2^k}, by simply repeatedly splitting any even weight into two smaller ones.

Then, we can simply combine 1, 2, 3, \ldots, 2^k of these units to form every multiple of \frac{M}{2^k} that’s \leq M, which is exactly what we wanted.

This gives us a pretty simple solution:

  • Find k, the largest integer such that 2^k divides M.
    This can be done by just iterating over k starting from 0, since M \leq 10^{18} ensures that k \leq 60.
  • Then, the answer is Yes if \frac{M}{2^k} divides N and No otherwise; of course along with N \leq M.

TIME COMPLEXITY

\mathcal{O}(\log M) per test case.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>

using namespace std;

using i64 = int64_t;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t; cin >> t;
	assert(1 <= t && t <= 2 * 100000);
	while (t--) {
		i64 m, n;
		cin >> m >> n;
		assert(1 <= m && m <= 1e18);
		assert(1 <= n && n <= 1e18);
		i64 z = m;
		if (n > m) {
			cout << "NO" << "\n";
			continue;
		}
		while (z % 2 == 0) {
			z /= 2;
		}
		cout << (n % z == 0 ? "YES" : "NO") << "\n";
	}
	return 0;
}
Tester's code (C++) 
#pragma GCC optimisation("O3")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define NUM1 1000000007LL
#define all(a) a.begin(), a.end()
#define beg(a) a.begin(), a.begin()
#define sq(a) ((a)*(a))
#define NUM2 998244353LL
#define MOD NUM1
#define LMOD 1000000006LL
#define fi first
#define se second
typedef long double ld;
const ll MAX = 200100;
const ll MAX2 = MAX;
const ll large = 1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        ll n, m;
        cin >> m >> n;
        if(n > m){
            cout << "NO\n";
            continue;
        }
        while(m%2 == 0) m /= 2;
        if(n%m == 0) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
	m, n = map(int, input().split())
	smallest = m
	while smallest%2 == 0: smallest //= 2
	print('Yes' if n%smallest == 0 and n <= m else 'No')
1 Like