Talismanium Jan 15 2011 at 22:28

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

5 min

5.1K

Python*

From sandbox

+34

Comments 75

eigrad Jan 16 2011 at 00:28

Не пойму, почему решение третьего задания не выглядит примерно так?

#!/usr/bin/env python
# coding: utf-8

"""
Task 3. Studious Student
"""

def solve(s):
    s = s[:-1].split()
    s.sort()
    return "".join(s)

if __name__ == "__main__":
    for task in open('in'):
        print ("%s\n" % solve(task))

Talismanium Jan 16 2011 at 09:21

Спасибо!
мой косяк.
исправил решение

mihaild Jan 16 2011 at 00:34

Во-первых, не очень понятно, зачем в 3й писать сортировку вручную
Во-вторых, на тесте из условия Ваше решение работает неправильно:
jibw ji jp bw jibw
Выдает bwjijibwjibwjp
Хотя можно bwjibwjibwjijp
PS. Если не ошибаюсь, «питонично» такое решение можно записать как

answer = "".join(sorted(raw_input().split(" ")[1:]))

eigrad Jan 16 2011 at 00:47

чтобы автор не придрался к вводу/выводу:

print("\n".join([ "".join(sorted(i.split())) for i in open('in') ]))

Talismanium Jan 16 2011 at 01:32

talis@talis-t4:~/facebook/words$ cat eigrad_string
print("\n".join([ "".join(sorted(i.split())) for i in open('in') ]))
talis@talis-t4:~/facebook/words$ python eigrad
bwjijibwjibwjp

talis@talis-t4:~/facebook/words$ python eigrad_string
bwjijibwjibwjp
talis@talis-t4:~/facebook/words$ cat in
jibw ji jp bw jibw
talis@talis-t4:~/facebook/words$
а правильный ответ( www.facebook.com/hackercup/problems.php/?round=4 — 4 строчка в примере вывода ):
bwjibwjibwjijp

или только у меня стандартный сорт неправильно работает?

P.S.: а все равно я собой доволен) и питоном) это была первая прога на нем написанная :)

mihaild Jan 16 2011 at 01:39

Чем это стандартный сорт неправильно работает? В лексикографическом порядке префикс слова меньше чем само слово.
Ваше решение, как и приведенное выше мое, работает неправильно. Просто в вашем зачем-то (я так и не понял, зачем) используется самописная сортировка.

funca Jan 16 2011 at 01:33

наверно, тупое решение:

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

выдает bwjibwjibwjijp

mihaild Jan 16 2011 at 01:35

Тупое. Ограничение вроде 100 слов. 100! долго перебираться будет)

Talismanium Jan 16 2011 at 01:38

ограничение 9 слов, только 9!

ctapnep Jan 17 2011 at 10:55

да, но таких наборов 100 штук. Значит на каждый набор из 9-и слов должно уходить не более 3.5 секунд.
А 9! вариантов сложить, отсортировать и выбрать нужный — это таки занимает время.

Я для интереса погонял это решение с разными входными данными. Таки с 9-ю словами проблем нет. С 10-ю на грани. А с 11-ю уже не судьба. Понятно, что от машинки зависит, но в целом так. Решение на грани фола. Но таки решение. И очень хорошее. Ибо простое и в тоже время укладывается в условия.

mihaild Jan 17 2011 at 14:35

9! это меньше 400 тыс. По идее, даже 11! (примерно 40 млн.) на чем-то компилируемом (С/С++) должно проходить.

Talismanium Jan 16 2011 at 01:39

Input
As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.

Output
Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.

Constraints
1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10

mihaild Jan 16 2011 at 01:41

Хм… facebook такой facebook.
В общем, по хорошему эту задачу точно можно решить за (вроде) квадратичное время.

Talismanium Jan 16 2011 at 01:46

скорее даже быстрее

лексикографическая сортировка работает, пока не начинаются слова идущие с одной буквы — их нужно перебирать пермутейшнами, уходя вглубь рекурсией
а все если слова с разных начальных букв — сортировка работает полностью

странно, фейсбук мне прислал, что я правильно решил все три задачи...)

mihaild Jan 16 2011 at 01:48

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

Skiminok Jan 16 2011 at 11:26

