Solutions for Facebook Hacker Cup 2013 / Round 1 No explanations for now...

card_game.py

import sys

MOD = 1000000007

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

def testcases(cin=sys.stdin):
  m = int(cin.next())
  for _ in xrange(m):
    n, k = map(int, cin.next().split())
    cards = map(int, cin.next().split())
    yield (n, k, cards)

def subsum(n, k, cards):
  ans = 0
  cards.sort()
  for i in xrange(k-1, n):
    ans += cards[i] * choose(i, k-1)
    ans %= MOD
  return ans

MAX_S = 10000
FACTS = [1]
for i in xrange(1, 1+MAX_S):
  FACTS.append((FACTS[-1]*i) % MOD)

def choose(n, k):
  return (FACTS[n]*modInv(FACTS[k]*FACTS[n-k])) % MOD

def modInv(a):
  x, nx, b = 0, 1, MOD
  while a > 0:
    q = b // a
    nx, x = x-q*nx, nx
    a, b = b-q*a, a
  return x

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

dead_pixels.cpp

#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> VI;

// so lazy! (64-bit req. to do this)

int main() {
  int nc; cin >> nc;
  for (int cNum = 1; cNum <= nc; ++cNum) {
    int w, h, p, q, n; cin >> w >> h >> p >> q >> n;
    int x, y, a, b, c, d; cin >> x >> y >> a >> b >> c >> d;

    vector<VI> screen(w+1, VI(h+1));

    for (int i = 0; i < n; ++i) {
      screen[x][y] = 1;
      int tx = (x*a + y*b + 1) % w;
      int ty = (x*c + y*d + 1) % h;
      x = tx; y = ty;
      }

    int pCount = 0;
    for (int i = w-1; i >= 0; --i)
      for (int j = h-1; j >= 0; --j) {
        screen[i][j] += screen[i+1][j] + screen[i][j+1] - screen[i+1][j+1];
        if ((i+p <= w) && (j+q <= h) && (screen[i][j] == screen[i+p][j] + screen[i][j+q] - screen[i+p][j+q]))
          ++pCount;
        }

    cout << "Case #" << cNum << ": " << pCount << '\n';
    }
  }

dead_pixels_lite.cpp

#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VP;

// use sentinels to simplify sweep?

int process(int h, int q, const map<int, int> &activeY) {
  int ret = 0, last = 0;
  for (map<int, int>::const_iterator i = activeY.begin(); i != activeY.end(); ++i) {
    ret += max(0, i->first-last-q+1);
    last = i->first+1;
    }
  ret += max(0, h-last-q+1);
  return ret;
  }

int main() {
  int nc; cin >> nc;
  for (int cNum = 1; cNum <= nc; ++cNum) {
    int w, h, p, q, n; cin >> w >> h >> p >> q >> n;
    int x, y, a, b, c, d; cin >> x >> y >> a >> b >> c >> d;

    VP dead(n); dead[0] = PII(x, y);
    for (int i = 1; i < n; ++i) {
      dead[i].first = (dead[i-1].first*a + dead[i-1].second*b + 1) % w;
      dead[i].second = (dead[i-1].first*c + dead[i-1].second*d + 1) % h;
      }

    sort(dead.begin(), dead.end()); // duplicates are OK

    map<int,int> activeY;
    VP::const_iterator rP = dead.begin();
    VP::const_iterator lP = dead.begin();
    int curL = 0;
    while ((rP != dead.end()) && (rP->first < curL+p)) {
      ++activeY[rP->second];
      ++rP;
      }

    int pCount = 0, curC = process(h, q, activeY);
    while ((rP != dead.end()) || ((lP != dead.end()) && (lP->first < w-p))) {
      int nxtLR = (rP != dead.end()) ? rP->first-p : w;
      int nxtLL = (lP != dead.end()) ? lP->first : w;
      int nxtL = min(nxtLR, nxtLL) + 1;

      pCount += curC*(nxtL-curL);
      curL = nxtL;
      while ((rP != dead.end()) && (rP->first < curL+p)) {
        ++activeY[rP->second];
        ++rP;
        }
      while ((lP != dead.end()) && (lP->first < curL)) {
        --activeY[lP->second];
        if (!activeY[lP->second]) activeY.erase(lP->second);
        ++lP;
        }
      curC = process(h, q, activeY);
      }

    pCount += curC*(w-p+1-curL);

    cout << "Case #" << cNum << ": " << pCount << '\n';
    }
  }

security.cpp

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

typedef vector<int> VI;

