Я думаю, топику самое место в «Алгоритмах». Тем более там уже есть один по машинной графике и обработки изображений, опять-таки с исходником на шарпе. А вообще странно разделять алгоритмы по языку реализации ;)
Хотелось бы почитать простое и понятное изложение Венгерского алгоритма и симплекс-метода, с реализациями (можно схематичными, но без лишних алгоритмических упрощений, типа матриц смежности вместо списков).
Вещи вроде обходов вширь-вглубь, на мой взгляд, давать не стоит, их знает любой, кто что-то делал с графами. А если знает, то и применение найдёт.
В олимпиадном программировании им нельзя доверять… И в жизни, нередко, требуется точное решение, тем более, что оно (в данном и многих других случаях) получается быстро и наверняка.
У Вас странное представление о теории сложности, Вы путаетесь в терминологии.
Вкратце, симплекс-метод (в среднем) работает за полиномиальное время, так же и память. Есть, впрочем, другие методы линейной оптимизации, которые работают строго за полиномиальное время, но они сильно сложнее в понимании/реализации.
Было бы интересно увидеть статьи про симплекс-метод и венгерский алгоритм. И, наверно, напрасно вы используете матрицы смежности — они не сильно нагляднее, но чаще медленнее (на разреженных графах).
Да, в Новосибирске тоже бесплатные пакеты (в любом случае, даже если их пробивают, то делают это в момент покупки, а не после, и раскладывают товар по ним), в отличии от Екатеринбурга и Ижевска. И пин-код не требуют при расчёте (в Ижевске при чеке больше 500 рублей, к тому же, нужен паспорт :().
Я про это и говорю: нужно учитывать, зачем применяется тот или иной приём. Мультитесты так и организованы, как Вы говорите: нескользо вариантов входных данных в одном файле, для каждого — вывод в выходном, полученный применением одного и того же алгоритма (собственно, решения) ко всем входам. Проверяется целиком выходной файл, если хоть один ответ не совпал — тест не пройден.
От задач никто не предлагает отказываться, просто чтобы не усложнять школьникам задачу введением мультитестов, часто достаточно просто немного изменить задачу, расширив диапазон ответов, избавившись от наиболее приоритетных ответов. Например, формулировать вопрос задачи не «существует ли», а «сколько таких».
Понятно, что изменять задачи, делать тесты, сложнее, чем просто свалить их в кучу, но это как раз не-усложняет задачу решающих.
Это называется мультитест, в АСM тоже нередко бывает. Помогает усложнить задачу участников :) тем, что неизвестно точно, на каком тесте падает решение, и прошло ли оно дальше после предыдущей правки (несколько приближает к условиям финала ACM ICPC). Кроме того, позволяет устанавливать более гибкие/хитрые ограничения на время выполнения, ну и по мелочам…
Я рад, что Вы это используете, но для решения проблемы именно этого «такого хитрого плана» достаточно просто немного по-другому составлять задания/тесты. Желательно учитывать плюсы и минусы каждого подхода.
В результате сбоя электричества или при зависании намертво, так что нельзя даже сбосить кеш на диск. С другими ФС тоже может случиться, но тут дополнительная проблема в виде неправильных программ, полагающихся на старое поведение ядра. Есть патчи, возвращающие старое поведение, но с ними прирост производительности резко падает…
в исходнике есть, в описании — нет. У многих по описанию и примерам возникнут вопросы о делении на 0…
Вещи вроде обходов вширь-вглубь, на мой взгляд, давать не стоит, их знает любой, кто что-то делал с графами. А если знает, то и применение найдёт.
Вкратце, симплекс-метод (в среднем) работает за полиномиальное время, так же и память. Есть, впрочем, другие методы линейной оптимизации, которые работают строго за полиномиальное время, но они сильно сложнее в понимании/реализации.
От задач никто не предлагает отказываться, просто чтобы не усложнять школьникам задачу введением мультитестов, часто достаточно просто немного изменить задачу, расширив диапазон ответов, избавившись от наиболее приоритетных ответов. Например, формулировать вопрос задачи не «существует ли», а «сколько таких».
Понятно, что изменять задачи, делать тесты, сложнее, чем просто свалить их в кучу, но это как раз не-усложняет задачу решающих.
Я рад, что Вы это используете, но для решения проблемы именно этого «такого хитрого плана» достаточно просто немного по-другому составлять задания/тесты. Желательно учитывать плюсы и минусы каждого подхода.
И на любых олимпиадах (напр., математических) в виде тестов может сильно помочь :)
.com