Её можно решить даже за время O(N log N).
Просто отсортировать строки, но не со стандартным компаратором, а с компаратором вида a + b < b + a

Skiminok Jan 16 2011 at 12:09

Вот простое решение за O(N log N) на Python 2.7, основанное на этой идее:

from functools import cmp_to_key

def comp(a, b):
    return -1 if a + b < b + a else 1 if a + b > b + a else 0

def solve(s):
    return "".join(sorted(s.split(), key = cmp_to_key(comp)))

Демонстрация:

>>> inp = "jibw ji jp bw jibw"

>>> solve(inp)

'bwjibwjibwjijp'

Talismanium Jan 16 2011 at 12:17

Большое спасибо!

funca Jan 16 2011 at 14:41

офф: складывается ощущение, что Гвидо что-то перемудрил с сортировками. запись в старом варианте (с опальной cmp) понятнее и короче:

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

Talismanium Jan 16 2011 at 14:44

Спасибо!
питон мне нравится все больше и больше!

egoholic Jan 17 2011 at 03:33

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

words = ['facebook', 'hacker', 'cup', 'for', 'studious', 'students']
words.sort.inject{|inj, word| inj + word}
#=> cupfacebookforhackerstudentsstudious

а если не только, то даже не знаю… мой выбор — ruby, хотя питон тоже интересен.

П.С. Пайтониты, не пинайте за маленький офтоп! мы же братья, давайте лучше вместе бомбанем по ~~Тбилиси~~ PHP'истам =)) Это шутка, не хотел задеть ни чьих нежных чувств =)

Talismanium Jan 16 2011 at 01:48

Большое спасибо!

crash Jan 16 2011 at 01:24

третья задача какая-то слишком простая или я чего-то не понял? отсортировать слова, слить?

mihaild Jan 16 2011 at 01:26

Не поняли.
Простейший пример:
a, ba, b — отсортированными будут a, b, ba, склеенные будут abba.
А надо abab

crash Jan 16 2011 at 01:33

но ведь вы сами написали решение через sorted,

>>> l = ['a', 'ba', 'b']
>>> sorted(l)
['a', 'b', 'ba']
>>>

mihaild Jan 16 2011 at 01:36

Выше я написал неправильное решение, эквивалентное неправильному предложенному в статье.

crash Jan 16 2011 at 01:39

понял

egoholic Jan 17 2011 at 10:17

а разве в алфавитном порядке слова с меньшим числом букв идут не выше? это я про ba и b, b ведь и должно быть раньше ba, по крайней мере так в энциклопедическом словаре, который у меня есть.

mihaild Jan 17 2011 at 14:36

Да, отсортированными они будут a, b, ba, после склейки — abba.
Но можно склеить как abab и получить лучший результат.

w0nder Jan 16 2011 at 06:16

Задачи — полбеды. Но так криво и тупо организованное соревнование по программированию раньше можно было встретить только в Воронеже. Фейсбуку должно быть прям ооочень стыдно

Talismanium Jan 16 2011 at 09:15

Гугл подсунул инсайдеров

Talismanium Jan 16 2011 at 10:10

Еще не понятен лимит времени… за 6 минут нужно просчитать 20 вариантов входящих данных. для кого это ограничение? у меня к кластеру доступ есть, а задание через 5 сек на исполнение уходит

или суть 6 минут не в этом?

w0nder Jan 16 2011 at 10:26

Суть 6 минут в том, что асимптотику плохого решения иногда и кластер не исправит. Вообще они взяли же «стандартные» (уже опробованные не раз гуглом) правила, только почему-то забыли всем об этом сообщить )

Talismanium Jan 16 2011 at 10:31

да вот поля у них какие-то маленькие…
100 на 100 максимум. для распределенной рекурсии это ничто
а кластеры из топ200 списка, им кол-ва процессоров не занимать

наверно единственное объяснение — в финальных тестовых данных есть некоторые крайние случаи, которых в примерах нету. т.е. чтобы увидев падение алгоритма не успел исправить.

w0nder Jan 16 2011 at 10:33

Ну далеко не у каждого есть кластер из топ200, согласитесь )

А в тестах должны быть крайние случаи, да. Впрочем не уверен что эти дятлы-организаторы хакеркапа об этом знают ))

