Solutions to Facebook Hacker Cup Round 1 problems (in Python)

_hackercup_2013_round_1.rst

Card Game

John is playing a game with his friends. The game's rules are as follows: There is deck of N cards from which each person is dealt a hand of K cards. Each card has an integer value representing its strength. A hand's strength is determined by the value of the highest card in the hand. The person with the strongest hand wins the round. Bets are placed before each player reveals the strength of their hand.

John needs your help to decide when to bet. He decides he wants to bet when the strength of his hand is higher than the average hand strength. Hence John wants to calculate the average strength of ALL possible sets of hands. John is very good at division, but he needs your help in calculating the sum of the strengths of all possible hands.

Problem You are given an array a with N ≤ 10 000 different integer numbers and a number, K, where 1 ≤ K ≤ N. For all possible subsets of a of size K find the sum of their maximal elements modulo 1 000 000 007.

Input

The first line contains the number of test cases T, where 1 ≤ T ≤ 25 Each case begins with a line containing integers N and K. The next line contains N space-separated numbers 0 ≤ a [i] ≤ 2 000 000 000, which describe the array a.

Output

For test case i, numbered from 1 to T, output "Case #i: ", followed by a single integer, the sum of maximal elements for all subsets of size K modulo 1 000 000 007.

Example

For a = [3, 6, 2, 8] and N = 4 and K = 3, the maximal numbers among all triples are 6, 8, 8, 8 and the sum is 30.

Security

You are designing a new encryption system that works in the following way:

For server-client communication you need a key k, composed of m sections, each of length l, and the key consists only of lowercase characters in the set {a, b, c, d, e, f}. The server has a key k1 and the client has a key k2 where:

k1 = f(k). f is a function that receives a key and replace some random letters by ? indicating that those characters can be any lowercase letter of the set described before.

k2 = f(g(k)). g is a function that takes a key and produces a random permutation of its m sections. And f is the function defined above.

For example, let m = 3, l = 2:

f('abacbc') = '?ba??c'
g('abacbc') = 'acbcab' (each section was moved one place to the left).

Your task is given k1 and k2, find key k. If there are several solutions, print the lexicographically smallest key. And if there is no solution at all, print "IMPOSSIBLE" (without the quotes).

Input description:

The first line has a single integer T, which corresponds to the number of test cases. T test cases follows: the first line of the test case corresponds to the integer m, the second line contains the string k1 and the third line contains the string k2.

Constraints:

T <= 20

0 < <= 100

0 < m <= 50

=

It is guaranteed that m is always a divisor of

k1 and k2 consist of {a, b, c, d, e, f, ?}

Output description:

For test case i, numbered from 1 to T, output "Case #i: ", followed by the lexicographically smallest key or "IMPOSSIBLE".

Dead Pixels

John's friend Peter purchases a new high resolution monitor with dimension W * H where W is the number of pixels in each row (i.e. width) and H is the number of pixels in each column (i.e. height).

However, there are N dead pixels on the monitor. The i-th dead pixel is located at (x[i], y[i]). (0, 0) is the top-left pixel and (W - 1, H - 1) is the bottom-right pixel. The locations of the dead pixels could be generated by 6 given integers X, Y, a, b, c and d by the following rules. If 2 pixels are at the same location, they are considered the same. It is possible that there are less than N distinct dead pixels:

x[0] = X
y[0] = Y
x[i] = (x[i - 1] * a + y[i - 1] * b + 1) % W (for 0 < i < N)
y[i] = (x[i - 1] * c + y[i - 1] * d + 1) % H (for 0 < i < N)

Peter connects his monitor to his computer and opens an image with dimension P (width) * Q (height). How many unique positions can the image be placed so that it can be displayed perfectly (i.e. all pixels of the picture are shown on the monitor)? The image cannot be rotated.

Input

The first line contains an integer T, which is the number of test cases. Then T test cases follow. Each test case contains 11 integers W, H, P, Q, N, X, Y, a, b, c, d.

Output

For each of the test cases numbered in order from 1 to T, output "Case #", followed by the case number (with 1 being the first test case), followed by ": ", followed by an integer which is the number of different possible positions for the poster.

Constraints

1 ≤ T ≤ 20

1 ≤ W, H ≤ 40 000

1 ≤ P ≤ W

1 ≤ Q ≤ H

1 ≤ N ≤ min(1 000 000, W * H)

1 ≤ a, b, c, d ≤ 100

