Codeforces #196: slowness

It tends to be difficult for me to find time for Codeforces matches. Today there was finally one in a time/day slot I can try out.

I adapted my TopCoder strategy into Codeforces. I decided not to open problem A until 10 minutes before the contest ends. But I sort of know that problems D and E tend to be too above my level, so I focused on problems C and B.

Problem C: The one with divisor trees

problem statement

A divisor tree is a tree of integer numbers in which all the leaf nodes are prime numbers and every other node is equal to the multiplication of all of its children. Given up to 8 numbers `(a_i <= 10^12)`, return the minimum number of nodes in a divisor tree that contains them all.

My first reaction was to try to think of a dynamic programming idea. Given a sub-set of the numbers, what is the minimum-size tree you can make? But as I was attempting to solve this I eventually noticed a solution that was easier to code and clearly correct.

Other than the numbers `a_i`, you don't need any of the other nodes to be composite. The only exception would be the root, the root of the tree may need to be composite when there is no way to distribute all of the numbers in a single subtree.

This takes us to concluding that each of the numbers `a_i`, will either be a direct child of another `a_j` or of a newly-added root. There are at most `9^8` ways to make this decision, which is not large. You can cut it even more by using backtracking and making sure not to add children to a integer that are not divisors of it, and that the product of all the children divides the parent.

After assigning the parents, we just need to calculate the size of the tree. For this we can use a small dynamic programming. Process the integers in increasing order and find, for each of them, the minimum size of the tree that has it as root. This size depends on the sizes of all the children and the number of remaining prime factors. So we also need something that is able to calculate the prime factors. A memoization does the job well as we only need the number of prime factors for numbers `a_i` and their divisors.

// from library: primesn, number of primes <= 1000000.
//               primes[i] : i-th prime number <= 1000033

// memoizes the number of prime factors for x.
map<long,int> primeFactors;
int countPrimeFactors(long x)
{
    if (primeFactors.find(x) == primeFactors.end()) {
        int res = 0;
        if (x == 1) {
            res = 0;
        } else {
            for (int i=0; i<primesn; i++) {
                if ( primes[i] > x/primes[i]) {
                    break;
                }
                if (x % primes[i] == 0) {
                    //one
                    res = 1 + countPrimeFactors(x / primes[i]);
                    break;
                }
            }
            if (res == 0) {
                res = 1;
            }
        }
        primeFactors[x] = res;
    }
    return primeFactors[x];
}


int n;
const long INF = numeric_limits<long>::max();
long a[8];
int parent[8];
long ta[8];


long best;

void backtrack(int x)
{
    if (x == n) {
        // all right, build the trees
        long tree[n+1]; //tree size
        for (int i=0; i<=n; i++) {
            tree[i] = 0;
            int children = 0; //number of children of a[i]'s root
            for (int j=0; j<i; j++) {
                if ( parent[j] == i ) {
                    children++;
                    tree[i] += tree[j];
                }
            }
            if ( (i != n) && (ta[i] != 1) ) {
                //how many prime factors does ta[i] have?
                int f = countPrimeFactors(ta[i]);
                tree[i] += f;
                children += f;
            }
            if (children > 1) { //we need this because a[i] might be prime.
                tree[i]++;
            }
        }
        best = std::min(best, tree[n]);
    } else {
        // assign a parent to #x, n means the root.
        for (int i=x+1; i < n; i++) {
            if ( ta[i] % a[x] == 0) {
                parent[x] = i;
                ta[i] /= a[x];
                backtrack(x+1);
                ta[i] *= a[x];
            }
        }
        parent[x] = n;
        backtrack(x+1);
    }
}

long solve()
{
    // Call the backtracking
    sort(a, a+n);
    for (int i=0; i<n; i++) {
        ta[i] = a[i];
    }
    best = numeric_limits<long>::max();
    backtrack(0);
    return best;
}

Problem B: The one with the other kind of tree

I opened this problem, seemed difficult but eventually thought of an approach. It took me a while to code it, and when I finished it, there were bugs. 10 minutes before the end of the contest, I switched to A, but it didn't appear that I would be able to solve it in 10 minutes, so I decided to go back to B. Debugged and finishing coding it right as the contest ended. It doesn't really matter though, because it turns out that my idea , while correct, would still time out because of an issue I missed to notice. After I fixed this issue, it works fine.

