Facebook Hacker Cup 2013 qualification solutions

balanced_smileys.py

import sys
from collections import Counter
import string,re
input_stream = sys.stdin
cases = int(input_stream.readline())

def is_understandable(input_str):
  _string = input_str.replace(':)', '').replace(':(', '')
  stack = []
  for char in _string:
    if char == '(':
      stack.append(char)
    elif char == ')' and len(stack) > 0 and stack.pop() != '(':
      return 'NO'
  if len(stack)> 0:
    if input_str[0] == '(': 
      return 'YES' 
    else: 
      return 'NO'
  else:
    return 'YES'

for i in xrange(cases):
  case_str = input_stream.readline().strip()
  print("Case #{0}: {1}".format(i+1, is_understandable(case_str)))

beautiful_strings.py

import sys
from collections import Counter
import string,re
input_stream = sys.stdin
cases = int(input_stream.readline())

def find_max_beauty(string):
  items = sorted(dict(Counter(list(string))).values())
  char_beauties = range(26,0,-1)
  sum = 0
  for i,val in enumerate(reversed(items)):
    sum += val*char_beauties[i]
  return sum

for i in xrange(cases):
  pattern = re.compile('[\W_]+')
  case_str = input_stream.readline().upper()
  case_str = re.sub(pattern,'',case_str)
  print("Case #{0}: {1}".format(i+1, find_max_beauty(case_str)))

finding_min.py

import sys
input_stream = sys.stdin
cases = int(input_stream.readline())
""" 
Disclosure: I was struggling with the indexing idea.. 
and I got influenced by the solution in a stackoverflow post to improve my implementation.
It still reads like that solution instead of mine.. 
I was out of time anyway after submitting my naiver solution, so didn't get to take advantage of sneaking on the interwebs
"""

def next_pointer(lst, start):
    idx = start
    # 0 indexed
    out = start - 1
    while idx < len(lst) and lst[idx]:
        out = idx
        idx += 1
    return out



def line_list(input_stream):
  return map(int,input_stream.readline().strip().split())


for t in xrange(cases):
  n,k = line_list(input_stream)
  a,b,c,r = line_list(input_stream)
  # Storing 10^9 is expensive, do it in chunks
  # 4 worked for the input from facebook
  m = [0] * (4*k)
  # This is the lookup set guaranteed to not be > len(k)
  # Lookup is used more like a dictionary.. 
  # Each index stores the number of occurences of the value
  lookup = [0] * (k+1)
  m[0] = a
  if m[0] <= k:
      lookup[m[0]] = 1
  for i in xrange(1, k):
      # Linear Congruential Generator
      m[i] = (b * m[i-1] + c) % r
      if m[i] < k+1:
          lookup[m[i]] += 1

  pointer = next_pointer(lookup, 0)
  m[k] = pointer + 1
  pointer = next_pointer(lookup, pointer+2)

  for i in xrange(k+1, n):
      # Is the number > the index.. and have we seen it before?
      if m[i-k-1] > pointer or lookup[m[i-k-1]] > 1:
          m[i] = pointer + 1
          # If the item isn't in the range we're tracking, 
          # decrement the counter at that index.. 
          if m[i-k-1] <= k:
              lookup[m[i-k-1]] -= 1
          lookup[m[i]] += 1
          pointer = next_pointer(lookup, pointer+2)
      else:
          m[i] = m[i-k-1]
      if pointer == k:
          break
  
  if pointer != k:
    out = m[n-1]
  else:
    out = m[i-k + (n-i+k+k) % (k+1)]
  print 'Case #%d: %d' % (t+1, out)

This breaks your balanced smileys: () :) () (
Should be "NO".

Also don't post solutions until contest is over.