SRM 603: uncertainty

What a match to be tainted by uncertainty. I have no idea if my 250 is correct and for a while I had no idea if my 500 was correct. Starting to write before the challenge phase and now I know that my 500 is at least correct in theory. I could have made an implementation mistake.

Div1 250

Two players have a tree. They play alternating turns. In a turn, a player must pick an edge and destroy the edge. This splits the tree into two components (also trees). The player then chooses a component to keep, the rest is discarded. The game ends when only one node remains. The nodes have some costs written on them. The first player wants to maximize this value, the other player wants to minimize it. Return the cost of the node if both players play optimally.

I had absolutely no idea what to do. I tried everything and couldn't think of a non-clever way to solve it. Eventually, I thought that since it is a div1 250, it shouldn't be so hard. It probably has a very easy solution that I am missing. Maybe a super easy solution that is, however, difficult to prove... I checked the example cases and noticed that they were all very simple... maek you think... Then I noticed that in all those cases, the returned value was the maximum cost node with degree equal to 1. After drawing in paper it sort of makes sense. I was late so I made a submission. Right now it seems that just about everybody is doing this. So maybe it is correct?

int findend(vector<int> edges, vector<int> costs)
{
    int n = edges.size() + 1;
    vector<int> degree(n, 0);
    for (int i = 0; i < edges.size(); i++) {
        // edge between i+1 and edges[i]
        degree[ edges[i] ]++;
        degree[i+1]++;
    }
    int best = 0;
    for (int i = 0; i < n; i++) {
        if (degree[i] == 1) {
            best = std::max(best, costs[i] );
        }
    }
    return best;
}

Div1 500

Given `n` count the number of pairs of two strings such that the second string is a rotation of the first string and the strings use only the first `k` letters of the English alphabet.

The number of rotations depends on the number of repetitions in the first string. If the string contains 2 repetitions (eg: abab), then the number of rotations is n/2. For each number of repetitions `r`, calculate the number of ways to have exactly that number of repetitions and multiply by `n/r`.

So in order to have `r` repetitions, `n` must be a multiple of `r`. So we are interested in all divisors `d` of `n`. With `n <= 1000000000`, we can find all the divisors in `O(sqrt(n))`.

The difficult part is to count the number of strings with an exact number of repetitions. Note that "aaaa" contains "a" repeated 4 times, "aa" repeated two times and "aaaa" "repeated" 1 time. We should only consider it as 4 repetitions. So if we calculate the number of strings with 2 repetitions as `K ^ (n / r)`, we have to subtract the strings with smaller repetitions that divide `r`... I couldn't think of a way to do this fast. I could only do it in `O(d^2)` where `d` is the number of divisors of `n`. At first I had no idea what an upper bound for the number of divisors is. We know we need an `O(sqrt(n))` algorithm to find them. But what about the actual number of divisors?

In my first excursions, I tried many numbers composed of the first few primes raised to some exponents. My best was 729.

Eventually though, I coded a bruteforce. It appears 1344 is the maximum number of divisors for `n <= 1000000000`. Let's see...

const int MOD = 1000000007;

vector<int> getDivisors(int n)
{
    vector<int> div;
    for (int i = 1; i*i <= n; i++) {
        if (n % i == 0) {
            div.push_back(i);
            if (n / i != i) {
                div.push_back(n / i);
            }
        }
    }
    sort(div.begin(), div.end());
    return div;
}
long modPow(long x, int y)
{
    long r = 1;
    while (y > 0) {
        if (y & 1) {
            r = (r * x) % MOD;
        }
        x = (x * x) % MOD;
        y /= 2;
    }
    return r;
}
long best = 1;
vector<int> primes = {2,3,5,7,11,13,17,19,23};

void backtrack(int p, long x, long divs)
{
    if (divs > best) {
        best = divs;
        cout << x <<" has "<<divs<<endl;
    }
    long y = x;
    int i = 0;
    if (p == primes.size()) {
        return;
    }
    while (y * primes[p] <= 1000000000LL) {
        y *= primes[p];
        i++;
    }
    //cout << "}" << endl;
    for (int j = i; j >= 0; j--) {
        backtrack(p+1, y, divs * (j+1) );
        y /= primes[p];
    }

}

int getNumber(int n, int k)
{
    // The bruteforce to find the maximum number of divisors
    //backtrack(0, 1, 1);
    
    vector<int> d = getDivisors(n);
    long total[d.size()];
    long res = 0;
    cout << d.size() << " divisors found"<<endl;
    for (int i = 0; i < d.size(); i++) {
        long x = modPow(k , d[i]);
        for (int j = 0; j < i; j++) {
            if (d[i] % d[j] == 0) {
                x = (x - total[j] + MOD) % MOD;
            }
        }
        total[i] = x;
        //cout << "for "<<d[i]<<" = "<<total[i]<<endl;
        res += (total[i] * d[i]) % MOD;
    }
    return (int)( res % MOD );
}

So?

The challenge phase is about to end and my solutions are standing. Let's see what happens

I don't really like 250s that have solutions that are easy but difficult to prove. How many people are getting points like me, coding it on a hunch? Well... maybe the solution is wrong,but Petr agrees, so... I gues it is right.