Friday, February 22, 2013

TC 571

p250 given a prefix and try next digit from 0 to 9, stop if current number is over n.
vector ans;

void rec(string pre, long long prod, int n)
{
  if (prod > n) return;
  ans.push_back(pre);
  for (ch = '0'; ch <= '9'; ++ch)
    rec(pre+ch, prod*10+ch-'0', n);
}

p500 need to find weighted maximum clique, yes, find max clique for n=50. The solution uses backtracking and it builds maximum clique containing a particular vertex from 1 to n, for each center, use dfs to explore next vertex to expand. This runs within time limit.

Some implementation tip: use bitmask to remember vertices in clique already, since 50 fits in 64 bits.

No comments:

Post a Comment