My solutions to the problems from Facebook HackerCup 2013 Round 1

card_game.rb

MOD = 1000000007
MAX = 10000

$dp = Array.new(MAX+1)
$dq = Array.new(MAX+1)

$dp[0] = 1
$dq[0] = 1

def inv(a,n)
  ans = 1
  while n > 0
    ans = (ans * a) % MOD if (n & 1) == 1
    a = (a * a) % MOD
    n >>= 1
  end
  ans
end

MAX.times do |i|
  $dp[i+1] = ($dp[i] * (i+1) ) % MOD
  $dq[i+1] = (inv(i+1,MOD-2) * $dq[i]) % MOD
 end

def comb(n,k)
  return 0 if k < 0 or k > n
  return (((($dp[n] * $dq[n-k]) % MOD) * $dq[k]) % MOD)
end

gets.to_i.times do |c|
  n, k = gets.split.map(&:to_i)
  a = gets.split.map(&:to_i).sort
  ans = 0
  a.each_with_index do |e,i|
    ans = (ans + ((comb(i,k-1) * e) % MOD)) % MOD
  end
  puts "Case \##{c+1}: #{ans}"
end

dead_pixels.cpp

#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;

#define PII pair<int,int>

int main(void)
{
	int T;
	cin >> T;
	for (int C = 1; C <= T; C++)
	{
		int W, H, P, Q, N , X, Y, a, b, c, d;
		cin >> W >> H >> P >> Q >> N >> X >> Y >> a >> b >> c >> d;
		vector < PII > p(N);
		p[0] = PII(X,Y);
		for (int i = 1; i < N; i++)
		{
			int aux = X;
			X = (aux * a + Y * b + 1) % W;
			Y = (aux * c + Y * d + 1) % H;
			p[i] = PII(X,Y);
		}
		sort(p.begin(),p.end());
		vector < int > line(H,-1);
		int i = 0, ans = 0;
		for (;i < N;)
		{
			int f = p[i].first, l = max(0,p[i].second - Q + 1), r = p[i].second;
			for (++i;i < N; i++)
				if (p[i].first > f)	break;
				else
				{
					int A = max(0,p[i].second - Q + 1);
					if ( l <= A && A <= r)
						r = max(r,p[i].second);
					else
					{
						for (int k = l; k <= r; k++)
						{
							if ( k + Q <= H && line[k] >= 0)
								ans += min(P,f-line[k]) - max(0,min(f,P-1)-line[k]);
							line[k] = f;
						}
						l = A, r = p[i].second;
					}
				}
			for (int k = l; k <= r; k++)
			{
				if ( k + Q <= H && line[k] >= 0)
					ans +=  min(P,f-line[k]) - max(0,min(f,P-1)-line[k]);
				line[k] = f;
			}
		}
		for (int k = 0; k + Q <= H; k++)
			if (line[k] >= 0)	ans += min(P,W-line[k])- max(0,min(W,P-1)-line[k]);
		cout << "Case #" << C << ": " << ( (W-P+1)*(H-Q+1) - ans) << endl;
	}
	return 0;
}

security.rb

require 'set'
g = nil
INF = 5 * (6 ** 110)
CONS = ('a'..'f').to_a.reverse

class Hungarian
	def improve_labels(val)
		@s.each { |x| @lu[x] -= val}
		@v.each do |vl|
			if @t.has_key? vl
				@lv[vl] += val
			else
				@min_slack[vl][0] -= val
			end
		end
	end
	
	def improve_matching(y)
		x = @t[y]
		if @mu.has_key? x
			improve_matching(@mu[x])
		end
		@mu[x] = y
		@mv[y] = x
	end

	def slack(x,y)
		@lu[x] + @lv[y] - @w[x][y]
	end
	
	def augment
		loop do
			p, vl = @v.select{ |u| not @t.has_key? u}.map { |x| [@min_slack[x],x] }.min
			improve_labels(p[0]) if p[0] > 0
			@t[vl] = p[1]
			if @mv.has_key? vl
				u1 = @mv[vl]
				@s.add u1
				@v.each do |v1|
					@min_slack[v1] = [slack(u1,v1),u1] if not (@t.has_key? v1) and @min_slack[v1][0] > slack(u1,v1)
				end
			else
				improve_matching(vl)
				break
			end
		end
	end
	def max_matching(w)
		@w = w
		@n = w.length
		@u = @v = (0..(@n-1))
		@lu = @u.map { |x| w[x].max }
		@lv = @v.map { 0}
		@mu = {}
		@mv = {}
		while @mu.size < @n
			free = @v.select{|x| not (@mu.has_key? x)}
			u0 = free[0]
			@s = Set.new
			@s.add(u0)
			@t = {}
			@min_slack = @v.map { |x| [slack(u0,x),u0] }
			augment
		end
		val = @lu.inject(:+) + @lv.inject(:+)
		return @mu
	end
end

gets.to_i.times do |c|
	m = gets.to_i
	k1 = gets.strip; k2 = gets.strip; n = k1.length / m
	$g = Array.new(m).map!{Array.new(m)}
	sv = Array.new(m).map!{Array.new(m)}
	m.times do |i|
		m.times do |j|
			arr = []; ac = ""
			flag = false
			n.times do |k|
				if k1[i*n+k] != '?' and k2[j*n+k] != '?' and k1[i*n+k] != k2[j*n+k]
					flag = true
					$g[i][j] = -INF
					break
				elsif k1[i*n+k] != '?'
					ch = k1[i*n+k]
				elsif k2[j*n+k] != '?'
					ch = k2[j*n+k]
				else
					ch = 'a'
				end
				arr << CONS.find_index(ch) * ( 6 ** (100 - (i*n+k)))
				ac += ch
			end
			$g[i][j] = arr.inject(:+) if not flag
			sv[i][j] = ac if not flag
		end
	end
	ans = Hungarian.new.max_matching($g).map{ |v,i|  sv[v][i]}
	puts "Case \##{c+1}: #{(ans.all? ? ans.join : "IMPOSSIBLE")}"
end