CHANGEXY - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sky_nik
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You are given A, B, and K.
Starting with x = K, you can do the following:

  • x\to x+1
  • x\to K\cdot x

Find the minimum number of moves needed to reach x = B.

EXPLANATION:

Let’s look at the process in reverse, i.e, starting from B and reaching A.
When doing this, we also need to invert the operations.

  • Instead of adding 1 to x, we can subtract 1 from it.
  • Instead of multiplying x by K, we can divide x by K, but only when x is already a multiple of K.

With this setup, note that whenever x is not a multiple of K, the only thing we can do is to subtract 1.
So, let’s repeatedly subtract 1 till a multiple of K is reached.

When x is a multiple of K, we have two options: either subtract 1 (in which case x is no longer a multiple of K again, so we’re forced to keep subtracting till we reach the next smaller multiple), or divide by K.
Intuitively, it seems more useful to divide by K, since it moves us lower ‘faster’ (as long as we don’t undershoot A by doing so, of course).
It turns out that this intuition is correct.

Proof

Suppose x is a multiple of K.
If \frac{x}{K} \lt A then division is impossible so we can only subtract, and the optimal solution is unique anyway.

So, let \frac{x}{K} \geq A.
If we never divide, we keep subtracting 1 till we reach A.
However, on the way we’ll definitely pass through \frac{x}{K}; and it’d have been faster to just divide by K once rather than subtracting 1 (x - \frac{x}{K}) times to get there.
So, any optimal solution will include a division somewhere along the line.

Next, note that whenever we perform the division, it has to be from a multiple of K - so, the number of subtractions performed beforehand is also some multiple of K, say K\cdot a.
However,

  • x \to (x - K\cdot a) \to (\frac{x}{K} - a) requires K\cdot a + 1 moves
  • x \to \frac{x}{K} \to (\frac{x}{K} - a) requires 1 + a moves, which is clearly better.

So, it’s optimal to divide immediately when x is a multiple of K.

tl;dr the following simple greedy works.
Start with x = B. Then,

  • if x is a multiple of K and \frac{x}{K} \geq A, divide x by K.
  • If x is a multiple of K and \frac{x}{K} \lt A, use (x-A) subtractions to reach A.
  • If x is not a multiple of K, use subtractions to reach either A or the next smallest multiple of K, whichever is closer.
    • To find the next smallest multiple of K, note that you can simply subtract (x\bmod K) from x, so this can be computed in \mathcal{O}(1).

Each division reduces x by a factor of K, so we’ll perform at most \log_K B divisions (since that will put us at 1 already).
Between divisions, the subtractions are simulated in \mathcal{O}(1) time, so they don’t affect the time complexity.

TIME COMPLEXITY:

\mathcal{O}(\log_K B) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int a, b; cin >> a >> b;
    int k; cin >> k;

    int ans = INF;
    for (int i = 0; ; i++){
        if (a > b){
            break;
        }
        
        auto get = [&](int k, int x){
            int ans = 1;
            while (x--) ans *= k;
            return ans;
        };
        
        int d = b - a;
        int v = i;
        for (int j = i; j >= 0; j--){
            int times = d / get(k, j);
            d -= times * get(k, j);
            v += times;
        }
        
        a *= k;
        ans = min(ans, v);
    }
    cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;

map<tuple<int, int, int>, int> cache;
int solve(int a, int b, int k) {
  if (a == b) {
    return cache[{a, b, k}] = 0;
  }
  const auto rem = min(b % k, b - a);
  if (rem) {
    return cache[{a, b, k}] = rem + solve(a, b - rem, k);
  }
  if (b / k >= a) {
    return cache[{a, b, k}] = 1 + solve(a, b / k, k);
  }
  return cache[{a, b, k}] = b - a;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int t; cin >> t; while (t--) {
    int a, b, k;
    cin >> a >> b >> k;
    cout << solve(a, b, k) << '\n';
  }
}
Editorialist's code (Python) 
def solve(a, b, k):
    if b < a: return 10**18
    if a == b: return 0
    if b%k != 0: return min(b-a, solve(a, b-b%k, k) + b%k)
    return min(b-a, solve(a, b//k, k) + 1)
    
for _ in range(int(input())):
    a, b, k = map(int, input().split())
    print(solve(a, b, k))
1 Like
2 
#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
    int t;
    cin>>t;
    while(t--){
        int a,b,k;
        cin>>a>>b>>k;
        long long m = a;
        int c = 0;
        long long x = 0;
        while(m*k<=b){
            m *= k;
            c++;
            x = b - m;
        }
        long long y  = 0;
        int d = c;
        while(c>=0){
            int z = pow(k,c);
            y += x/z;
            x -= (x/z)*z;
           
            c--;
        }
        y += d;
        cout<<y<<"\n";
    }
}

i am moving from a to b . First i am calculating the multiplication then adding.

4

Here is another way to approach this.

Consider representations of numbers in base K. Multiplying by K is appending 0 to the K-base representation. The optimal solution is to first keep adding 1 to A until it’s K-base representation becomes equal to some prefix of the K-base representation of B. Then for each additional K-digit d of B multiply A by K and then d times add 1 - total d + 1 operations per each K-digit d.

It can be proved by induction on B. Assuming it holds for all previous values of B, B is divisible by K, and B \ge A \cdot K, the trailing 0-s of K-base representation of B-1 turn into K-1, and the last non-zero K-digit will be less by 1. On the other hand, the K-base representation of B / K will drop the last 0. The latter is clearly preferable.

1 Like