0 ≤ X < W

0 ≤ Y < H

cardgame.py

MODULO = 1000000007


def num_combinations(n, k):
    result = 1
    for i in range(n - k + 1, n + 1):
        result *= i
    for i in range(1, k + 1):
        result /= i
    return result

    
def cardgame(cards, k):
    result = 0
    cards.sort()

    # We need to calculate combinations in O(1) time for each card
    combinations = 1
    
    for i, card in enumerate(cards):
        # Each card will be maximum in num_combinations(i - 1, k - 1) hands
        if i + 1 < k:
            continue
        if i - k >= 0:
            combinations *= i
            combinations /= i - k + 1
        
        result += card * combinations
        result %= MODULO
    return result
        

def read_numbers(line):
    if line[-1] == '\n':
        line = line[:-1]
    return [int(x) for x in line.split()]


if __name__ == '__main__':
    import sys
    case_count = int(sys.stdin.readline()[:-1])
    for i in range(1, case_count + 1):
        n, k = read_numbers(sys.stdin.readline())
        cards  = read_numbers(sys.stdin.readline())
        print "Case #{}: {}".format(i, cardgame(cards, k))
        

deadpixels.py

# Requires: bintrees 0.3.0 <http://pypi.python.org/pypi/bintrees/0.3.0>
from bintrees import RBTree 


def generate_pixels(W, H, N, X, Y, a, b, c, d):
    pixels = set()
    x, y = X, Y
    pixels.add((x, y))
    for n in range(N - 1):
        x_new, y_new = (x * a + y * b + 1) % W, (x * c + y * d + 1) % H
        x, y = x_new, y_new
        pixels.add((x, y))
    return pixels


def deadpixels(monitor_width, monitor_height, image_width, image_height, pixels):
    pixels = list((x, 'A', y) for (x, y) in pixels) + list((x + image_width, 'Z', y) for (x, y) in pixels)
    pixels.sort(reverse=True)

    y_combinations = monitor_height - image_height + 1
    intervals = RBTree({-1: 10000, monitor_height: 10000})
    result = 0
    
    for w in range(monitor_width):
        while len(pixels) and pixels[-1][0] == w:
            x, event, y = pixels.pop()

            if event == 'A':
                old_y = intervals.get(y)
                if old_y:
                    intervals[y] = old_y + 1
                    continue
                else:
                    intervals[y] = 1

                succ_y = intervals.succ_key(y)
                prev_y = intervals.prev_key(y)

                old_combinations = max(0, succ_y - prev_y - image_height)
                new_combinations = max(0, y - prev_y - image_height) + max(0, succ_y - y - image_height)

            elif event == 'Z':
                old_y = intervals.get(y)
                if old_y and old_y > 1:
                    intervals[y] = old_y - 1
                    continue
                    
                succ_y = intervals.succ_key(y)
                prev_y = intervals.prev_key(y)

                old_combinations = max(0, y - prev_y - image_height) + max(0, succ_y - y - image_height)
                new_combinations = max(0, succ_y - prev_y - image_height)
                
                intervals.remove(y)

            y_combinations = max(0, y_combinations + new_combinations - old_combinations)

        if w + 1 >= image_width:
            result += y_combinations
        
    return result
    

def read_numbers(line):
    if line[-1] == '\n':
        line = line[:-1]
    return [int(x) for x in line.split()]


if __name__ == '__main__':
    import sys
    case_count = int(sys.stdin.readline()[:-1])
    for i in range(1, case_count + 1):
        W, H, P, Q, N, X, Y, a, b, c, d = read_numbers(sys.stdin.readline())
        pixels = generate_pixels(W, H, N, X, Y, a, b, c, d)
        print "Case #{}: {}".format(i, deadpixels(W, H, P, Q, pixels))

security.py

from itertools import izip_longest

    
def grouper(n, iterable, fillvalue=None):
    "Collect data into fixed-length chunks or blocks"
    # grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx
    args = [iter(iterable)] * n
    return izip_longest(fillvalue=fillvalue, *args)


def match_groups(g1, g2):
    result = {}
    for i in range(len(g1)):
        if g1[i] == '?' and g2[i] == '?':
            continue
        elif g1[i] == '?':
            result[i] = g2[i]
        elif g2[i] == '?':
            result[i] = g1[i]
        elif g1[i] != g2[i]:
            return None
    return result


