Сегодня на задачах X Кубка Векуа, Гран-При Южного Кавказа проводится четвёртый (онлайн) матч Россия-Китай. Первые три матча проводились на Чемпионатах Урала. Все матчи, кроме первого, проводились онлайн. Победителем очного матча в 2013 году стала сборная России, в 2014 выиграл Китай, в 2015 — снова Россия.
В составе сборных — команды-финалисты 2016 года; в сборную России входят первые 5 команд-финалистов по итогам NEERC-2015.
Auto comment: topic has been translated by snarknews (original revision, translated revision, compare)
When can we see detailed final standing?
Unlocked
Как можно проаппелириовать к задаче E? В ней ответ порядка 5·104 и требуется 6 знаков абсолютной точности. Итого от участников требуется 11 знаков точности. Наше решение получало WA25, руководитель сектора по окончании сказал нам, что у нас на большом тесте порядка 45000 выдавало ошибку в шестом знаке после запятой (т.е. десять знаков были правильными). Изменения порядка слагаемых/сомножителей дало нам AC в дорешивании.
.
Мне интересно как жюри может гарантировать, что у них сохраняется 11 знаков точности? У жюри есть точная оценка погрешности решения, если они требуют 11 знаков точности? Или у них решение в BigDecimal?
Я не раз наблюдал на Educational round-ах, что обычно в таких случаях можно свалить абсолютно всё, что угодно.
У Zlobober линейное решение, так что можно и в BigDecimial'ах.
У меня тоже линейное решение, если что.
.
Вообще меня тоже напрягает, что, формально говоря, анализ погрешности в численном решении с вещественными числами с учётом поведения вещественных типов практически никто никогда не проводит.
Обычно совершенно не очевидно (во всяком случае, мне), что если рассмотреть какую-то задачу на тервер, решающуюся, скажем, квадратичной динамикой, то от перемены порядка вычислений или эквивалентной замены формул не набежит существенной погрешности. Приходится пользоваться эмпирическим знанием, в каких ситуациях такого, скорее всего, не случится, либо эмпирическим же аргументом, что есть несколько авторских решений, написанных чуть-чуть по-разному, и они отличаются на ± 10 - 12, а значит можно поставить погрешность, скажем, ± 10 - 9, но отсутствие формальности в подобного рода процессе меня всегда чуточку пугало.
.
Вообще можно не изобретать велосипед, а пользоваться, например, Boost interval arithmetic. Если действительно интересно разобраться в теме, то небольшую часть того, что рассказывают про использование даблов в ИТМО, можно почитать на наших викиконспектах (например, тут). А еще есть много интересных статей на английском на эту тему, которые легко гуглятся.
Проблема только в том, что такие библиотеки/классы позволяют узнать, что решение дает маленькую погрешность на конкретном тесте, но не позволяет доказать, что решение работает всегда правильно.
.
Я как-то в Петрозаводске слышал такой метод (кажется, Zlobober рассказывал про задачу, которую он готовил; в легенде было что-то про пиво, а в задаче нужно было считать какие-то углы). Возьмём все числа, которые были получены решением в результате промежуточных вычислений, отсортируем и посмотрим на разности соседних. Их тоже отсортируем. Если в результате получится что-то вроде
То можно с уверенностью ставить eps=1e-10, потому что слева стоят существенные разности, а справа погрешности (естественно, в этом тоже нужно убедиться, но часто это понятно из общих соображений). Не знаю, насколько это реально является доказательством, но выглядит убедительно.
.
Да, ты все точно передал. Задача сводилась к unique массива даблов, и именно таким образом я выбирал эпсилон для модельного решения и убеждался, что он ничего лишнего не склеит и ничего "равного" случайно не различит.
Но там была задача, где инпут — маленькое положительное целое, и я мог запустить проверку на всех возможных тестах. Такая роскошная возможность выпадает не всегда.
.
Как его предлагается использовать в произвольной задаче? Типа рассматриваем строку с проверкой:
За всё время работы программы на одном тесте выписываем все возможные значения
fabs(A - B), и убеждаемся, что наибольшее из тех, которые меньше eps, отличаются от eps по меньшей мере на два порядка в меньшую сторону, и что наименьшее из тех, которые больше eps, отличаются от eps по меньшей мере на два порядка в большую сторону?Ставим на это ассёрт и убеждаемся, что на тестах жюри он не падает? Вроде звучит разумно. А как это адаптировать под проверки вида:
Видимо делаем ровно то же самое, снова с
fabs(A - B)? Я правильно понял твою идею?.