Разбор задач Hacker Cup Qualification Round + перенос Facebook Hacker Cup Online Round I

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

Квалификационный раунд, анонсированный официально Хабром завершился успешно.
Результаты раунда говорят о 5846 игроках, прошедших в первый онлайн тур.
Участникам квалификационного раунда предлагалось 3 задачи, для прохождения достаточно было правильного решения любой из них.

А вот первый онлайн раунд, прервав ближе к завершению, перенесли из-за технических проблем минимум на неделю:
We've decided to push back the remaining subrounds of round 1 until we are sure that they can run smoothly. Updates will follow here, but you can safely assume that the subrounds will not occur at least until next weekend.


В целях экономии места, перевод условий я сокращу, оставив суть, необходимую для решения. Полные условия доступны в оригинале на английском.

Задача 1. «Double Squares»

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

• Диапазон входящих чисел от нуля до 2147483647

На входящие числа:
10 25 3 0 1
Правильный ответ программы:
1 2 0 1 1
На задачу наложено ограничение по времени — отправить ответ нужно до истечения 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 означает удаленную первую шайбу из второй строчки)

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

1. #!/usr/bin/python
2. #coding=utf-8
3.  
4. #ищет "родителей"
5. def next(y,x,v):
6.   l=[]
7.   if (x+y)%2==0: #где запланирована фишка
8.     l.append((y-1,x,v))
9.     return  l
10.   #значит на пустом месте
11.   if (y-1,x) in skip:#над нами пусто
12.     l.append((y-1,x,v))
13.   #но ретернить рано - могли и с боков свалиться
14.   #проверяем левее
15.   if x!=0:#не в самом левом столбике
16.   if x!=0 and x!=size:
17.     if (y,x-1) not in skip:#левее есть фишка
18.       if x==1 or (y%2==1 and ( x==2 or x==size)):
19.         #дополнительные условия - на то, что крестик не скраю
20.         l.append((y-1,x-1,v))# с самой левой один путь дорога
21.       else:
22.         l.append((y-1,x-1,v/2.))# не с самой левой - два пути
23.   # если в самом левом столбце - падение сверху уже запланировано
24.   #проверяем правее
25.   if x!=size:#не в самом правом столбике
26.     if (y,x+1) not in skip:#правее есть фишка
27.       if x==size-1 or (y%2==1 and ( x+1==2 or x+1==size-2)):
28.         l.append((y-1,x+1,v))# с самой правой один путь дорога
29.       else:
30.         l.append((y-1,x+1,v/2.))# не с самой правой - два пути
31.   return l
32. #перевод входных данных в сквозную декартову адресацию
33. def rc_to_yx(rs,cs):
34.   if rs%2==0:
35.     return (rs,cs*2)
36.   return (rs,cs*2+1)
37. f = open('in', 'r')
38. f.readline()
39. lines_in=f.readlines()
40. for inputWords in lines_in:
41.   skip_l = []
42.   skip=set(skip_l)
43.   inputWords = inputWords[0:-1].split(' ')
44.   inputWords= filter (lambda a: a != "", inputWords)
45.   r=int(inputWords.pop(0))
46.   c=int(inputWords.pop(0))
47.   target=int(inputWords.pop(0))
48.   s_count=inputWords.pop(0)
49.   for q in range(int(s_count)):
50.     rs=inputWords.pop(0)
51.     cs=inputWords.pop(0)
52.     skip.add(rc_to_yx(int(rs),int(cs)))
53.   #Закончили с загрузкой данных, приступаем к вычислениям
54.   size=c+c-2 #"ширина"слоя, для определения правой границы
55.   n={}
56.   n[(r-1,target*2+1)]=1
57.   for q in range(r-1):
58.     s=n
59.     n={}
60.     for (b,a),v in s.iteritems():
61.       for (y,x,v) in next(b,a,v):  
62.         try:
63.           n[(y,x)]+=v
64.         except KeyError:
65.           n[(y,x)]=v
66.     #print n #дебажный послойный вывод
67.   #Все уже посчитали, осталось вывести максимальную вероятность
68.   maxv=0
69.   maxx=0
70.   for (y,x),v in n.iteritems():
71.     if v>maxv:
72.       maxv=v
73.       maxx=x
74.   #Выводим, как хочет фейсбук - с 6 нулями
75.   print '%(i)d %(d)f' % \
76.     {"i":(maxx-1)/2, "d":maxv}
77. print

* This source code was highlighted with Source Code Highlighter.

Задача 3. «Studious Student»

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

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

Решение

(удалил неправильное решение)

Решение от хабраюзера funca, сложность О(N!)

1. from itertools import permutations
2. source = "jibw ji jp bw jibw"
3. words = source.split()
4. answer = min("".join(combination) for combination in permutations(words))

* This source code was highlighted with Source Code Highlighter.

По условию N<=9, факториальная сложность успевает отлично
Плюсовать этот его коммент


Решение от хабраюзера Skiminok сложность O(N log N)

1. from functools import cmp_to_key
2. def comp(a, b):
3.   return -1 if a + b < b + a else 1 if a + b > b + a else 0
4. def solve(s):
5.   return "".join(sorted(s.split(), key = cmp_to_key(comp)))

* This source code was highlighted with Source Code Highlighter.

Плюсовать этот его коммент

Более короткая версия на лямбде от funca

1. def solve(s):
2.   return "".join(sorted(s.split(), cmp=lambda a, b: cmp(a+b, b+a)))

* This source code was highlighted with Source Code Highlighter.

Плюсовать этот коммент