Invitation to the December Cook-off on CodeChef

13 лет назад, # ^ |

+31

Statements are for noobs

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

-53

с условиями и дурак сдать может, а без условий слабо?))

→ Ответить

13 лет назад, # ^ |

-25

1 min ago shindann... Ciel and A-B... C++ 4.3.2

вот парниша последовал моему совету

→ Ответить

13 лет назад, # ^ |

Not the first time when such things happen. Also, there is another bug - status of this contest is "Ended" at the home page .

→ Ответить

13 лет назад, # ^ |

он был с самого начала

→ Ответить

NiceDay

13 лет назад, # |

Ciel and New Menu расскажите пожалуйста как решать...

→ Ответить

Sereja

13 лет назад, # ^ |

Число кратно 8 если 3 последних цифры кратны 8и, из этого выходит простенькая реализация за один проход.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

На Java нужно было как-то хитро читать? У меня постоянно был TLE.. Код здесь

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Извините, а где у вас откидываются ведущие нули?

У вас он по-моему вообще не перестает считывать. Почему просто всю строку сразу не считать было?

→ Ответить

13 лет назад, # ^ |

>Извините, а где у вас откидываются ведущие нули?
В задаче нигде не сказано, что строка может приходить неправильно сформированной. 00001 - неправильная строка

>У вас он по-моему вообще не перестает считывать.
Если посмотрите спецификацию метода, то он будет считывать до последнего символа и возвратит -1 в конце чтения.

>Почему просто всю строку сразу не считать было?
Считывать онлайн намного эффективнее, нежели чем читать всё, затем бежать по строке заново.

→ Ответить

13 лет назад, # ^ |

Ну строка то она правильная вообще-то (в условии сказано про другое)
И даже если судить по вашему то изначально может быть что-то вроде 10008
И для этой строки будет ответ 6 (это строки 0, 0, 0, 8, 1000 и 10008, а такие строки как 08, 00 и 000 учитывать не надо)

-1 то разве дождется он при стандартном input'е? Если бы был файл тогда понятно

→ Ответить

13 лет назад, # ^ |

>Ну строка то она правильная вообще-то (в условии сказано про другое)
Тогда я не понял вашего выражения "Извините, а где у вас откидываются ведущие нули?". Строка "00001" не будет являться правильным вводом для этой задачи, соответственно, я не откидываю ведующие нули.

>-1 то разве дождется он при стандартном input'е? Если бы был файл тогда понятно
На стандартный ввод подаются конечное количество символов, когда символов нет, read() возвращает -1. Не вижу в чём здесь сомнения. Я всегда тестирую, подавая на ввод файл:

type test | java -cp bin Main

→ Ответить

13 лет назад, # ^ |

Строка 00001 является правильным вводом и ответ на нее 4 (0 0 0 0)

→ Ответить

13 лет назад, # ^ |

Зачем тогда писать "Извините, а где у вас откидываются ведущие нули?" :-)

→ Ответить

13 лет назад, # ^ |

Ну я понял ваша программа 00 и 000 посчитает за правильные варианты

→ Ответить

13 лет назад, # ^ |

Да, такие ситуации не обрабатываются. Только не понятно, откуда вы взяли, что такого типа данные будут вводиться в программу?

→ Ответить

13 лет назад, # ^ |

Ну потому что по условию строка состоит из цифр (и нигде не сказано, что нулей подряд идущих не будет)
И как в одном из моих первых сообщений вариант тоже вполне реален.

→ Ответить

13 лет назад, # ^ |

Не ясно, почему если 00001 - это правильно, то 0000 - это неправильно :-) Вроде, логично либо оба считать неправильными либо оба правильными :-)

→ Ответить

13 лет назад, # ^ |

Оба варианта ввода верны
Просто при подсчете возможных вариантов и в первом и втором варианте должно получится 4
(то есть 0 0 0 0 в обоих случаях)
Сам вариант 0000 при вводе 0000 (и при 00001) не верен

→ Ответить

13 лет назад, # ^ |

ты споришь так, как будто ты ее сдал и у тебя абсолютно правильное решение.

тебе человек пытается растолковать, в чем ты не прав, а ты все равно усираешься, что прав

→ Ответить

13 лет назад, # ^ |

-8

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

→ Ответить

13 лет назад, # ^ |