def find_max_matching(graph):
    pairs = {}
    used = set()

    # Create full adjacency list
    adjacency = dict(graph)
    for v, neighbours in graph.items():
        for w in neighbours:
            adjacency.setdefault(w, []).append(v)

    def kuhn(v):
        if v in used:
            return False
        used.add(v)
        
        for w in adjacency[v]:
            if w not in pairs or kuhn(pairs[w]):
                pairs[w] = v
                return True
        return False
            
    for v in graph:
        used = set()
        kuhn(v)

    return pairs


def find_max_lexi(k1_sections, graph):
    pairs = {}
    for v in sorted(graph.keys()):
        for w in graph[v]: # adjacent
            adjacent = graph[v]
            del graph[v]
            removed = []
            for x, adj in graph.items():
                if w in adj:
                    removed.append(x)
                    adj.remove(w)
            
            match = find_max_matching(graph)
            if len(match) == len(k1_sections) - len(pairs) - 1:
                pairs[w] = v
                break

            # Readd v and w to the graph
            graph[v] = adjacent
            for x in removed:
                graph[x].append(w)

    return pairs

    
def apply_group_match(group1, group2):
    result = []
    for i in range(len(group1)):
        if group1[i] == '?' and group2[i] == '?':
            result.append('?')
        elif group1[i] == '?':
            result.append(group2[i])
        else:
            result.append(group1[i])
    return ''.join(result)


def apply_result(k1_sections, k2_sections, result):
    for i2, i1 in result.items():
        i2 = i2 - len(k1_sections)
        k1_sections[i1] = apply_group_match(k1_sections[i1], k2_sections[i2])


def security(k1, k2, m):
    section_len = len(k1) / m
    k1_sections = [''.join(g) for g in grouper(section_len, k1)]
    k2_sections = [''.join(g) for g in grouper(section_len, k2)]
    k2_sections.sort()

    # Construct a list of lists of possible matches between groups
    matches = {}
    for g1, group1 in enumerate(k1_sections):
        matches[g1] = []
        for g2, group2 in enumerate(k2_sections):
            m = match_groups(group1, group2)
            if m is not None:
                matches[g1].append(g2 + len(k1_sections))

    match = find_max_lexi(k1_sections, matches)
    if len(match) < len(k1_sections):
        return None

    apply_result(k1_sections, k2_sections, match)
    return ''.join(k1_sections).replace('?', 'a')


if __name__ == '__main__':
    import sys
    case_count = int(sys.stdin.readline()[:-1])
    for i in range(1, case_count + 1):
        m = int(sys.stdin.readline()[:-1])
        k1 = sys.stdin.readline()
        if k1[-1] == '\n':
            k1 = k1[:-1]
        k2 = sys.stdin.readline()
        if k2[-1] == '\n':
            k2 = k2[:-1]
        result = security(k1, k2, m)
        print "Case #{}: {}".format(i, result if result is not None else 'IMPOSSIBLE')
        

Hi , I tried following approach doing something like a[i] * n-1Ck-1 + a[i+1] n-2Ck-1 till n = k and it does give sample output as per the sample input ..but when i run the code against the input file it takes say something about 20 minutes or more to process all the data ..

here's my code

import math 

MD = 1000000007
def stirling(n):

    return math.sqrt(2*math.pi*n)*(n/math.e)**n

def ncr(n,r):    
    return (stirling(n)/stirling(r)/stirling(n-r) if n>20000000  else
            math.factorial(n)/math.factorial(r)/math.factorial(n-r))

def solve(inp,deck,hand):

  a = inp
  a.sort()
  a.reverse()
  k = hand
  l = deck - 1
  tot = 0


  for i in xrange(len(a)):
      tot += a[i] * ncr(l,k-1) # a[0] * n-1 C k-1 + a[1] * n-2Ck-1 +.. for n = r in nCr
      if tot > md:
          tot = tot % md
      if l == (k-1):
          break
      l -= 1
      tot %= MD
  return tot


filename = open("card_game.txt",'ru')
cases = map(int,filename.readline().split())

for cs in xrange(cases[0]):
  deck,hand = map(int,filename.readline().split()m)
  inp = map(int, filename.readline().split())

  print ('Case #%d : %d' % (cs,solve(inp,deck,hand)))

@aregee: It's probably calculating ncr repeatedly, that's killing the performance of your program. It did when I tried it! Instead of calculating ncr(n, k) from scratch each time, you can get it by multiplying ncr(n - 1, k) by a simple fraction. See line 24 of cardgame.py.