@Talismanium15 янв 2011 в 19:28

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

5 мин

5.3K

Python *

Из песочницы

+34

Комментарии 75

@eigrad 15 янв 2011 в 21: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 16 янв 2011 в 06:21

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

@mihaild 15 янв 2011 в 21:34

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

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

@eigrad 15 янв 2011 в 21:47

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

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

@Talismanium 15 янв 2011 в 22: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 15 янв 2011 в 22:39

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

@funca 15 янв 2011 в 22: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 15 янв 2011 в 22:35

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

@Talismanium 15 янв 2011 в 22:38

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

@ctapnep 17 янв 2011 в 07:55

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

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

@mihaild 17 янв 2011 в 11:35

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

@Talismanium 15 янв 2011 в 22: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 15 янв 2011 в 22:41

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

@Talismanium 15 янв 2011 в 22:46

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

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

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

@mihaild 15 янв 2011 в 22:48

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

@Skiminok 16 янв 2011 в 08:26

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

@Skiminok 16 янв 2011 в 09: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 16 янв 2011 в 09:17

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

@funca 16 янв 2011 в 11:41

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

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

@Talismanium 16 янв 2011 в 11:44

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

@egoholic 17 янв 2011 в 00:33

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

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

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

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

@Talismanium 15 янв 2011 в 22:48

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

@crash 15 янв 2011 в 22:24

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

@mihaild 15 янв 2011 в 22:26

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

@crash 15 янв 2011 в 22:33

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

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

@mihaild 15 янв 2011 в 22:36

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

@crash 15 янв 2011 в 22:39

понял

@egoholic 17 янв 2011 в 07:17

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

@mihaild 17 янв 2011 в 11:36

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

@w0nder 16 янв 2011 в 03:16

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

@Talismanium 16 янв 2011 в 06:15

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

@Talismanium 16 янв 2011 в 07:10

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

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

@w0nder 16 янв 2011 в 07:26

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

@Talismanium 16 янв 2011 в 07:31

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

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

@w0nder 16 янв 2011 в 07:33

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

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

@Talismanium 16 янв 2011 в 07:42

эт да :)

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

@w0nder 16 янв 2011 в 07:47

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

@Talismanium 16 янв 2011 в 07:51

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

@w0nder 16 янв 2011 в 08:07

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

@EgorK 16 янв 2011 в 22:00

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

@Talismanium 16 янв 2011 в 22:03

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

@EgorK 16 янв 2011 в 22:05

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

@Talismanium 16 янв 2011 в 22:06

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

@EgorK 16 янв 2011 в 22:07

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

@aml 16 янв 2011 в 17:58

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

@EgorK 16 янв 2011 в 21: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 16 янв 2011 в 22:07

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

@EgorK 16 янв 2011 в 22:09

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

@mikhanoid 17 янв 2011 в 18:31

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

@EgorK 16 янв 2011 в 22:01

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

@Skiminok 16 янв 2011 в 08:39

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

Судите сами:

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

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

@novoselov 16 янв 2011 в 11:17

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

@aml 16 янв 2011 в 17:51

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

@EgorK 16 янв 2011 в 22:11

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

@Talismanium 16 янв 2011 в 22:21

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

@Skiminok 17 янв 2011 в 07:42

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

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

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

@mihaild 17 янв 2011 в 11:37

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

@novoselov 17 янв 2011 в 05: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 17 янв 2011 в 05: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 17 янв 2011 в 07:54

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

@EgorK 16 янв 2011 в 22:02

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

@aml 17 янв 2011 в 05:02

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

@novoselov 17 янв 2011 в 05: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 17 янв 2011 в 07:55

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

@aml 17 янв 2011 в 08:02

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

@Triaffer 17 янв 2011 в 01: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 17 янв 2011 в 05:06

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

@goodman 17 янв 2011 в 11:34

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

@mihaild 17 янв 2011 в 11:40

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

@f0rbidik 17 янв 2011 в 15: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 17 янв 2011 в 15:27

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

@novoselov 17 янв 2011 в 17:11

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

@f0rbidik 17 янв 2011 в 18:20

479001601?

@novoselov 22 янв 2011 в 17:13

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

@f0rbidik 25 янв 2011 в 12:17

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий