Pull to refresh

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

Python *
Sandbox
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.
image

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

Задача 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.

Плюсовать этот коммент
Tags:
Hubs:
Total votes 50: ↑42 and ↓8 +34
Views 4.4K
Comments Comments 75