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

[eigrad]

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

#!/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]

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

[mihaild]

Во-первых, не очень понятно, зачем в 3й писать сортировку вручную
Во-вторых, на тесте из условия Ваше решение работает неправильно:
jibw ji jp bw jibw
Выдает bwjijibwjibwjp
Хотя можно bwjibwjibwjijp
PS. Если не ошибаюсь, «питонично» такое решение можно записать как
answer = "".join(sorted(raw_input().split(" ")[1:]))


[eigrad]

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

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

[Talismanium]

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]

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

[funca]

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

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

выдает bwjibwjibwjijp

[mihaild]

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

[Talismanium]

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

[ctapnep]

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

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

[mihaild]

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

[Talismanium]

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]

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

[Talismanium]

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

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

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

[mihaild]

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

[Skiminok]

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

[Skiminok]

Вот простое решение за 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]

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

[funca]

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

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

[Talismanium]

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

[egoholic]

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

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

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

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

[Talismanium]

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

[crash]

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

[mihaild]

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

[crash]

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

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

[mihaild]

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

[crash]

понял

[egoholic]

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

[mihaild]

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

[w0nder]

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

[Talismanium]

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

[Talismanium]

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

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

[w0nder]

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

[Talismanium]

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

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

[w0nder]

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

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

[Talismanium]

эт да :)

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

[w0nder]

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

[Talismanium]

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

[w0nder]

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

[EgorK]

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

[Talismanium]

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

[EgorK]

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

[Talismanium]

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

[EgorK]

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

[aml]

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

[EgorK]

Хм, вообще-то там проходило совсем тупое решение с двумя циклами:
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]

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

[EgorK]

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

[mikhanoid]

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

[EgorK]

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

[Skiminok]

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

Судите сами:

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

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

[novoselov]

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

[aml]

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

[EgorK]

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

[Talismanium]

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

[Skiminok]

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

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

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

[mihaild]

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

[novoselov]

Давайте просто сравним 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]

* парсер съел окончание
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]

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

[EgorK]

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

[aml]

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

[novoselov]

Как-то так:

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]

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

[aml]

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

[Triaffer]

А я из хрома под убунту не смог за скачать 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]

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

[goodman]

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

[mihaild]

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

[f0rbidik]

Для первой задачи:
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]

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

[novoselov]

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

[f0rbidik]

479001601?

[novoselov]

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

[f0rbidik]

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