Уже через три часа стартует первый раунд FHC. Напомним, что в следующий этап проходят все те участники, которые решат столько же задач, сколько 500-е место, при условии что 500-й участник решил хотя бы одну задачу. Раунд продлится 24 часа
ссылка на раунд — https://www.facebook.com/hackercup/problems.php?round=225705397509134 Не забываем что в прошлый раз были проблемы с https
Немного не так: в следующий раунд проходят те участники, которые решили столько же задач, сколько и 500е место, при условии, что 500ый участник решил хотя бы одну задачу.
fixed, спасибо
Ссылку на олимпиаду киньте
Вот тут есть много всего.
Ты не сможешь участвовать в ней, если не прошел квалификационный раунд.
Спасибо
Кинул.
У меня одного
Запрашиваемая Вами страница не найдена. Вы нажали на устаревшую ссылку или неправильно набрали адрес. Некоторые вебсайты чувствительны к регистру. Вернуться на главную Вернуться на предыдущую страницу
?
Нет, не у одного...
То же самое.
Это у их уже походу традицией становится...
там уже около 300 человек об этом отписалось :)
Уже заработало...
После этого комментария я уже смирился с тем, что не видать мне Online Round 1. Но на следующий день пришло письмо — ответ на клар:
Hi Boris,
Your problem was graded correct. Good luck in Round 1.
Thanks for contacting Facebook,
Facebook
-----Original Message to Facebook-----
_From: ... _
To: The Facebook Team
Subject: Hacker Cup Feedback
Type of Feedback: error
Problem: Billboards
What's Up?: Some days ago I send solution of this problem, put had no result. I send it on https. I read on forum that it means that I had presentation error, but it wasn't showed to me, so I've no chance to correct solutions. Also I read that some submitions with same problem were corrected by jury and rejdged. So, can you make the same with my solution? Contact Email: ...
-----End Original Message to Facebook-----
Тем не менее в раунд меня не пускает. Да что ж это такое =( На главной странице не могу даже найти контактов жюри.
Round One: Fight!
So fail....
So much win.
So fail.
Раунд еще не закончился.
Конечно, однако я думаю мой комментарий не приносит ничего такого чего не видно в условии...
Догадайся убрать под спойлер хотя бы. В идеале конечно надо удалить комментарий.
Ты заслуженно не проходишь в следующий раунд
Петросян, я не знаю кто ты есть на самом деле, но ты — мерзкий человек. К людям надо иметь хоть каплю уважения. Андрей заслужил пройти в следующий раунд.
Если так дальше и пойдёт, то 500ое место будет иметь все 3 задачи
это да. Прошло всего 4 часа раунда, а 250 человек уже послали все 3 задачи (а остальные 250 — по 2 задачи). Так что схалявить как в квале не получиться, придётся решать все 3.
Итого 1492 человека решило 3 задачи (без учета тестирования).
Да, забавно получилось. У меня друг упорно до конца искал баги, и все 3 решения отсылал в последние 10 минут
Поясните пожалуйста мне убогому, почему в первой задаче ответ для S = 5, 6 а не 5? Мы ведь можем поместить checkpoint и goal в точку (1, 4) и тогда S = 5 и T = 5, разве нет?
а все, дошло. там же написано английским по белому, что checkpint не совпадает со стартом и финишем.
Во время раунда как бэ без пояснений. И скройте пожалуйста все под спойлер.
Ух.. вроде решил все задачи. Несмотря на постоянные их лаги, задачи у них очень интересные, по крайней мере раунд1 мне очень понравился.
Уверен что все 3 задачи сдаст далеко не 500 человек. Задачи простые, многие пренебрегают внимательной вычиткой условия, тестированием на крайних случаях. Оффтоп: в этой теме неоправданно много минусов.
Посубмитят 3 видимо всё-таки больше 500 человек
Посубмитили уже больше 500 человек. Очевидно, задачи более-менее простые(конечно, узнаем на финальных тестах насколько они простые). Вот лично я считаю, что это плохо. Чисто гипотетически, если Петр ошибется в какой-нибудь задаче, он весьма вероятно пролетит мимо следующего раунда! Это не есть хорошо.
Мне почему-то кажется, что 2 задачи все же пройдут в сл. раунд. В той же квале я после сис. теста поднялся с 3000 до 1800 места (+1200 мест), хотя в тех задачах (A и С) я ума не приложу где можно было набажить.
А мне всё же не верится что у 400+ человек упадёт что-то из трёх задач.
Одного мы уже знаем, осталось 400+ -1 :-Р
Или Попелышев
Jokser, в квалификации было много дурачков которые сдавали абы что, видел исходники где на английском написано "Я не знаю как решается эта задача", а в этом раунде таких должно быть меньше. Тем более что в квалификации у многих падала третяя из-за удвоенной буквы С
Никто не застрахован :)
Ты как всегда прав. Сколько сильных участников не прошло дальше...
см. выше, я считал что меньше 500 сдадут третью, так что не всегда прав. ;)
Все. Не знаю как вы, а я молиться богам программирования что нигде нет багов. Чекерами вроде как проверил, но все-таки...
Андрей шансы растут, теперь 400+ -2 :D
Я бы сказал не 400, а уже 600=) Ну и -3 тогда=)
-4 (((
Типун тебе на язык.
Самое смешное, что на самом сайте, в комментариях к туру уже давным давно выложены по несколько раз идеи решения всех задач =(
Модерация, такая модерация на мордакниге=(
Загнули они с ограничением на 500 мест с тремя простыми задачами... При этом любой может решить задачи, почитав комментарии, а те, кто честно решал, но в связи с техническими какими проблемами с сетью там, или отослав не то, или глупую ошибку допустив, пролетят, решив даже 2 задачи, так как разжеванные решения всем известны и с 3-мя уже больше 1000=(
Пролистал FAQ и правила. Среди условий дисквалификации: "Communicating or publishing information concerning the content of the problems, or solutions to the problems, with other competitors, either directly or indirectly, before the end of the Round." Не понимаю, на что расчитывали те, кто там прям в комментариях на тесты отвечал или условия постил.
На десяток дисквалов пару сотен людей "решивших", даже если вдруг эти дисквалы таки будут
не понятна логика людей, которые пишут решения. ладно те, кто читают — читеры, они везде читеры. Но какой смысл помогать конкурентам — вот что непонятно.
Чё-то не круто получается: люди с закрытым проблемсетом могут не пройти в следующий раунд
В смысле? Если правильно решено 3 задачи, то в любом случае проходишь в следующий, ибо это не хуже, чем у 500 места в любом случае.
Ааа я не обратил внимание. Ну тогда всё норм
Ничерта не работает на Facebook: только что благополучно получил Time Expired по одной из задач, т.к. сабмиты у меня принимать никто не хочет — нажимаю на кнопку Submit, и ничего не происходит. Остальные две решать, естественно, не буду. (отправлял из Firefox 8.0)
Надо заметить, у меня по всем трем такой вердикт, хотя с первого раза все отправилось, причем я вижу свои сорцы, вывод и md5. Сам на всякий случай написал feedback, и вам советую.
Я не вижу ни сорцы, ни вывод, ни md5, ни себя в мониторе, ни причин решать остальные две задачи.
Зайди без https. Так бывает.
Во-первых, одна задача зафейлена, и мое отношение к facebook отныне максимально негативно, а во-вторых, я и так заходил без https.
Никогда не сдавайся!
Добро пожаловать в клуб "Зафейливших-из-за-багов-hacker-cup" =)
Это в очередной раз говорит о том, что прежде чем проводить реальные соревнования, надо проводить тестовые контесты на своей системе. Все особенности всех браузеров и конфигураций учесть непросто, и даже если в системе не используется, простите за выражение, флеш, всё равно априори нельзя быть уверенным на 100% в работоспособности.
Вообще, конечно, соревнования для саперов надо проводить по таким правилам, а не для программистов %)
Посмотрим. Может, все-таки окажется так что 700+ решений упадут из-за какой-нибудь фигни и народ пройдет. Всякие чудеса случаются.
Как решать Checkpoint?
Кол-во способов дойти в (i,j) — C(i+j,j) причем стоит оно i+j. Раскладываем в произведение двух цешек (предподсчитаны) с минимальной суммой
Каким образом преподсчитываются все C(i+j,j)? Я сохранял в массив все 10 миллионов вариантов. Уверен, что есть способ лучше.
Я считал все C(i, j) при i до 105, j ≤ i. Но останавливался, если C(i, j) ≥ 107
Можно было рассмотреть :
C(i+j,j) i+j <= 5000.
C(i+j,2) и C(i+j, 1) 5000 < i+j < 10000000.
Это все сочетания которые могут быть меньше десяти миллионов.
Возможно, глупый вопрос или баян, но хотелось бы узнать как можно эффективно посчитать C(n,k)? Вроде наивным способом будет цикл, есть ли способы лучше?
вот так можно
Спасибо за ответ! Получается динамика в случае с небольшими сочетаниями. Если же цифры большие , например, 10000000? Случайно нет никакого свойства, позполяющего считать быстро?
Кстати, а ваш вариант, похоже, вообще неправильный ибо числитель переполненяется.
В каком случае переполняется? Я не был уверен на 100%, но таки оставил так.
Проверил, переполнения не происходит :)
А, пардон, я не заметил что это java. Просто на С/C++ long обычно 32 бита и там точно такой же код легко переполнится.
В любом случае, нет никакой нужды делать это в две переменные, можно сразу делать result = (result*(n1-m1))/(m1+1) ибо оно всегда целочисленно.
В этой задаче можно построить треугольник паскаля с отсечением. Я так делал.
Я решил так. Написал динамику по типу кол-во способов дойти до клетки, если можно ходить только вверх-вправо. Высчитывал ее через 2 строки до тех пор пока кол-во способов в первом элемент новой строки не перевалит за S. Там сложность получается меньше чем O (S * logS). Ну и соответственно обновлял кратчайшие расстояния при данном S. А далее у нас кол-во путей разбивается S = Sa * Sb. Где Sa — до checkpoint, Sb — до goal. Нужно перебрать делители S и найти наилучший ответ.
Можете, пожалуйста, показать код. Не совсем ясно, каков массив состояний. Вроде, динамика на матрице имеет сложность O (N*N)
Вот код
Я решал так:
Динамикой нашел точки в которые можно добраться A путями, и сохранил в массиве самый короткий путь. Теперь мы имеем массив arr[S] == T
S общее = S CheckPoint * S Goal
T (0,0 -> Goal) = T (0,0 -> CheckPoint) + T (CheckPoint -> Goal)
Просто перебираем все пары множителей через массив
Предпосчитаем для каждого i из [1, 10000000] минимальный периметр dp[i] такого прямоугольника, чтобы количество способов добраться из левой нижней вершины в правую верхнюю было ровно i. Сделать это можно было просто треугольником Паскаля с отсечением. Потом для каждого s будем переберем все его делители del до корня, включая единицу, и найдем минимальную величину dp[s]+dp[s/del].
Там получается, что до какой-то точки можно дойти с помощью C[n,k] способами. И фактически теперь для каждого S нам нужно найти минимальное n, что найдётся k, такой, что C[n,k]=S (тогда n — это путь минимальной длины). Ну и поскольку нам нужно пройти через контрольную точку, то рассмотрим все делители S и ответом будет n1+n2, где n1 и n2 минимумы соответственно в C[n1,k1]=S1 и C[n2,k2]=S2, где S=S1*S2. Я так решал...
В последней "Squished Status" вроде было проще всего набажить — не рассмотреть какой-то случай с нулями, или с типами промахнуться (получить переполнение)
А какие там случаи? Конечно, возможно, что у меня неправильное решение, но оно жутко простое, да и случаев там особо нет никаких...
В моем решении могли возникать проблемы, если max значение однозначно(меньше 10)
Я считал через динамику, и случаи когда нулей 3+ подряд, когда 100, и нельзя брать только 1, или только 10. Вобщем у меня осталось ощущение что я чего-то недосмотрел
Там ещё один случай — 200.
Да. Я имел ввиду 100 как пример, подразумевалось x0 и x00, хотя у последнего действительно только 2 вариант при данном ограничении на М
Да... у меня тоже жутко простая динамика. Там может быть люди ловились на том, что в динамике новое число нужно проверить, чтобы оно не было с лидирующими нулями.
Лидирующие нули необходимо было обрезать (включая 0) + опускать те сочетания цифр, которые превосходят данных max.
Не надо ничего обрезать. Если в динамике очередное число начинается с нуля, то не считаем такие случаи в динамике. http://codeforces.me/blog/entry/3787#comment-76968 вот хорошо расписано. Я делал по такой же формуле.
Как раз в этом разборе и написано "Таким образом, нужно учитывать, что число не начинается с нуля и попадает в интервал [1..M] и использовать заранее посчитанные значения."
что вы имеете ввиду насчет "промахнуться с типами"? Использование целочисленных типов?
ну я вот модуль 4+ миллиарда прочитал как 4+ миллиона. =(((
использовать int вместо long long
А, точно, не заметил, что надо было, Использовал не задумываясь:)
Задача — баян, древний из книги Ф. Меньшикова.
Проверка опять производится вручную? =\
Решение последней расскажите пожалуйста. Мое решение по времени зашло, но может это какая-то известная задача и решается без костылей.
ways[i] = количество способов прочитать сообщение, состоящие из i первых символов строки. ways[0] = 1, ways[i + j] += ways[i], для таких j = 1......, что подстрока str[i + 1...i + j] является валидным числом.
+угловые случаи, например для 255 100 ответ — 1, а не 2 или 3
так а что здесь углового? валидное число — это число от 1 до M, это явно сказано в условии.
Например для строки 1100, i = 0, j = 1 ways[0+1] += ways[0] если str[0+1 ... 0+1] является валидным числом Но str[1] нельзя считать валидным числом, потому что нельзя разбить на строки 1-1-[00 — как ни возми, они не валидны]
Т.е. важно не только чтобы строка str[i+1 ... i+j] была валидной, но и то что после нее остается
ну так и что? давайте промоделируем i = 0 ways[1] += ways[0] (число 1) ways[2] += ways[0] (число 11) ways[3] += ways[0] (число 110) ways[4] — не добавляем,1100 — не подходит пока все ок, ways[1] = ways[2] = ways[3] = 1
i = 1. ways[1 + 1] += ways[1] ( число 1) ways[1 + 2] += ways[1] (число 10) ways[1 + 3] += ways[1] ( число 100) получили, что пока ways[4] = 1. i = 2. ways[2 + 1] — не добавляем, ибо 0 — не валидное число. аналогично для любых добавлений дальше.
в конце получим,ways[4] = 1, как и нужно.
"валидное число" как раз учитывает угловые случаи.
Решение — ДП.
dp[i] = количество способов разбить строку до i-го символа включительно.
Представим строку как массив чисел (0 <= s[i] < 10), пусть они нумеруются с единицы.
dp[0] = 1
dp[i] = (1 <= s[i] && s[i] <= M? dp[i — 1]: 0) + (10 * s[i — 1] + s[i] <= M && s[i — 1] > 0? dp[i — 2]: 0) + (100 * s[i — 2] + 10 * s[i — 1] + s[i] <= M && s[i — 2] > 0? dp[i — 3]: 0)
Таким образом, нужно учитывать, что число не начинается с нуля и попадает в интервал [1..M] и использовать заранее посчитанные значения.
Ответ dp[length(s)]
кстати я сейчас занимаю 777 место.
Круто
Да я знаю, что круто.
Е-мое ну сколько можно, а? У них что, реально руками проверяют все тесты? Про чекеры, валидаторы не слышали, не?
Вроде результаты уже окончательные стоят.
Японский городовой, у меня первая упала.
looser:(
Наверное, случай с делителем единицой не рассмотрел.
Нет, все тупее. Банально забыл лонги, у меня в одном месте умножение с переполнением. Тупее не придумаешь.
а где там умножать лонги? везде все кажется в инт помещается?..
тупее — в 3й брать ответ по модулю (int)4207849484 =)
Вот где. Решил память сэкономить. Этот вариант уже с лонгами. http://pastie.org/3280400
Бывают и более эпичные ошибки. :-) У меня присваиванием (умышленно?) вбито значение 127 в предпросчете, из-за которого при S=1 (ну и везде, где биномиальный коэффициент равный 1 учавствует) я выдаю 254. Как, когда и зачем я это сделал — ума не приложу, сознание категорически отказывается брать на себя ответственность за epic fail. :-)
У одного из моих друзей эпичная ошибка в третьей:
static final long MOD = 0xfaceb00c;
Числа в Java знаковые, буквы L справа от константы не стоит, значит она 32-разрядная и, ВНИМАНИЕ, отрицательная.
В эклипсе компилятор автоматически подсвечивает, что число выходит за границы инта, если в конце не стоит l и число представлено в десятичной форме 4207849484.
Да везде подсвечивает, если именно в 10-ной форме. Иван вел речь как раз про hex.
Как правильно сказал -dp-, раунд был для саперов. Увы, несколько человек наступили на мину. При том на коровью.
Передайте ваше другу, что надо быть проще :) Если бы написал по-простому, в десятичной системе счисления
static final long MOD = 4207849484;, то это бы даже не скомпилировалось бы.Оно, конечно, да, но мышка оказалась ближе к 16ричному варианту :(
Это был Egor?
PS: так за что минусуете-то?
"This round has ended. Feel free to use the problems for practice though!" Кто подскажет как их использовать если возможности скачать input нету ? :) Кстати когда были представлены даты этого года, сказали можно попробовать решить задачи прошлого года, и ссылка на неработающую систему проверки :)
P.S. было бы неплохо по окончанию писать причину Реджекта по задаче (какой тест например). Или решили и дальше гнуть линию абсолютно молчаливых организаторов ? :)
Тот, что давали вам :)
Качаешь любое правильное решение из таблицы, запускаешь на своём тесте и сравниваешь ответы. Кэп передаёт пламенный привет)
я для всех задач использовал 1 интуп файл, так что у меня только для последней, а упала первая
Его можно скачать, вроде как.
output, md5 и исходник :)
Могу скинуть свой инпут и оутпут
Давай :) Для третей, если кому-то нужно input output
Checkpoint input output
Есть 1 отличии, и что характерно на 13ом тесте :)
У меня разложение 9699690 дает S1 = 2002, S2 = 4845 и T1 = 14, T2 = 20
У тебя получается 28 в сумме. Хм
Оказалось условие остановки динамики срабатывало немного раньше чем нужно было. Отсюда неполная таблица
Спасибо за инпут
Кстати, может кто-нибудь красный на cf:тренировках выложит? Могу еще свои инпуты/аутпуты выдать для коллекции.
Кстати да, было бы прикольно. Мне друг скинул свои инпут/аутпут по первой задаче, и моё неправильное решение с этим инпутoм прошло бы ) 20 тестов, видимо, маловато для отлавливания большинства багов