CodeChef invites you to participate in the December CookOff at http://www.codechef.com/COOK17
Time: 2130 hrs 18th December 2011 to 0000 hrs, 19th December 2011 (Indian Standard Time - +5:30 GMT)
Details: http://www.codechef.com/COOK17/
Registration: Just need to have a CodeChef user id to participate. New users please register here
Problem Setter: Hiroto Sekido (LayCurse)
Problem Tester: Jingbo Shang (shangjingbo)
It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.
с условиями и дурак сдать может, а без условий слабо?))
1 min ago shindann... Ciel and A-B... C++ 4.3.2
вот парниша последовал моему совету
На Java нужно было как-то хитро читать? У меня постоянно был TLE.. Код здесь
Извините, а где у вас откидываются ведущие нули?
У вас он по-моему вообще не перестает считывать. Почему просто всю строку сразу не считать было?
В задаче нигде не сказано, что строка может приходить неправильно сформированной. 00001 - неправильная строка
>У вас он по-моему вообще не перестает считывать.
Если посмотрите спецификацию метода, то он будет считывать до последнего символа и возвратит -1 в конце чтения.
>Почему просто всю строку сразу не считать было?
Считывать онлайн намного эффективнее, нежели чем читать всё, затем бежать по строке заново.
И даже если судить по вашему то изначально может быть что-то вроде 10008
И для этой строки будет ответ 6 (это строки 0, 0, 0, 8, 1000 и 10008, а такие строки как 08, 00 и 000 учитывать не надо)
-1 то разве дождется он при стандартном input'е? Если бы был файл тогда понятно
Тогда я не понял вашего выражения "Извините, а где у вас откидываются ведущие нули?". Строка "00001" не будет являться правильным вводом для этой задачи, соответственно, я не откидываю ведующие нули.
>-1 то разве дождется он при стандартном input'е? Если бы был файл тогда понятно
На стандартный ввод подаются конечное количество символов, когда символов нет, read() возвращает -1. Не вижу в чём здесь сомнения. Я всегда тестирую, подавая на ввод файл:
type test | java -cp bin Main
И как в одном из моих первых сообщений вариант тоже вполне реален.
Просто при подсчете возможных вариантов и в первом и втором варианте должно получится 4
(то есть 0 0 0 0 в обоих случаях)
Сам вариант 0000 при вводе 0000 (и при 00001) не верен
ты споришь так, как будто ты ее сдал и у тебя абсолютно правильное решение.
тебе человек пытается растолковать, в чем ты не прав, а ты все равно усираешься, что прав
ну если разговор такой приватный, то пожалуйста в ЛС, а раз уж в форуме пишете, то не возмущайтесь
от того, что я к тебе на "ты", суть моего сообщения не меняется
Ну вы не указывайте, что и где нам писать.
чья бы корова мычала, а ваша б молчала
Это кажется неправильно. Число кратно 2^i если k последних цифр кратно 2^i, где k - наименьшее число что 10^k делится на 2^i.
UPD: Понял это одно и тоже
Это одно и то же
ну вот, снова слил...
Оказывается, максимум достигается, если взять первые несколько задач и последние несколько задач (по величине вероятности). Получается алгоритм со сложностью O(N*logN + K*K).
Но там проблемы с делением на ноль, поэтому я закодил совсем в лоб за (N*logN + K*K*K).
Обоснование: Пусть все задачи фиксированы кроме одной, тогда по ней ответ это линейная функция, поэтому максимум достигается на границе, поэтому выгодно ее брать первой или последней из не выбранных.
подскажите пожалуйста что не так я делаю в задаче Ciel and Quiz Game. Код здесь.Уже понял почему не верно.
2 3 1 1 1
2 3 2 1 0
2 3 2 1 1
66 38 2 5 0
вот на такие тесты например очень ответ хочется
0.403225806452
0.609311740891
0.735807860262
0.023415953692
Кто может объяснить почему здесь(задача про Random Walk) падает assert на то что у гаусса все получилось? Казалось бы такое может быть только если нет пути в N, но assert на то что он есть не падает. Они выкладывают тесты потом?
Anyway, since the writer's approach is iteration with O(n^5 logn) complexity, O(n^6) is not that bad. The weirdest part is that he solves such big matrix(500x500) correctly with double, but for 60x60 matrix all other participations get WA. It seems that he didn't use some particular technique to avoids errors.
B.T.W. I think the gauss eliminations can be optimized further to an O(n^3) approach, with BigDecimal, it's solvable theorically.
I think with O(n^3) complexity, it's enough even to implements a Fraction class with BigInteger.
Глупый вопрос наверное, но почему такое не работает в Battle Arena: храним для каждой позиции вероятность выигрыша p и проигрыша q, начиная из неё, максимизирующие p / (p + q)?
Так так и можно, по сути. Предполагаем, что в f(0, 0, 0) лежит число p. Делаем именно такую динамику наверх по ma, va, vb, получаем f(ma, va, vb) и приравниваем к f(0, 0, 0). То же с тернарным поиском по величине ответа получило в моей криворукой реализации ТЛ :(
А в случае ничейного исхода что возвращается? Там же внутри динамики еще надо максимум выбирать из двух тактик, так вот если возвращать для ничейного результата что-то неправильное, то это внесет огромный разнос в ответ.
P.S. Вопрос отменяется, если речь идет о решении, которое использует бинарный или тернарный поиск.
А где эти задачи дорешать можно?
UPD: Нашел. Забавно они задачи с контеста по разным местам раскидывают.
Никак не пойму, откуда следует утверждение, обосновывающее корректность бинпоиска в Ciel and Battle Arena:
Let the correct answer be P. If we set dp[a][b][c] = X for a ≤ 0, b ≤ 0, then X ≤ dp[VA][VB][MA] ≤ P or P ≤ dp[VA][VB][MA] ≤ X is hold.
Объясните, пожалуйста.