Tuesday, February 19, 2013

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(3n/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?

8 comments :

vexorian said...

I failed div1 500, for a test case that seems crafted against this approach.

But it is possible to salvage the solution. I didn't consider the 3*m >= 2*n condition when solving it. When you keep it in mind, you can crop the recursion by just making sure to skip whenever the sum between the size of R and the size of P is certainly going to be smaller than 2*n/3.

So it amounts to just adding this to the top of the recursion:

if ( 3*(__builtin_popcount(P) + __builtin_popcount(R) ) < 2*n) {
return;
}

PRAVEEN DHINWA said...

have you checked it after this pruning , Please tell whether this approach passed or not !!

vexorian said...

The updated approach passes the system test I failed VERY fast. It cuts down the time from 7 seconds to 0 seconds. But I cannot run complete system tests until the practice rooms are added.

vexorian said...

It passes....

.. But after fixing a bug.

__builtin_popcount does not work with 64 bits integers, so normally you would use: __builtin_popcountl, but it seems that in TopCoder's c++ compiler version, __builtin_popcountl is bugged.

So what I did was this:

#define __builtin_popcountl(x) ( __builtin_popcount(x) + __builtin_popcount(x>>32) )

And later:

if ( 3*(__builtin_popcountl(P) + __builtin_popcountl(R) ) < 2*n) {
return;
}


The whole thing becomes much simpler if you just include the size of the sets in the function arguments...

Jakub Tarnawski said...

I *think* that __builtin_popcountl is for longs (which are same as ints on 32-bit platforms). But there is a __builtin_popcountll function for long longs ;)

vexorian said...

It seems that __builtin_popcountl uses base 64 in gcc 4.6 (my computer) but doesn't in TopCoder's version.

Jakub Tarnawski said...

If you have a 64-bit system/compiler, then longs would be 64-bit on your machine.

Mir Wasi Ahmed said...

Wow, I failed SRM 630 Div-1 250 just because of __builtin_popcountll. I used Bron Kerbosch algorithm.

http://community.topcoder.com/stat?c=problem_solution&rm=323292&rd=16061&pm=13284&cr=22754207