SRM 571

This is 3rd SRM I participated in 2013. After failing SRM 568 and SRM 569 with really silly mistakes I decided to ascend my rating finally.

250

Looks very easy and it is. We are given $N$ strings of type "1.mp3", "2.mp3", etc. We need to sort them lexicographically and return top 50 strings. There are bunch of different correct solutions but idea is the same: if $N \le 50$ then we just compute every string and sort resulting array. Else we need to consider some big numbers close to power of ten.

It might sound funny but I managed to put bug in easiest solution. Then reubmitted it for 149 points instead of ~220 points. Regardless huge disappointement I was happy that could submit something working as last two rounds I failed even easy problems.

Challenge phase brought me another 50 points challenging guy with different bug.

500

This problem was about finding clique in a graph of up to $50$ vertices maximizing total weight of picked. Another constraint was: clique should include at least $\frac{2}{3}$ of total number of vertices.

First thing everybody probably noticed: looking for optimal clique is NP-hard problem, so exclude anything polynomial here.

Second is obvious constraint: $\frac{2}{3} \times n \le 16$. It means there is something to do with it. I could not come up with anything better than quite stupid backtracking approach with some sorting for better pruning. It looks like I am still bad in math and it worked slower than expected and failed on system test.

During Challenge phase my solution defended two challenges but it did not help in the end.

I saw several greedy solutions and one DP in my room: all failed. Approach is backtrack but from different end (you do not expect it to be that easy, right?). Someone found Bron-Kerbosch algorithm in wiki but failed. Another approach was greedy solution combined with random shuffles (not first time I notice such randomizing crap work).

In the practice session I could implement correct solution in minutes which leads to well known conclusion: in TopCoder idea of the solution tends to be much harder and more important than implementation details. That is the reason we love it.

Solution: for given subset of vertices find any non-connected pair. If there is no such pair it means we found clique, return sum of subset as the best answer. Else there are two ways: try look at subset with out the first bad vertix or with out the second one. It looks exponential and it is but number of different branches do not exceed $2^{16}$ as we are not interested in small subsets.

In the end

I was one of majority with one solved problem and less than 200 points which brought me tiny amount of rating. It feel like it would take enormous amount of effort to come back to middle-yellowish position.

A lot of people from KZ participated today. Even guys from Palo Alto. Even from Kharkov. Keep it up, guys!

Code

250 - FoxAndMp3

string toStr(Int x) {
  stringstream strm;
  strm << x << ".mp3";
  return strm.str();
}

vector <string> res;
int n;

void doit(Int x) {
  if (x > n)
    return;
  if (res.size() >= min(50, n)) return;

  res.pb(toStr(x));

  for (int i = 0; i < 10; i++) {
    doit(x * 10 + i);
    if (res.size() >= min(50, n)) return;
  }
}

class FoxAndMp3 {
public:
  vector <string> playList(int n) {
    ::n = n;
    if (n <= 50) {
      vector<string> a;
      for (int i = 1; i <= n; i++) {
        stringstream strm;
        strm << i << ".mp3";
        a.pb(strm.str());
      }
      sort(a.begin(), a.end());

      return a;
    }
    for (int i = 1; i <= 9; i++)
        doit(i);

    return res;
  }
};

500 - MagicMolecule

int res, n, need;
vector<int> magicPower;
vector<string>magicBond;
map<Int, int> memo;

int get(Int mask) {
  if (memo.count(mask))
    return memo[mask];
  int &res = memo[mask];
  res = -1;

  if (bitcount(mask) < need)
    return res;

  int badA = -1, badB;

  for (int i = 0; i < n; i++)
    if (mask & (1LL << i))
      for (int j = i + 1; j < n; j++)
        if (mask & (1LL << j))
          if (magicBond[i][j] == 'N') {
            badA = i;
            badB = j;
            break;
          }

  if (badA == -1) {
    res = 0;
    for (int i = 0; i < n; i++)
      if (mask & (1LL << i))
        res += magicPower[i];
    return res;
  }

  return res = max(get(mask ^ (1LL << badA)), get(mask ^ (1LL << badB)));
}

class MagicMolecule {
public:
  int maxMagicPower(vector <int> magicPower, vector <string> magicBond) {
    ::magicBond = magicBond;
    ::magicPower = magicPower;


    res = -1;
    n = (int)magicPower.size();
    for (; need * 3 < 2 * n; need++);

    return get((1LL << n) - 1);
  }
};