problem statement

A set of n towns is a tree (n-1 roads and it is connected). m towns are haunted. The origin of the hauntings is a town such that its minimum distance between it and the haunted cities is at most d. Return the number of cities that follow this rule. `(1 <= m <= n <= 100000)`,

Very large constraints, but we got to take advantage of it being a tree.

Since it is a tree, we can pick a root, any vertex works. For each vertex calculate farHaunted, the maximum distance between the vertex and a haunted vertex that is a child or a grand child of it. (In the rooted tree) This is workable in `O(n)` time.

The real challenge is to find the actual maximum distance from a vertex to a haunted one, (possibly outside the subtree). To do this, let me define parentHaunted, the minimum distance between vertex x and a haunted vertex such that the road between x and the haunted vertex visits the parent of x. After this is defined, we can just start on the root and then find parentHaunted for each child and grandchild we find. Using this value we can calculate the real maximum distance between the vertex and a haunted one. parentHaunted depends on the parent's parentHaunted and the data from the siblings, pick the sibling with the worst farHaunted. This is the part that caused my time out bug, it is best to do it in O(degree(x)) time.

int n, m, d;
const int MAX = 100000;
int p[MAX];
bool haunted[MAX];
int a[MAX], b[MAX];

int degree[MAX];
vector<int> g[MAX];

int farHaunted[MAX]; //what is the furthest haunted child of x?

void dfs(int x, int parent)
{
    int & fur = farHaunted[x];
    fur = -1;
    for (int i=0; i<degree[x]; i++) {
        int y = g[x][i];
        if (y != parent) {
            dfs(y, x);
            if (farHaunted[y] != -1) {
                fur = std::max(fur, farHaunted[y] + 1);
            }

        }
    }
    if (haunted[x]) {
        fur = std::max(fur, 0);
    }
}

int reallyFar[MAX];

void dfs2(int x, int parent, int hauntedParent)
{
    //my current position
    reallyFar[x] = std::max(hauntedParent, farHaunted[x]);
   
    pair<int,int> bestChild ={-1,-1};
    pair<int,int> secondBestChild = {-1,-1};
    for (int i=0; i<degree[x]; i++) {
        int y = g[x][i];
        if (y != parent) {
            pair<int,int> p = make_pair(farHaunted[y], y);
            if (p > bestChild) {
                secondBestChild = bestChild;
                bestChild = p;
            } else if (p > secondBestChild) {
                secondBestChild = p;
            }
        }
    }

    
    for (int i=0; i<degree[x]; i++) {
        int y = g[x][i];
        if (y != parent) {
            int furpar = -1;
            if (hauntedParent != -1) {
                furpar = hauntedParent + 1;
            }
            if (haunted[x]) {
                furpar = std::max(furpar, 1);
            }
            int oth = bestChild.first;
            if (y == bestChild.second) {
                oth = secondBestChild.first;
            }
            if (oth != -1) {
                furpar = std::max(furpar, oth + 2);
            }
            dfs2(y, x, furpar);
        }
    }
}

int solve()
{
    fill(haunted, haunted+n, false);
    for (int i=0; i<m; i++) {
        haunted[--p[i]] = true;
    }
    //build the tree
    fill(degree, degree+n, 0);
    for (int i=0; i<n-1; i++) {
        int u = --a[i], v = --b[i];
        
        degree[u]++;
        degree[v]++;
    }
    for (int i=0; i<n; i++) {
        g[i].resize(degree[i]);
        degree[i] = 0;
    }
    for (int i=0; i<n-1; i++) {
        int u = a[i], v = b[i];
        assert(g[u].size() > degree[u] );
        assert(g[v].size() > degree[v] );
        g[u][degree[u]++] = v;
        g[v][degree[v]++] = u;
    }
    // pick an arbitrary root, let us say 0. Find farHaunted
    dfs(0, -1);
    // now do another DFS to fill reallyFar:
    dfs2(0, -1, -1);
    
    for (int i=0; i<n; i++) {
        if (reallyFar[i] <= d) {
            res ++;
        }
    }
    return res;
}