CLSPWR - Editorial

PROBLEM LINK:

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

Author: Srikkanth R
Tester : Radoslav Dimitrov
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy

PREREQUISITES:

Maths, Precomputation

PROBLEM:

An integer x is said to be a Perfect Power if there exists positive integers a and b (i.e a, and b should be \geq 1) such that x = a^{b+1}.

Given an integer n, find the closest Perfect Power to n. If there are multiple Perfect Powers equidistant from n and as close as possible to n, find the smallest one.

More formally, find the smallest integer x such that x is a Perfect Power and |n - x| \leq |n - y| over all Perfect Powers y.

EXPLANATION:

Have a close look at the constraints of N, it’s just 1e18. Why just man, it’s so big?

Remember we will be dealing with the powers and it will take few iterations to get to 1e18 even if we start will the lowest base possible i.e 2. It just takes 60 iterations to reach a value of 1e18.

Now let’s look at how we can solve this problem. One of the basic ideas is to iterate for all bases and their powers. The problem with this approach is that the numbers that can act as bases are very large. A number as large as 1e9 can act as a base.

Can we optimize it?

For a moment change the condition for power and say every power should be greater than 3. Then what is the maximum value that base (a) can take, is it less than 1e5. Hence we can surely iterate over the bases here if the power allowed to us was greater than 3.

Now the only powers that we are not considering and are in problem are squares and cubes. But for any number, it is quite easy to check a perfect square or a perfect cube closest to it.

But yes, there is another problem with test cases, these test cases are so large that even after optimizations, we will end up hitting TLE. One of the ways is pre-computation of all the perfect powers and then apply binary search on it to find the closest power.

TIME COMPLEXITY:

O(N*log(N)), where N \approx 1e5

SOLUTIONS:

Setter
#include <bits/stdc++.h>

#define LL long long
using namespace std;

int go = 1192904420;
mt19937 rng(go);
#define rand(l, r) uniform_int_distribution<LL>(l, r)(rng)

clock_t start = clock();

LL readInt(LL l, LL r, char endd) {
    LL x = 0;
    char ch = getchar();
    bool first = true, neg = false;
    while (true) {
        if (ch == endd) {
            break;
        } else if (ch == '-') {
            assert(first);
            neg = true;
        } else if (ch >= '0' && ch <= '9') {
            x = (x << 1) + (x << 3) + ch - '0';
        } else {
            assert(false);
        }
        first = false;
        ch = getchar();
    }
    if (neg) x = -x;
    if (x < l || x > r) {
        cerr << l << " " << r << " " << x << " failed\n";
    }
    assert(l <= x && x <= r);
    return x;
}
string readString(int l, int r, char endd) {
    string ret = "";
    int cnt = 0;
    while (true) {
        char g = getchar();
        assert (g != -1);
        if (g == endd) {
            break;
        }
        ++cnt;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
LL readIntSp(LL l, LL r) {
    return readInt(l, r, ' ');
}
LL readIntLn(LL l, LL r) {
    return readInt(l, r, '\n');
}
string readStringSp(int l, int r) {
    return readString(l, r, ' ');
}
string readStringLn(int l, int r) {
    return readString(l, r, '\n');
}

LL power(LL a, LL b) {
    LL res = 1, mul = a;
    while (b) {
        if (b & 1) {
            res = (res * mul);
        }
        mul = (mul * mul);
        b >>= 1;
    }
    return res;
}

int max_allowed[60];
void pre_calc() {
    max_allowed[2] = 1e9 + 1;
    max_allowed[3] = 1e6 + 1;
    for (int b=4;b<60;++b) {
            int x = 2;
            while (log(x) * b <= log(10) * 18 + log(2) + 1e-9) {
                x++;
                // cerr << x << " trying\n";
            }
            x--;
            max_allowed[b] = x;
    }
}

void solve() {
    LL n = readIntLn(1, (LL)1e18);
    // LL n = 100;
    LL ans = 1;
    auto chk = [&](LL ret) {
        LL have = abs(n - ret), got = abs(n - ans);
        if (have < got) {
            ans = ret;
        } else if (have == got) {
            ans = min(ans, ret);
        }
    };
    for (int b=2;b<60;++b) {
        LL lo = 1, hi = max_allowed[b], HI;
        HI = hi;
        while (lo < hi) {
            LL mid = (lo + hi + 1) >> 1;
            if (power(mid, b) <= n) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        chk(power(lo, b));
        if (lo < HI) chk(power(lo+1, b));
    }
    cout << ans << '\n';
}

int main() {
// Start solution here use readIntLn, readIntSp and readStringSp and readStringLn
// for reading input
    pre_calc();

    int T = readIntLn(1, 100000);
    // int T = 1;
    while (T--) {
        solve();
    }
// End solution here
    // assert(getchar() == EOF);
    
    cerr << fixed << setprecision(10);
    cerr << "Time taken = " << (clock() - start) / ((double)CLOCKS_PER_SEC) << " s\n";
    return 0;
}

My solution is a bit more simple.

2^{60} > 10^{18}, so we only have to check powers from 2 to 60.
For every i (2 \leq i \leq 60), we want the largest k such that k^i \leq n, so k = \left \lfloor{{\sqrt[i]{n}}}\right \rfloor. Obviously, only k^i and (k + 1)^i are possible answers. So just take the one which is closer to n.

Code

4 Likes

exactly nice approach

Can you prove that (k+1)^ i is going to be the closest from the right side? whats the proof for this?.. did you calculate k using the power function? what was your approach to calculate k ?

Can you prove that (k+1)^ i is going to be the closest from the right side? whats the proof for this?

By definition, k^i is the largest power of k less than or equal to n, so (k + 1)^i will be strictly greater than n.

did you calculate k using the power function? what was your approach to calculate k ?

Yes, I already described the details in my comment. I used std::pow().

Try to read my code. It should make more sense now.

1 Like