bool augment(int m, const vector<VI> &edgeL, vector<int> &match) {
  queue<int> q;
  VI pred(2*m, -1);

  for (int i = 0; i < m; ++i)
    if (match[i] == -1)
      q.push(i);

  while (!q.empty()) {
    int qL = q.size();
    while (qL--) {
      int t = q.front(); q.pop();
      for (VI::const_iterator i = edgeL[t].begin(); i != edgeL[t].end(); ++i)
        if (pred[m+*i] == -1) {
          pred[m+*i] = t;
          q.push(*i);
          }
      }
  
    qL = q.size();
    while (qL--) {
      int t = q.front(); q.pop();
      if (match[m+t] == -1) {
        int v = m+t;
        while (v != -1) {
          match[v] = pred[v];
          match[pred[v]] = v;
          v = pred[pred[v]];
          }
        return true;
        }
      else {
        pred[match[m+t]] = m+t;
        q.push(match[m+t]);
        }
      }
    }
  
  return false;
  }

int bipart(int m, const vector<VI> &edgeL) {
  vector<int> match(2*m, -1);
  int mSize = 0;
  while ((mSize < m) && augment(m, edgeL, match)) ++mSize;
  return mSize;
  }

bool compat(int m, const string &k1, const string &k2, int a, int b) {
  int sL = k1.size() / m;
  for (int k = 0; k < sL; ++k) {
    int i = sL*a + k, j = sL*b + k;
    if ((k1[i] != '?') && (k2[j] != '?') && (k1[i] != k2[j]))
      return false;
    }
  return true;
  }

string solve(int m, string k1, const string &k2) {
  vector<VI> edgeL(m);

  for (int i = 0; i < m; ++i)
    for (int j = 0; j < m; ++j)
      if (compat(m, k1, k2, i, j))
        edgeL[i].push_back(j);

  if (bipart(m, edgeL) != m) return "IMPOSSIBLE";

  int sL = k1.size() / m;
  for (int i = 0; i < m; ++i)
    for (int k = 0; k < sL; ++k)
      if (k1[sL*i+k] == '?') {
        char &c = k1[sL*i+k];
        VI pEdge = edgeL[i];
        for (c = 'a'; c <= 'f'; ++c) {
          edgeL[i].clear();
          for (VI::const_iterator j = pEdge.begin(); j != pEdge.end(); ++j)
            if (compat(m, k1, k2, i, *j))
              edgeL[i].push_back(*j);
          if (bipart(m, edgeL) == m) break;
          }
        }

  return k1;
  }

int main() {
  int nc; cin >> nc;
  for (int cNum = 1; cNum <= nc; ++cNum) {
    int m; cin >> m;
    string k1, k2; cin >> k1 >> k2;

    cout << "Case #" << cNum << ": " << solve(m, k1, k2) << '\n';
    }
  }

Thanks for posting your solutions. I'm especially interested in the Python solution for the card game problem. I had no idea about the existence of yield (or generators for that case) and reading from stdin in Python.

I've never used Python for competitive coding until this Hacker Cup, figured I'd give it a try. Here's my attempted solution. It failed miserably on the judges data, my OS would kill the process because it kept using too many resources. It's also possible I have some errors in the logic.

#!/usr/bin/env python

import itertools
import array

def findsubsets(S,m):
    return set(itertools.combinations(S, m))

def main():
    T = input()
    for i in xrange(1, T+1):
        N, K = [int(x) for x in raw_input().split()]
        #a = []
        a = array.array('I') # try to speed it up with an array
        [a.append(int(x)) for x in raw_input().split()]

        max_sum = 0
        #s = set(a)
        for ss in findsubsets(a,K):
            max_sum += max(ss)
            #ss.clear()

        print "Case #{}: {}".format(i, max_sum % 1000000007)

if __name__ == '__main__':
    main()

@dideler I'm actually still learning Python, and try to use it for these kinds of problems when possible to get more practice with it. Also, coming from C++, it is often nice not to have to worry about integer overflow. As you can see I did switch back to C++ for the other two; I am still most comfortable there.

I like using yield but sometimes I probably overuse it :) Reading from stdin is something that I've experimented a bit with; it can be quite the bottleneck sometimes (though for Hacker Cup probably not) -- the method I used above is not necessarily the fastest but it's reasonably flexible, and I prefer to isolate that stuff from the rest of the code through the "testcases()" generator.

As for your solution, the I'd say the issue is using "itertools.combinations". For example if N = 10000 and K = 5000, there are close to 1.6 * 10^3008 k-element subsets. So you need a different algorithm than just producing all the subsets and processing each one. Not to say that itertools.combinations isn't useful when you actually do want all the combinations one by one.

Probably by examining my code you can see how I avoided considering each subset individually.

EDIT: I meant to mention that the reason I write def testcases(cin=sys.stdin): is because in some problems, I want to read a number at a time instead of a line at a time (showing my C++ bias here). In that case we can wrap a generator around sys.stdin that splits lines into numbers and yields them one at a time, and then use that as the cin in testcases.