Talismanium Jan 16 2011 at 10:42

эт да :)

про кластер:
а облако? за 5 минут сжечь несколько баксов за огромные мощности и результат не так и дорого

w0nder Jan 16 2011 at 10:47

Ну дойдешь ты так до финала (что ОООчень маловероятно) — там что делать будешь, очно?

Talismanium Jan 16 2011 at 10:51

100 баксов (дают всем финальщикам) отобьют все расходы на облако :D

w0nder Jan 16 2011 at 11:07

Ну удачи, будет интересно потом услышать рассказ об этом )

EgorK Jan 17 2011 at 01:00

Не знаю как тут, а на финале GCJ был заблокирован инет

Talismanium Jan 17 2011 at 01:03

встать и пойти кофе пить кофе за счет фирмы, деморализуя оставшихся участников :)

EgorK Jan 17 2011 at 01:05

Не совсем понял это ремарки ;)

Talismanium Jan 17 2011 at 01:06

ну если попал в топ25 можно себе позволить расслабиться и посмеяться над организаторами. отрезали инет, не предупредив — устрой забастовку, в правилах не запрещено, а в газетах писать будут :D

EgorK Jan 17 2011 at 01:07

Не напишут, потому что nobody cares

aml Jan 16 2011 at 20:58

Там обычный алгоритм поиска Дейкстры работает — никакая рекурсия не нужна. Если неправильный алгоритм выбрать с экспоненциальной сложностью, то никакой кластер не справится. Вон в первой задаче на сумму квадратов многие не догадались корень извлечь, а тупо перебором решали с квадратичной сложностью. Без шансов, какое бы железо ни взять.

EgorK Jan 17 2011 at 00:59

Хм, вообще-то там проходило совсем тупое решение с двумя циклами:
for (long i = 0; 2 * i * i <= x; i++) for (long j = i; i * i + j * j <= x; j++) if (i * i + j * j == x) ans++;
По крайней мере на Java, на Python может и не проходило

mihaild Jan 17 2011 at 01:07

Это к задаче про квадраты. Ассимптотика получается линейная, может и прошло бы, но не факт.
А про алгоритм Дейкстры — я так понял, к 1й задаче из 1А.

EgorK Jan 17 2011 at 01:09

Ну, я исходил из этой строчки первоначального коммента:
Вон в первой задаче на сумму квадратов многие не догадались корень извлечь, а тупо перебором решали с квадратичной сложностью. Без шансов, какое бы железо ни взять.
А то, что проходила — это точно, за 18 секунд с 1 тестом она легко справляется

mikhanoid Jan 17 2011 at 21:31

Ну. Если вы умеете писать такую распределённую рекурсию за 6 минут, то вас всяко сразу возьмут в Facebook работать.

EgorK Jan 17 2011 at 01:01

Суть 6 минут в том, что если алгоритм реально плох (2^n когда предполагался n^2, скажем) никакой кластер не поможет

Skiminok Jan 16 2011 at 11:39

В моей душе после этой недели потерялись последние капли уважения к Facebook, Inc.

Судите сами:

Задачи — скучные и простые. В формулировках задач баги, их меняют на ходу, во время контеста, причём втихомолку, ничего участникам не сообщив. Была задача, которая предполагала решение динамическим программированием, но тем не менее прекрасно работал жадный алгоритм. Были задачи, условие которых пришлось перечитать 2-3 раза, чтобы понять (иллюстраций в условиях — никаких).
Тесты — никакие, они иногда почти ничего не проверяют. В задачах утверждают, что количество тесткейсов во входных файлах будет до 100, в реальности оно везде 20. Да даже и 100 для некоторых задач — цифра скучная. В авторских тестах из примера одной из задач — ошибка. Их так и не исправили во время контеста, поэтому мы писали правильное решение на свой страх и риск — хрен его знает, как у них реальное авторское решение и чекер сделаны...
Система — это вообще тихий ужас. Видимо, написана левой ногой за вечер каким-нибудь фейсбуковским интерном, что ли. В интерфейсе кнопки не работают, чтобы отослать решение, нужно раз 300 нажать на «Submit» — авось с какой-то попытки он таки отреагирует и зачтет ответ (а таймер-то тикает!) Вместо входного файла скачивается html, а в некоторых браузерах вообще ничего не скачивается. Некоторые браузеры теряют посылки, даже если кнопка «Submit» умудрилась сработать =) В scoreboard квалификационного раунда показывались лишь первые 10 человек, хотя участвовало явно побольше.
В итоге всего этого безобразия организаторы не выдержали и прекратили контест на 20 минут раньше положенного. Это вообще ни в какие ворота не лезет. Какая бы кривая у вас там ситуация не была — дайте, в конце концов, людям писать! Потом раунд и отменить можно, если что.