ну если разговор такой приватный, то пожалуйста в ЛС, а раз уж в форуме пишете, то не возмущайтесь

от того, что я к тебе на "ты", суть моего сообщения не меняется

→ Ответить

13 лет назад, # ^ |

Ок, это понятно. В общем можно считать, что оба варианта возможны как ввод, тогда нужно считать аккуратно все числа. Теперь становится понятным, что вы имели ввиду под "Извините, а где у вас откидываются ведущие нули?" :-)

→ Ответить

13 лет назад, # ^ |

и вообще, к критике надо относится спокойней, а то развели тут холивар, и ввод некорректный, и условие некорректное...

→ Ответить

13 лет назад, # ^ |

Ну вы не указывайте, что и где нам писать. Если не врубаетесь в суть разговора, то перечитайте несколько раз.

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Ну вы не указывайте, что и где нам писать.

чья бы корова мычала, а ваша б молчала

→ Ответить

13 лет назад, # ^ |

и вообще, число кратно 2ⁱ, если i последних цифр числа кратно 2ⁱ

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Это кажется неправильно. Число кратно 2^i если k последних цифр кратно 2^i, где k - наименьшее число что 10^k делится на 2^i.

UPD: Понял это одно и тоже

→ Ответить

13 лет назад, # ^ |

Это одно и то же :)

→ Ответить

dalex

13 лет назад, # ^ |

← Rev. 2 →

Это одно и то же

^{ну вот, снова слил...}

→ Ответить

Anton_Lunyov

13 лет назад, # ^ |

Вроде бы наименьшее такое k, как раз равно i. :)

→ Ответить

13 лет назад, # |

как решать Ciel and Quiz Game?

→ Ответить

Anton_Lunyov

13 лет назад, # ^ |

← Rev. 5 →

Оказывается, максимум достигается, если взять первые несколько задач и последние несколько задач (по величине вероятности). Получается алгоритм со сложностью O(N*logN + K*K).
Но там проблемы с делением на ноль, поэтому я закодил совсем в лоб за (N*logN + K*K*K).
Обоснование: Пусть все задачи фиксированы кроме одной, тогда по ней ответ это линейная функция, поэтому максимум достигается на границе, поэтому выгодно ее брать первой или последней из не выбранных.

→ Ответить

13 лет назад, # ^ |

Блин а я писал meet-in-the-middle и вагон геометрии, так и не прошла пока

→ Ответить

13 лет назад, # ^ |

-12

вагон геометрии? ничего не перепутали?

→ Ответить

13 лет назад, # ^ |

А что тут можно перепутать? Если решать через meet in the middle, то придется для текущего элемента <X, Y>, искать в другом множестве такой элемент <A, B>, что AX + BY максимально. Иначе никак.

→ Ответить

1a1a1a

13 лет назад, # ^ |

Можете подробней эту идею сказать :) Заранее спасибо!

→ Ответить

13 лет назад, # ^ |

-8

а точно, на самом деле я тоже самое и придумал, просто не прикрутил это к геометрии

→ Ответить

13 лет назад, # ^ |

Именно так

→ Ответить

Fcdkbear

13 лет назад, # ^ |

А как вы пытались максимизировать это геометрически?

→ Ответить

13 лет назад, # ^ |

Есть n прямых и m точек (и тех и других до кажется до 60000) для каждой прямой нужно найти самую далекую от неё точку. Это стандартная задача. Строим выпуклую оболочку для точек. Сортим прямые по полярному углу. А потом идем циклом по прямым и двигаем указатель.

→ Ответить

Jughead

13 лет назад, # ^ |

Аналогично, блин)

→ Ответить

Sereja

13 лет назад, # ^ |

У меня прошли оптимизации. То-есть зафиксим какое-то решение, и попытаемся его улучшить, и так пока можем.

→ Ответить

1a1a1a

13 лет назад, # |

← Rev. 3 →

~~подскажите пожалуйста что не так я делаю в задаче Ciel and Quiz Game. Код здесь.~~

Уже понял почему не верно.

→ Ответить

13 лет назад, # |

Кто решил Ciel and Battle Arena, дайте пожалуйста пару ответов на маленькие тесты (второй семпл - для меня большой тест).

→ Ответить

13 лет назад, # ^ |

