SRM 643

div1 250: The one with factorization

Factorize `2 <= N <= 10^18`, but half of the vector containing the sorted prime factors is given to you as the input. (The even-indexed ones) For example, 18 = 2*2*3, the prime factors vector is {2,2,3}, which means that the input will be 18, {2,3}, get it?

Factorization is supposed to be a hard problem. And for `N <= 10^18` it is, specially given the constraints, not so much the 2 seconds execution constraint, but the 256 MB memory constraint, the available time to code stuff and the lack of being able to save useful stuff in hard drive before running each test case... I mean, the *n*x* factor command can certainly factorize some large numbers, but you are supposed to do things the manual way here rather than reuse code..

So factorizing `N` is out of the question, maybe that's why it has to include some factors in the input. My first instinct was to think, well, just divide `N` by the known prime factors, the remaining value `n` shall be small enough to factorize, right? This is false. Just imagine `N` equal to 2 multiplied by a large prime number close to `10^18 / 2`. The large prime number would be a bit too large to do the `O(sqrt(N))` factorization by trial division algorithm we normally use.

Second idea was to do some ad hoc things. If there is only one prime factor provided, it means the number of prime factors is either 1 or 2, these are both easy cases to solve (result is either `{"primes"[0]}` or `{"primes"[0], N/"primes"[0]}` ). But this doesn't help. Cases in which the input has more than one factor can still lead to a rather large `n` after dividing: `999999999999999896 = 2 * 2 * 2 124999999999999987`.

So the solution is based in the following logic: The very last prime number in the factorization can be rather large `O(N)`, large, but if it is really so large, it will be the only such large number in the factorization. If this number is in an odd position, it will be ignored, and the resulting `N` after dividing by the known factors will be large because it includes this prime number. So the idea (which may not be 100% correct) is to just do trial division up to the `sqrt(2000000000)` and then, if there is still a number after dividing that much, what's left ought to be a prime number, right? I have no idea how good this is.

typedef long long int64;
#define long int64
struct TheKingsFactorization
{
    vector<long> getVector(long N, vector<long> primes)
    {
        long n = N;
        for (long p: primes) {
            n /= p;
        }
        //for (long p = 2; p * p <= 2000000000LL; p++) {
        for (long p = 2; p * p <= n; p++) {
            while (n % p == 0) {
                n /= p;
                primes.push_back(p);
            }
        }
        if (n > 1) {
            primes.push_back(n);
        }
        sort(primes.begin(), primes.end());
        
        return primes;
    }
};
#undef long

I suspect there will be many challenges in the challenge phase. I prepared up some cases, it's unlikely I'll get to use them, because Petr is in my room. Finished typing this as the coding phase ended. Let's see what happens.

SRM 640 : Do I still have write access here?

It's SRM 640, that means there have been 140 SRMs since SRM 500, remember SRM 500? It was fun.

Div1 250: The one with Trees

You have a bunch of stars with different colors. Use Ribbons to connect the stars, so that the ribbons and stars make a tree (connected, no cycles). Only some specific pairs of stars may be connected. Return the minimum number of ribbons connecting two stars with equal colors we should use.

So... isn't this the very definition of the minimum spanning tree problem? You need to find an undirected tree, with a minimum sum of used edge costs. Just make an edge cost 1 if the two stars it connects have the same color.

So just implement Prim's or Kruskal's Minimum Spaning Tree algo. I went for Kruskal because I am odd.

class ChristmasTreeDecoration:
 def solve(self, col, x, y):
    n = len(col)
    # I like python for things like this, create a list of edges (c,u,v) c is cost
    edges = [ ( int(col[i-1] == col[j-1]), i-1, j-1) for (i,j) in zip(x,y) ]
    
    # Precarious union find thingie 
    parent = range(n)
    def getParent(x):
        while parent[x] != x:
            (x, parent[x]) = (parent[x], parent[parent[x]]) 
        return x
    
    # Kruskal:
    total = 0;
    for (cost, u,v) in sorted(edges):    #sorting edges by cost
        if getParent(u) != getParent(v): #distinct components
            parent[getParent(u)] = v     #connect them
            total += cost                # add cost
    return total

After coding this and realizing it is super short and elegant I starred at the screen for a while. Skeptical that this was so easy. 250s lately are harder than this. I also doubted for a while if my getParent(x) function is bugged or not. Normally I use a stack to move all x to have parent[x] = the super grand parent. But this seems to work fine.

Div1 550: The one with bipartite graphs

You are given `n_1,n_2,a,d`, `n_1,n_2 <= 1000000000` return the maximum number of edges in a graph with `n_1+n_2` vertices, where each vertex has degree of at least `d` and the maximum bipartite matching is `a`.

So yeah... this problem exists. I am sure there has to be some sort of solution.

Div1 1000:

Another problem that probably has a solution. My hunch is that this one is rather easy once you do plenty of math.

Challenge phase

Nothing to report.

Let's see if that 250 survives.