SRM 628: sleeping during the srm

Okay, so here is the thing. This is a 7:00 AM match. That is not usually a problem except I went to sleep at 4:00+something AM, at least I could register early to the match. So I put my alarm clock to 7:15 AM, I thought losing those 15 minutes wouldn't really change my score too much unless div1 medium is easy. I *really* woke up at 7:30. With 45 minutes the objective was to do at least div1 easy...

Div1 Easy: The one with sub-routines

Given `2 <= n <= 10^18` Find the maximum `x` such that : `(x ^ d(x) = n)` where `d(x)` is the number of divisors of `x`. If no such `x` exists, return -1.

The key is to notice that `d(x)` cannot really get too large. Any valid `d(x)` is `O(log(n))`, so we iterate through all the values of `d` such that `n` is a power of `x`. Until we reach a `d` that is very large.

For a given `d`, let's find `x : x ^ d = n` , this is the `d`-th root of `n`. We could use the pow function here, but it uses floating point numbers and you would need to be careful with precision and stuff... So we can just use a binary search for the largest `x` such that `x ^ d <= n`. Incidentally, if this `x` is 1, then we know that `d` has become too large and we can stop the search.

Once we have `d` and its valid value of `x` , all we need to do is verify that the number of divisors of `x` is equal to `d`. `d` will be at least 2, which means that `x` is `O(sqrt(n))`. We can count the divisors of `x` in `O(sqrt(x))` time. This yields an `O(n ^ (1/4))` algorithm. Nice?

The main method of my solution looks like this:

long findArgument(long n)
{
    long d = 2;
    long res = -1;
    while (true) {
        // find x : x ^ d = n
        
        long x = binarySearch(1, n+1, [&](long x) {
                return ipow(x,d) <= n;
        });
        if (ipow(x,d) == n) {
            // possible
            if (countDivisors(x) == d ) {
                res = std::max(res, x);
            }
        } else if (x == 1) {
            break;
        }
        
        d++;
    }
    
    return res;
}

Everything else are standard sub-routines ...

long binarySearch(long lo, long hi, std::function<bool(long)> P)
{
    // P(lo) true
    // P(hi) false
    while (lo + 1 < hi) {
        long ha = lo + (hi - lo) / 2;
        if (P(ha)) {
            lo = ha;
        } else {
            hi = ha;
        }
    }
    return lo;
}

const long INF = 1000000000000000002LL;
long ipow(long x, long d)
{
    // returns x ^ d if x ^ d < INF, else INF 
    long r = 1;
    while (d > 0) {
        if (d % 2 == 1) {
            if (r > INF / x) {
                r = INF;
            } else {
                r = r * x;
            }
        }
        d /= 2;
        if (x > INF/x) {
            x = INF;
        } else {
            x = x * x;
        }
    }
    return r;
}

long countDivisors(long x)
{
    long p = 1;
    long c = 0;
    while ( p <= x / p) {
        if (x % p == 0) {
            c++;
            if (x / p != p) {
                c++;
            }
        }
        p += 1;
    }
    return c;
}

Div1 medium: The one with expressions

You are given a tree of binary expressions. The expressions can either be the ADD function or the MAX function. You also have a list of (positive) values you can assign to each of the leaves in the tree. There are at most 2000 leaves. Return the maximum total value

Good luck with THAT. Solution is likely some sort of greedy but I am too asleep to do this.

.

Afterwards

During the challenge phase I read codes for div1 500. The idea appears to be that you can find out the maximum quantity of values that will be added up together in the final expression. If you have this number `x`, then you just have to pick the largest `x` integers from the values and add them together. Of course they had to pick THIS match to have an easy div1 medium...