Solutions for Facebook Hacker Cup Round 2 I got stuck on problem 2 during the actual round due to a bit of a nasty off-by-one error (fixed below); in retrospect it would have been better to try #3 to have a chance at qualifying. Added solution to problem #3; essentially a standard DP on a tree + a bit of cleverness to ensure proper counting. Dur…

cake_cutting.py

import sys

def main():
  for (i, (n, a)) in enumerate(testcases()):
    print "Case #{0}: {1}".format(i+1, regions(n, a))

def testcases(cin=sys.stdin):
  nc = int(cin.next())
  for _ in xrange(nc):
    nums = map(int, cin.next().split())
    yield (nums[0], nums[1:])

def regions(n, a):
  n_verts = sum(a)
  n += n_verts

  base = (n*n + n + 2) // 2
  return (base - 2*n_verts)

if __name__ == "__main__": sys.exit(main())

permutations.cpp

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

typedef long long int LL;
typedef pair<int, int> PII;

const int MOD = 1000000007;
const int MAX_N = 1000;

struct node {
  int subSize;
  vector<PII> edges;
  vector<LL> stat;

  LL ways(int a, int dir) const {
    if (dir == -1)
      return stat[a];
    else
      return (MOD + stat.back()-stat[a]) % MOD;
    }
  };

LL choose[MAX_N+1][MAX_N+1];

LL recurse(vector<node> &g, int v = 0, int p = -1) {
  g[v].subSize = 1;
  g[v].stat.push_back(0);
  g[v].stat.push_back(1);

  for (vector<PII>::const_iterator i = g[v].edges.begin(); i != g[v].edges.end(); ++i)
    if (i->first != p) {
      recurse(g, i->first, v);

      int &na = g[v].subSize, &nb = g[i->first].subSize;

      vector<LL> nStat(1+na+nb);
      for (int a = 1; a <= na; ++a)
        for (int b = 0; b <= nb; ++b) {
          LL vb = g[i->first].ways(b, i->second);
          LL t = (g[v].stat[a]*vb) % MOD;
          t = (t * choose[a+b-1][b]) % MOD;
          t = (t * choose[na+nb-a-b][nb-b]) % MOD;

          nStat[a+b] = (nStat[a+b] + t) % MOD;
          }

      na += nb;
      g[v].stat.swap(nStat);
      }

  for (int i = 1; i <= g[v].subSize; ++i)
    g[v].stat[i] = (g[v].stat[i] + g[v].stat[i-1]) % MOD;

  return g[v].stat.back();
  }

int main() {
  for (int i = 0; i <= MAX_N; ++i) {
    choose[i][0] = choose[i][i] = 1;
    for (int j = 1; j < i; ++j)
      choose[i][j] = (choose[i-1][j-1] + choose[i-1][j]) % MOD;
    }

  int nc; cin >> nc;
  for (int cNum = 1; cNum <= nc; ++cNum) {
    int n; cin >> n;

    vector<node> g(n);
    for (int i = 1; i < n; ++i) {
      int a, b; char c; cin >> a >> c >> b;
      int v = (c == '<') ? 1 : -1;

      g[a].edges.push_back(PII(b, v));
      g[b].edges.push_back(PII(a, -v));
      }

    cout << "Case #" << cNum << ": " << recurse(g) << '\n';
    }
  }

roboelection.cpp

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long int LL;

inline LL roundup(LL n, LL d) { return (n+d-1) / d; }

inline LL skipR(LL v, LL n, LL k, LL p) { return roundup(100*v-n*(100-p), k*(100-p)) - 1; }

LL nRounds(LL n, LL k, LL p) {
  if (p == 100) return (n / k);

  LL tn = (n % k) - k, tv = tn;
  while (tn < n) {
    tn += k; tv = tn;
    LL t = max(0LL, skipR(tv, tn, k, p));
    tn += t*k;
    }

  return 1 + ((n-tv) / k);
  }

int main() {
  int nc; cin >> nc;
  for (int cNum = 1; cNum <= nc; ++cNum) {
    LL n, k, p; cin >> n >> k >> p;

    cout << "Case #" << cNum << ": " << nRounds(n, k, p) << '\n';
    }
  }