TopCoder SRM 571: Educative

As I write this before the challenge phase, it appears this SRM was easier than usual. Tons of solutions, even for the hard problem. Even I could solve medium and easy. But I am not 100% sure about div1 medium.

Div1 hard

This was about using disks to move candy around making it rotate using the disk's center until you reach a specific point.

At first candy has a whole radius it can reach, this radius intersects with circles, and then creates a donut pattern. Thought that even If I thought of a solution I would not have too much time, so I skipped it.

Div1 medium: The one with Cliques

You are given a molecule (graph) of up to 50 atoms (vertices) , each with some power (weight). Find a sub-graph that has m elements. Such that 3*m is at least as large as 2*n. Every pair of atoms in the graph must be connected. Find the maximum sum of weights (power)

So, the result set is a Clique. Also, it should be a maximal Clique. Because if it is possible to make a bigger Clique without removing some atoms, then it makes no sense not to (no negative power). I was trying to come up with an algorithm that did this, and took advantage that the clique has to be large (at least 2/3 of the graph). But then I thought. (Wouldn&pos;t this be a classic problem?). So I decided to do a google search: "Find maximal complete Sub-graphs" A stack overflow question and a wikipedia link later I ended up on this page: Bron Kerbosch's algorithm. According to that page, as long as you use the pivot optimization that algorithm will be O(3^n/3), which is great for n=50.

I implement that algorithm (had a couple of implementation bugs, so it took some time). I then tested with some large graphs. The full n=50 graph, and a graph that had 15 complete subgraphs of 3 vertices and one of 5. It seems the algorithm is very fast, but I am not so sure if there might be a better challenge case..

As I write this, I noticed that my program has already survived 2 challenge cases.

typedef long long int64;
#define long int64

struct MagicMolecule
{
    int n;
    long N[50];
    int res;
    vector<int> magicPower;
    // Taken from wikipedia, translated to use bitmasks.
    void BronKerbosch2(long R, long P, long X)
    {
        if (P == 0LL && X == 0LL) {
            // P and X empty, R is a maximal clique
            int t = 0;
            int m = 0;
            for (int i=0; i<n; i++) {
                if ( (1ll << i) & R) {
                    m++;
                    t += magicPower[i];
                }
            }
            if ( 3*m >= 2*n ) {
                res = std::max(res, t);
            }
            return;
        }
        //choose a pivot vertex u in P U X
        int u = 0;

        while ( ! ( (1ll<<u) & (P|X) ) ) {
            u++;
        }

        //for each vertex v in P \ N(u):
        for (int v = 0; v < n; v++) {
            if ( ( (1ll << v) & P) && !( (1ll << v) & N[u])  ) {
                BronKerbosch2( R | (1ll << v), P & N[v], X & N[v]);
                P -= (1ll << v);
                X |= (1ll << v);
            }
        }
    }

    int maxMagicPower(vector <int> magicPower, vector <string> magicBond)
    {
        
        res = -1;
        n = magicPower.size();
        
        //N[i] is the set of neighbors of i
        for (int i=0; i<n; i++) {
            N[i] = 0;
            for (int j=0; j<n; j++) {
                if (magicBond[i][j] == 'Y') {
                    N[i] |= ( 1ll << j );
                }
            }
        }
        this->magicPower = magicPower;
        BronKerbosch2(0, (1ll<<n) - 1, 0);
        return res;
    }
};
#undef long

Div1 easy

There are n files named 1.mp3, 2.mp3, ... 10.mp3, 11.mp3, .... n.mp3. They are sorted by name. And anyone who has dealt with file managers knows that sorting by name is not the same as sorting by song number, unless the song numbers have leading 0s.

Return the first min(n, 50) file names after sorting the files.

This is as interesting as an easy problem can be.

So the results are: 1.mp3, 10.mp3 ... (until 10...0 is greater than n), then 100001.mp3, then 100002, ... 100009, 100010, ... and so and so.

I preferred to use a backtracking approach. Starting at i=0, I recurse through i*10 + 0, i*10 + 1, ... i*10+9, in that order. Whenever I find a integer, I add it to the result. When the result has min(n,50) elements, it is time to end the whole recursion. So this recursion will need min(50, n) steps overall.

struct FoxAndMp3
{
    int n;
    vector<string> res;
    
    void rec(int x)
    {
        if (x > n) {
            return;
        }
        if ( res.size() == n || res.size() == 50) {
            return;
        }
        if (x != 0) {
            ostringstream st;
            st << x <<".mp3";
            res.push_back(st.str());
        }
        for (int i= (x == 0); i<=9; i++) {
            if ( res.size() == n || res.size() == 50) {
                break;
            }

            if ( x  <= (n - i) / 10 ) {
                rec(x * 10 + i);
            }
        }
    }
    
    vector <string> playList(int n)
    {
        this->n = n;
        rec(0);
        return res;
        
    }
};

At this moment, my div1 500 has already survived 3 challenges.

Let us see how it goes

Will my submissions survive the system tests? Will I recover yellow? No idea. It was a interesting match. But easier than usual. I think admins want a warm up for Saturday's TCO match (which will have easy problems) and also want to make up for the latest trend in hard matches.

Comments?