Разбор задач Facebook Hacker Cup 2011 Qualification Round

Facebook Hacker Cup 2011 проходит в 4 раунда — квалификационный, два онлайн раунда и финальный, в главном офисе.

Уже завершился квалификационный раунд, анонсированный официально Хабром
Результаты раунда говорят о 5846 игроках, прошедших в первый онлайн тур.
Участникам квалификационного раунда предлагалось 3 задачи, для прохождения достаточно было правильного решения любой из них.
В целях экономии места, перевод условий я сокращу, оставив суть, необходимую для решения. Полные условия доступны в оригинале на английском
<habracut/>
Задача 1. «Double Squares»

Найти число представлений целого числа в виде суммы двух полныых квадратов целых (например: 10=1^2+3^2 — одно разложение, а 25=5^2+0^2=4^2+3^2 два разных разложения).

• Программа должна работать для чисел от нуля до 2147483647

На вход ей подается условие вида:
5
10
25
3
0
1
На который программа в стандартный вывод должна написать:
1
2
0
1
1

• цифра 5 — число последующих строк — по одной на каждое число, к разложению.
• вывести нужно — 5 чисел — количество способов разложения.

На задачу наложено ограничение по времени — отправить ответ нужно до истечения 6 минут с момента скачивания файла заданий, в котором максимум 100 чисел.

Решаем:

Оценка: корень из 2147483647 равен 46340,95 — не так уж и много.
Идея: заполнить массив полными квадратами от 0 до 46341

тогда задача сведется к пробеганию с двух концов массива вовнутрь:

• сумма квадратов больше заданного числа — правую границу сдвигаем влево
• сумма квадратов меньше заданного числа — левую границу сдвигаем вправо
• сумма квадратов равна заданному числу — инкрементируем результат
• границы соединились — выводим ответ, берем следующее число

А пока голова думает, руки успевают набрать убогое решение прямым перебором (обходя массив слева направо и из разности исходного числа и квадрата беря корень).
Приводить код не буду — сэкономим место для более интересных задач.

Задача 2. Peg Game

Между двумя стенками в шахматном порядке закреплены шайбы (красные):



С зеленого кружочка падает монетка, которая налетая на шайбу равновероятно отскакивает левее или правее (от крайней шайбы монетка всегда отскакивает вовнутрь). Падая монетка попадет в голубой кружочек — выход. Если монетку кидали в средний кружок, она может путешествовать вдоль любой стрелочки:



Во входящих данных указан размер «поля» — всегда нечетного числа строк, и любого числа столбцов, и номер выхода, в который нужно попасть монеткой.
За ответ принимают номер окна и вероятность, с которой монетка попадет в заданный выход с наибольшей вероятностью.
Помимо этого, некоторые шайбы удалены (потерялись от времени).

Будем рассматривать поле поменьше, в котором 1 шайба потерялась, а попасть нужно в средний выход:

Решение

Рекурсия с подсчетом всевозможных путей не успеет — максимальный размер поля 99на100 а за отведенные 6 минут нужно успеть просчитать до 100 разных полей, и успеть отправить назад результат.

Ключевая идея:


Идем снизу вверх, от точки выхода — в нее кладем вероятность 1. в нее можем попасть из двух точек, левее-выше и правее-выше. Из этих точек в точку выхода мы попадаем с вероятностью 1/2. Правило сложения вероятностей говорит об их перемножении. Уровень закончили, переходим к следующему: Есть 2 точки, с вероятностями 1/2. Рассматриваем независимо их вклад в следующий:

• В левую точку мы можем попасть только упав справа (сверху шайба), а слева просто пролетим мимо. Из правого «родителя» в нее мы попадаем с 1/2. Опять «складываем» вероятности, т.е. перемножаем 1/2*1/2, получаем 0.25
• В правой точке вероятность прихода от левого родителя 1/2, а от правого — 1, т.к. за игровое поле монетка не выходит — там стенка

Теперь складываем (уже по обычному) полученные вероятности, чтобы получить третий слой, который оказывается последним. (Иначе для каждого элемента с ненулевой вероятностью запускаем аналогичный процесс).
Имеем, что в средний выход можно попасть только кидая монетку из среднего или правого окошка, причем с одинаковой вероятностью.
В формате исходных данный фейсбука, рассматриваемое поле представляется строкой: 3 4 1 1 0

• первые две цифры — размеры поля
• номер выхода (считают с нулевого)
• количество потерянных шайб, такое же количество следующих пар-координат (1 0 означает удаленную первую шайбу из второй строчки)

Теперь реализуем эту идею:

#!/usr/bin/python
#coding=utf-8
 