В общем, я уже ничего хорошего от этого Hacker Cup не жду. Следующие раунды писать буду из принципа, уже любопытно просто, чего они там на этот раз отчебучат :)

novoselov Jan 16 2011 at 14:17

1 задача — формат входного файла данного для примера отличался от формата файла который требовалось скачать. Пришлось править парсер на лету. «А таймер то тикает»
2 задача — перепутали местами параметры G и W
3 задача — по условию задачи перепутан порядок значений вероятностей на поворотах.
В итоге в соответствии с указанными правилами нельзя было решить ни одну задачу!
EPIC FAIL

aml Jan 16 2011 at 20:51

Во 2 задаче перепутали параметры, да и тестовый пример там похоже неправильный был.
В 1 задаче вроде всё вообще без ошибок было. А в 3 действительно цифры были перепутаны. Но правильно написанной программе, вообще говоря, должно быть без разницы. Тестовый пример был правильный, да и итоговое решение мне засчитали.

EgorK Jan 17 2011 at 01:11

В 1й задаче все было по правилам. Newline тоже whitespace. То, что Вы не прочитали условие, а просто посмотрели на инпут — не их проблема

Talismanium Jan 17 2011 at 01:21

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

Skiminok Jan 17 2011 at 10:42

Не, это исключено. Задачи там все же придумывают бывшие ACMщики. Так что в 6 минут вы не влезете в том и только том случае, если не придумаете алгоритм оптимальной сложности.

И не надо никаких новомодных ухищрений, типа кластеров и параллелизма. Не помогут.

P.S. Конечно, качество FHC оставляет желать лучшего пока что, но я верю, что на последних раундах все-таки так все и будет. По крайней мере для Google Code Jam это 100% верно.

mihaild Jan 17 2011 at 14:37

На GCJ вроде бы все раунды нормальные. Хотя, конечно, у них более отработанная схема.

novoselov Jan 17 2011 at 08:12

Давайте просто сравним example и download.
example
N\n
R C {row1} {row2}\n
R C {row1} {row2}\n
…

download
N\n
R C\n
{row1}\n
{row2}\n
\n

novoselov Jan 17 2011 at 08:19

* парсер съел окончание
download
N\n
R C\n
{row1}\n
{row2}\n
\n
R C\n
{row1}\n
{row2}\n
\n

Вы не видите разницы? После блока строк еще одна пустая строка. Организаторам сложно было предоставить пример в том же формате?
В контексте нескольких test case'ов whitespace и newline все же разные понятия, в контексте конкретного языка они могут и совпадать, но решения принимались на любом языке, хоть в excel, хоть в matlab, хоть на счетах. Как минимум стоило указать что понимается под whitespace.

EgorK Jan 17 2011 at 10:54

А почему они были обязаны представить в то же формате? Они были обязаны представить в формате, описанном в условии задачи. Оба этих формата подходят под описание «All tokens are whitespace-separated».

EgorK Jan 17 2011 at 01:02

В третьей задаче есть еще 1 решение — за O(n 2^n), динамика по подмножествам

aml Jan 17 2011 at 08:02

Третья задача решается с O(n * log(n)) без всякой динамики. Там вообще перебор не нужен:
1. Все углы трассы сортируются по предпочтительности обгона именно в этой точке. Предпочтительность — отношение вероятности успешно обогнать к вероятности успешно проехать без обгона. Сортировка — O(n*log(n)).
2. Первые R-1 углов по этому отсортированному списку мы будем обгонять, остальные — просто ехать. Перебираем весь список углов и считаем произведение вероятностей успешно проехать на каждом углу. Сложность — O(n)
3. Выводим полученную вероятность.

