Instantly share code, notes, and snippets.

# Quantris/card_game.py Created Feb 3, 2013

Solutions for Facebook Hacker Cup 2013 / Round 1 No explanations for now...
 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 =  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())
 #include #include using namespace std; typedef vector 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 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'; } }
 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.