2 3 1 1 0
2 3 1 1 1
2 3 2 1 0
2 3 2 1 1
66 38 2 5 0
вот на такие тесты например очень ответ хочется

→ Ответить

Anton_Lunyov

13 лет назад, # ^ |

+13

0.208333333333
0.403225806452
0.609311740891
0.735807860262
0.023415953692

→ Ответить

13 лет назад, # ^ |

Input:

3 2 2 1 1

Output:

0.9712352

→ Ответить

PavelKunyavskiy

13 лет назад, # |

← Rev. 3 →

Кто может объяснить почему здесь(задача про Random Walk) падает assert на то что у гаусса все получилось? Казалось бы такое может быть только если нет пути в N, но assert на то что он есть не падает. Они выкладывают тесты потом?

→ Ответить

ilyakor

13 лет назад, # ^ |

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

→ Ответить

PavelKunyavskiy

13 лет назад, # ^ |

Хм. Возможно. Но у меня стресс за 30 минут не нашел тест где падает assert.

→ Ответить

Petr

13 лет назад, # |

Could you share the testcase my solution fails on Random Walk?

→ Ответить

Petr

13 лет назад, # ^ |

Never mind, I've read the editorial and the part that Gaussian elimination is not supposed to pass. It's strange that the assertions that verify that the Gaussian elimination error is not big do not fail in my solution, though.

→ Ответить

KADR

13 лет назад, # ^ |

Nevertheless, the only accepted solution for this problem uses Gaussian elimination.

→ Ответить

bjin

13 лет назад, # ^ |

I don't know how he avoids float point round-off errors, but this is not the weirdest part. With a simple idea(try to calculate answer for each node with flower, and reduce size of matrix to 2n), there is a O(n^4) approach, instead of his O(n^6) one.

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.

→ Ответить

KADR

13 лет назад, # ^ |

The solution I was trying to submit during the contest has the complexity O(N^3). It gets WA, as expected. However, I haven't tried to submit it with BigDecimals.

→ Ответить

bjin

13 лет назад, # ^ |

I think maybe your method is what I'm considering: do gauss elimination twice, first time to remove all non-flowered nodes, right?

I think with O(n^3) complexity, it's enough even to implements a Fraction class with BigInteger.

→ Ответить

KADR

13 лет назад, # ^ |

Yes, I do Gaussian elimination twice: on the initial graph and on the graph without flowered nodes.

Maybe I should have tried to implement a Fraction class.

→ Ответить

LayCurse

13 лет назад, # ^ |

+13

I've uploaded a part of (not all) judge cases. http://ideone.com/wuXju

→ Ответить

13 лет назад, # |

-8

меня одного удивляет: 36.gennady.korotkevich

→ Ответить

mmaxio

13 лет назад, # |

Глупый вопрос наверное, но почему такое не работает в Battle Arena: храним для каждой позиции вероятность выигрыша p и проигрыша q, начиная из неё, максимизирующие p / (p + q)?

→ Ответить

maksay

13 лет назад, # ^ |

← Rev. 3 →

Так так и можно, по сути. Предполагаем, что в f(0, 0, 0) лежит число p. Делаем именно такую динамику наверх по ma, va, vb, получаем f(ma, va, vb) и приравниваем к f(0, 0, 0). То же с тернарным поиском по величине ответа получило в моей криворукой реализации ТЛ :(

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

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

P.S. Вопрос отменяется, если речь идет о решении, которое использует бинарный или тернарный поиск.

→ Ответить

Egor

13 лет назад, # ^ |

У меня это получало неправильный ответ на втором семпле

→ Ответить

mmaxio

13 лет назад, # ^ |

Да у меня тоже =) Просто хочется понять в чем ошибка такой логики.

→ Ответить

Egor

13 лет назад, # ^ |

Ну, например, нельза сравнивать 0.5, 0.5 и 0.25, 0.25 - какая из этих позиций лучше зависит от ответа

→ Ответить

13 лет назад, # |

← Rev. 2 →

А где эти задачи дорешать можно?

UPD: Нашел. Забавно они задачи с контеста по разным местам раскидывают.

→ Ответить

13 лет назад, # |

← Rev. 2 →

Никак не пойму, откуда следует утверждение, обосновывающее корректность бинпоиска в 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.

Объясните, пожалуйста.

→ Ответить