#ищет "родителей"
def next(y,x,v):
  l=[]
  if (x+y)%2==0: #где запланирована фишка
    l.append((y-1,x,v))
    return  l
  #значит на пустом месте
  if (y-1,x) in skip:#над нами пусто
    l.append((y-1,x,v))
  #но ретернить рано - могли и с боков свалиться
  #проверяем левее
  if x!=0:#не в самом левом столбике
  if x!=0 and x!=size:
    if (y,x-1) not in skip:#левее есть фишка
      if x==1 or (y%2==1 and ( x==2 or x==size)):
        #дополнительные условия - на то, что крестик не скраю
        l.append((y-1,x-1,v))# с самой левой один путь дорога
      else:
        l.append((y-1,x-1,v/2.))# не с самой левой - два пути
  # если в самом левом столбце - падение сверху уже запланировано
  #проверяем правее
  if x!=size:#не в самом правом столбике
    if (y,x+1) not in skip:#правее есть фишка
      if x==size-1 or (y%2==1 and ( x+1==2 or x+1==size-2)):
        l.append((y-1,x+1,v))# с самой правой один путь дорога
      else:
        l.append((y-1,x+1,v/2.))# не с самой правой - два пути
  return l
#перевод входных данных в сквозную декартову адресацию
def rc_to_yx(rs,cs):
  if rs%2==0:
    return (rs,cs*2)
  return (rs,cs*2+1)
f = open('in', 'r')
f.readline()
lines_in=f.readlines()
for inputWords in lines_in:
  skip_l = []
  skip=set(skip_l)
  inputWords = inputWords[0:-1].split(' ')
  inputWords= filter (lambda a: a != "", inputWords)
  r=int(inputWords.pop(0))
  c=int(inputWords.pop(0))
  target=int(inputWords.pop(0))
  s_count=inputWords.pop(0)
  for q in range(int(s_count)):
    rs=inputWords.pop(0)
    cs=inputWords.pop(0)
    skip.add(rc_to_yx(int(rs),int(cs)))
  #Закончили с загрузкой данных, приступаем к вычислениям
  size=c+c-2 #"ширина"слоя, для определения правой границы
  n={}
  n[(r-1,target*2+1)]=1
  for q in range(r-1):
    s=n
    n={}
    for (b,a),v in s.iteritems():
      for (y,x,v) in next(b,a,v):   
        try:
          n[(y,x)]+=v
        except KeyError:
          n[(y,x)]=v
    #print n #дебажный послойный вывод
  #Все уже посчитали, осталось вывести максимальную вероятность
  maxv=0
  maxx=0
  for (y,x),v in n.iteritems():
    if v>maxv:
      maxv=v
      maxx=x
  #Выводим, как хочет фейсбук - с 6 нулями
  print '%(i)d %(d)f' % \
    {"i":(maxx-1)/2, "d":maxv}
print

Задача 3. «Studious Student»
Переставляя слова данного набора составить слово с наименьшим лексикографическим порядком (как в словаре).

Например, из набора: facebook hacker cup for studious students
Нужно получить слово: cupfacebookforhackerstudentsstudious

Решение

Сортируем слова в лексикографическом порядке и выписываем их слитно в одно большое.
Гуглим сортировщик списка на питоне, получаем первые 35 строчек программы:

import sys
 
def sort(words):
  sortedList = []
  for i in range(len(words)):
    word = words[i]
    if not sortedList:
      sortedList.append(word)
    else:
      for j in range(len(sortedList)):
        sortedWord = sortedList[j]
        if isLeftWordBeforeRight(word, sortedWord):
          sortedList.insert(j, word)
          break
        elif j == (len(sortedList) - 1):
          sortedList.append(word)
  return sortedList
 
def isLeftWordBeforeRight(left, right):
  isBefore = False
  if right.startswith(left):
    isBefore = True
  else:
    for n in range(len(left)):
      if n < len(right):
        comparison = compareChars(left[n], right[n])
        if comparison != 0:
          isBefore = comparison < 0
          break  
  return isBefore
 
def compareChars(left, right):
  return alphabet.find(left) - alphabet.find(right)
 
#alphabet = "zyxwvutsrqpomnlkjihgfedcba" # единственная замена - нам нужен прямой порядок
alphabet = "abcdefghijklmnopqrstuvwxyz"
 
f = open('in', 'r')
f.readline()
lines_in=f.readlines()
print
for inputWords in lines_in:
  inputWords = inputWords[0:-1].split(' ') # слова по условию могут быть через несколько пробелов, обрезаем конец - там символ переноса
  trash=inputWords.pop(0) #число слов нам не понадобится
  inputWords= filter (lambda a: a != "", inputWords) #после сплита пробелами удаляем артефакты
  #print inputWords # дебажный вывод
  sorted = sort(inputWords) # сортируем
  for word in sorted:
    sys.stdout.write(word) #печатаем слова слитно
  print #переносим строку
print

Пишем с 36 по 51 строчку — ввод из файла, запуск сортировки, слитный вывод.