Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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 = [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())
#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';
}
}
#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';
}
}
#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';
}
}
@dideler

This comment has been minimized.

Copy link

dideler commented Feb 3, 2013

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()
@Quantris

This comment has been minimized.

Copy link
Owner Author

Quantris commented Feb 3, 2013

@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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.