novoselov Jan 17 2011 at 08:28

Как-то так:

int skip = T — R+1;
turns.Sort((turn, next) => ((turn.normal — 1) * (next.over — 1) * (turn.over * next.normal )).CompareTo((turn.over — 1) * (next.normal — 1) * (turn.normal * next.over)));
var p = turns.Take(skip).Select(turn => turn.over).Concat(turns.Skip(skip).Select(turn => turn.normal));

числитель произведение p[i] — 1, знаменатель произведение p[i], все поделенное на gcd

EgorK Jan 17 2011 at 10:55

Речь ведь идет про квалификационный раунд. И в нем тоже есть решение за сортировку, но его еще надо доказать. Это же решение естественно

aml Jan 17 2011 at 11:02

Прошу прощения, я про 1A писал.

Triaffer Jan 17 2011 at 04:02

А я из хрома под убунту не смог за скачать input для 2-й задачи — мне упорно отдавали скрипты :/, пришлось логиниться в файрфоксе, и качать 2,5 минуты(!) файл 400 кб, на отработку и отправку оставалось менее 50 сек, естественно, не успел.

С 3 задачей я немного поизвращался — т.к. в условии сказано, что есть только английские буквы в нижнем регистре, то строку из 10 символов можно представить как число в 27-ричной системе счисления ('\0'=0, 'a' = 1 и т.д.), перевести ее в число (unsigneg long long int с головой хватило), потом отсортировать массив стандартным sort(там quick sort вроде) и вывести.
При максимальном количестве входных данных, сгенерированых рандомно, сей метод работает за 0,027 сек(интересно у кого сколько).

Интересно, а про 6 минут на отправку решения написали сразу? а то я сразу посмотрел задачи, скачал input, и пошел спать ) а утром мне сказали time expired :))
Перерегистрировался, отправил решения.
Пришло 2 ответа — «вы прошли, поздравляем» и «удачи в следующем году». Походу за перергистрацию дисквалифицировали?

aml Jan 17 2011 at 08:06

Скрипты сохранил? Можно глянуть?

goodman Jan 17 2011 at 14:34

А для второго задания не подойдет Алгоритм А* или другие алгоритмы ИИ поиска?

mihaild Jan 17 2011 at 14:40

А где во втором задании (про колышки) граф?

f0rbidik Jan 17 2011 at 18:21

Для первой задачи:
c = x² + y²
c / 2 = ( x² + y² ) / 2
Среднее ( x² + y² ) / 2 можно определить высотой середины отрезка соединяющего две точки ( x, x² ) и ( y, y² ). Соответственно середины всех отрезков соединяющих точки ординаты которых удовлетворяют указанному выше равенству будут лежать на прямой c / 2. Поскольку абсцисса середины данного отрезка есть среднее абсцисс точек, которые соединяет отрезок, искомые пары чисел следует искать следующим образом:

Выбираем некоторое рациональное число в интервале [ sqrt( c ) / 2, sqrt( c / 2 ) ], симметричное относительно соседних целых;
Выбираем, симметричные относительно выбранного ранее числа, целые числа, проверяем удовлетворяют ли целевому равенству и повторяем итерацию;

Отрезок [ sqrt( c ) / 2, sqrt( c / 2 ) ] образуется абсциссами точек пересечения прямой c / 2 с прямой f( x ) = c x / sqrt( c ) и параболой g( x ) = x².

Итого, требуется порядка k * N сравнений, где k удвоенное число целых в интервале [ sqrt( c ) / 2, sqrt( c / 2 ) ], а N число целых в интервале [ 0, sqrt( c ) ].

Talismanium Jan 17 2011 at 18:27

можно в виде проги?

novoselov Jan 17 2011 at 20:11

А может проще? Делаем факторизацию числа (для целых чисел в заданном интервале это не более 5000 итераций), далее через google можно в одну формулу посчитать количество сумм квадратов.

f0rbidik Jan 17 2011 at 21:20

479001601?

novoselov Jan 22 2011 at 20:13

479001601 = 13^2×2834329
Квадраты
{665, 21876}, {7800, 20449}, {15065, 15876}

f0rbidik Jan 25 2011 at 15:17

Прошу прощения, имелось ввиду простое число 479001701.