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.

CF 168

A. among a[i] and k*a[i] you can have only one of them. If we sort all numbers, then it is always better to choose a[i] since a[i]*k potentially will conflict with a higher number. Some inductive argument will prove this claim. Then it takes only one scan of the sorted array and remember the banned numbers in a c++ stl set. One catch is to use 64 bit integer as k can be 10^9.

B. interesting problem. No solution yet. Here are some observations:
1. There is always a solution. Why? You can first solve a subproblem with only n-1 nodes, and then that subtree is all zero, now you have only one node with nonzero value and it is easy to see how to do the rest.
2. Order of operations do not matter. Actually, if you fix the set of operations, any permutation of ordering give you same end result.
3. Given 2, then at least one leaf node needs to be considered at most once.

facebook hackercup round 3

When it is down to top 100, the competition is tough, as is the problem.

A. given a matrix of conflict M[10][10], M[i][j] = 1 if i and j conflict. Find count of valid numbers with length K or less. K can be 10^18. A number is valid if any two conflicting digits have two other digits between them.

I don't have a solution but here is some idea.

Let C[L][first][second]  be the count of numbers with length at most L and first digit and second digit, both first and second could be zero.

Then C[L][first][second] = sum of C[L-1][second][d] for d = 0 to 9, and first does not conflict with d. (We already know that second does not conflict with d or C[L-1][second][d] is zero)

This is a linear recurrence and since L could be 10^18, this hints to a solution using fast exponentiation. It would be an easy problem if we need only one digit separation, now it is two digits.

Update: watashi's solution, you can map [first][second], a 2d vector into 1d by using a*n+b as coordinator, then the rest is just like a linear recurrence with two dimensions, L, and pair of first and second. Everybody knows fastpow can do this.