Блог пользователя at1

Автор at1, 14 лет назад, По-русски

Контест

  Мне контест очень понравился, как отличная тренировка решения ботвистых задач. Мне не нравится, когда условие неполно, некорректно, неоднозначно. Здесь же все условия интуитивно понятные (мне) и, вроде, абсолютно корректные.
  Также, по задачам подготовлены очень хорошие тесты (могу оценивать только то, что дорешал A-C).
  Так что, к авторам вообще не может быть претензий, они подготовили оригинальный, качественный сет  задач. Лично мне контест очень понравился, хоть и поверг мой рейтинг в пучины отчаяния =).
  В каждой комнате все равны перед задачами и взломами, поэтому не вижу проблем с "неравенством" положений, о которых все пишут. Ну сразу же понятно, что в A всякие крайние случаи сыплются, а значит либо аккуратно на бумажке придумываешь решение, либо злостный тест, а лучше и то и другое. А дальше все покажет опыт, как и на других контестах.

Разбор

К сожалению, разбор задачи C мне, наоборот, не понравился. "Точность - это обычный математический объект, и с ним надо уметь строго работать, а не бояться!" (почти точная цитата Андрея Лопатина после лекции 2005 года). Пускай на контесте можно иногда (иногда? никогда!) махнуть рукой, но при разборе такой задачи, по-моему мнению, недопустимо.

Я, конечно, совсем не авторитет в этом вопросе, но вот как бы я написал часть про EPS-ны:
1. Есть два принципиальных подхода, считать все точно (т.е. с EPS = 0) или оценивать погрешность своих действий, следя, чтобы она не повлекла за собой WA, а второй, это вычислить EPS, который точно позволит получить ответ с требуемой точностью. Утверждается, что угадывание EPS, это то же самое, что угадывание алгоритма, может повезти, но лучше подумать 10 минут и правильное что-нибудь написать. Кстати в серьезных задачах необходимо сравнивать с разной абсолютной погрешностью.
2. При этом не обязательно в первом случае считать все в целочисленном типе. Пока мантиса не переполнилась (15-16 значащих дес. цифр в double, 20-21 long double) и не совершены операции вносящие погрешность (все кроме + * и / когда делится без остатка) с числами с плавающей точкой можно работать как с целыми. Т.е. сравнивать без всяких EPS.
3. Фраза из разбора: "if (currentTime + addTime > distance / potterSpeed - EPS)" - здесь нельзя убирать EPS, т.к. есть деление! Поставить "маленькое"? как?

Надо вычислить:

Везде в бинпоисках разумно сравнивать времена. Тогда время встречи будет отклоняться от ответа не более, чем на EPS. Отсюда следует, что EPS < 10-6.
Также мы считаем координаты точки с требуемой точностью 10-6, по формуле:
a + dir * dist = a + ((b - a) / |b - a|) * (time * vs).
(Можно оценивать это равенство по всем трем координатам одинаково, они все должны быть вычислены независимо, с одинаковой точностью).
Здесь a и b целые точки из условия, а значит вычислены абсолютно точно.
(b - a) / |b - a| - ошибка будет в последней значащей цифре, не более 2*10-16 (т.к. ответ от [0..1], нормировка вектора - "хорошая" операция: корень ошибется в одном бит. знаке и деление в одном бит. знаке, можно поскладывать относительные погрешности и умножить на 1).
Вообще: нормируйте вектора, вероятности и т.п., это хорошо!

Ошибка time не более EPS, значит, err(time * vs) <= err(time) * 10000 = EPS * 10000.
Отсюда оценка EPS * 10000 <= 10-7 => EPS <= 10-11. (10-7 вместо 10-6, чтобы учесть нормировку).
Значит времена в бин поиске можно сравнивать сточностью 10-11, вещ. типа double хватает.

Как-то так я обычно оцениваю такие штуки. Я неявно пользовался формулами для относительной и абсолютной погрешностей:
abserr(x) = x * relerr(x)
abserr(x + y) = abserr(x - y) = abserr(x)+abserr(y);
relerr(x * y) = relerr(x / y) = relerr(x)+relerr(y);

PS: я был бы рад, если бы кто-нибудь из красных комдивов написал пару страничек в своем блоге, о том, как он считает погрешность на примере нескольких ботвистых задач. Интересует возникающие спец эффекты при сложении и вычитании близких чисел, как изм. точность при исп. стандартных мат. функций и прочее. (Если это случится, пошлите мне ЛС, плз).

PPS: как отметили участники, бин поиск while (r - l) > EPS зависает на хороших тестах, проверено. Стого объянить почему так не берусь (интуитивно: у Вас же всего 16 значащих цифр, а значит рано или поздно, при убывании r - l, будет выполнено m = (l + r) * 0.5 = l).
Надо отсекать по времени или итерациям. Тем более точность вычисления m = (l + r) * 0.5 для некоторого количества итераций, также легко оценивается (чтобы препод по числякам не ругался. Наоборот, там очень любят оценивать этот параметр =) ). После 100 итераций, даже в long double продолжать смысла особого нет.
  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
> 3. Фраза из разбора: "if (currentTime + addTime > distance / potterSpeed - EPS)" - здесь нельзя убирать EPS, т.к. есть деление! Поставить "маленькое"? как?
Здесь сравнение не на равенство, а на больше/меньше... Здесь действительно эпсилону делать нечего. Какая б не была ошибка при делении - мы не знаем в какую она сторону.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Мне кажется, что я все же прав.

    Здесь написано:
    Если <время Поттера> не больше, чем <время снитча>, то Поттер снитч поймает.
    (тут только посылка, правда, заключение опущено)

    Причем мы считаем равными времена отстоящие друг от друга менее, чем на EPS.
    Поэтому не важно "в какую сторону погрешность" в такой проверке:
    greater-or-equal(x, y) <=> x > y - eps;

    Если же EPS убрать, то решение может выдать No solution, если не повезет.

    Тем не менее - это не важно, критиковалось предложение авторов "поставить EPS сильно меньше, чем...", вместо "правильно оценить погрешность того, что..."
    Хотя, возможно, это и имелось ввиду, но оценка - это же основная часть разбора в этой задаче =(
    • 14 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится
      Во-первых, "No solution" мы не можем получить... бинарный поиск запускается если на концах отрезка значения функции имеют разный знак... И он либо сойдётся к чему-то, либо TL exceed.
      Во-вторых, EPS в проверке на то, выбирать правую или левую границу в том виде, в котором он там, не катит... Это вполне очевидно - он только сдвигает ошибку в одну сторону.

      Если уж и лепить куда-то эпсилон тут, так в следующие строчки, где присваивание границ происходит. По типу:
      rightTime =  currentTime + EPS2; else leftTime = currentTime - EPS2; но только EPS2 - это уже другой эпсилон, чтоб поиск сошёлся он должен быть меньше EPS/2 (который в основном цикле), и отражать оценку погрешности вычисления функции (корень которой мы ищем). Тогда алгоритм будет сходится с погрешностью EPS, иначе он сходится с EPS+погрешность вычисления функции. Но только смысла в этом мало, т.к. на практике EPS можно взять сразу меньше требуемой по условию точности вот как раз на максимальную оценку погрешности вычисления функции.

      P.S. А авторский разбор задачи С если б я критиковал, то не потому что там недостаточно разжевали чью-то ошибку, а потому что там нету даже намёка на существование аналитического решения. Но, конечно, не буду спорить, что может быть оно для особых маньяков.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        По поводу аналитического решения: приношу самые искренние извинения. Я о нем знаю, но у меня совершенно вылетело из головы, когда писала разбор. И не такое уж оно маньячное.

        Хотя по моему опыту решения олимпиадных задач могу сказать, что в подобных задачах лучше писать бинпоиск. Пусть он и асимптотически хуже, но зато код получается более прозрачным, нет ни одной формулы, которую надо было бы выводить на бумажке. Набажить практически негде (в логике программы; здесь я не имею в виду проблемы с EPS). К тому же, бинпоиск обычно автоматически учитывает всякие крайние случаи. Например, если бы концы отрезка могли совпадать, в аналитическом решении нужно было разбирать отдельный случай, в бинпоиске - нет. (На последнее один раз попала, теперь пишу бинпоиск).
      • 14 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        Если Гарри и мяч стартуют из одной точки с одинаковой скоростью, по вашему ответ NO (на концах отрезка ведь знаки одинаковые)? Даже если вы запустите бинарный поиск, то боюсь, без EPS проверка выльется в X > X, с неточно вычисленными X в обеих частях.

        Чтоб честно убрать EPS из того условия, нужно ещё проверить не совпадают ли точки старта. В разборе даже намёка на это нет, надеюсь, авторское решение проходит тест с одинаковым стартом. 

        • 14 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Тест с одинаковым стартом - здесь действительно крайний случай. Авторское решение проходит такой тест.
        • 14 лет назад, # ^ |
          Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
          >Если Гарри и мяч стартуют из одной точки с одинаковой скоростью, по вашему ответ NO

          Тут речь идёт о проверке внутри цикла бинарного поиска. Проверка на запуск - это другое, её, конечно, надо делать с EPS, но речь не о ней. Когда мы проверяем знак функции на средине отрезка - EPS не нужен. И когда бинпоиск запущен No уже мы не получим.
          • 14 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Читайте внимательнее, речь в том, что вы бинпоиск не запустите на описанном тесте (знак в вершинах ломаной одинаковый, и без разницы проверять с EPS или без), и даже если бинпоиск запустить, то внутренняя проверка даст фейл без EPS.

            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              >и даже если бинпоиск запустить, то внутренняя проверка даст фейл без EPS.

              Про проверку на запуск бинпоиска тут речь не шла. Предполагаем, что там всё правильно и мы его запустили. И тогда  в случае одинакового старта он сойдётся к этой границе (к старту).

              Как внутренняя проверка может дать "фейл без EPS"??? Там выбирается граница (правая/левая) в зависимости от условия больше/меньше, и это всё касательно средины отрезка. No solution уже не получится никак.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
>> В каждой комнате все равны перед задачами и взломами
Не читали ещё вот этот пост?
14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Да что вы все так вцепились в этот eps. Я сам терпеть не могу задачи на эти даблы, ведь они все зависят от этих eps. Но в этом случае, eps можно использовать всего один раз и то для проверки равенства! Сто раз всем в олимпиадном программировании повторяют и повторяют: пишите бинарный поиск с фиксированным числом итераций, тогда Ваш ответ будет максимально точен. Люди с этим падали на TopCoder, падают на CodeForces и ничему не учатся.
Если использовать eps только в одном месте для сравнения, то понятно, что eps порядка 1e-6 достаточно. Меньше брать нежелательно, у Вас столько знаков после десятичной точки при больших координатах не будет. Меня вообще поражает как люди обсуждали у кого какой eps, но при этом даже не задумывались, а как же они его используют.
Пора бы уже закрыть все эти темы о погрешностях. С тестами все было в порядке, с решениями жюри - тоже. Не вижу причин на что-то жаловаться.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Полностью поддерживаю, ну, за исключением того пункта, что я сказал практически то же самое на восемь часов раньше, в два раза короче и в пять раз корректнее :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Правильно! Но тут возник другой вопрос: нужен ли eps внутри тела цикла (цикл пускай и с фиксированным количеством итераций)? Потому всю тему закрывать рано...
14 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
Сначала по поводу строчки "if (currentTime + addTime > distance / potterSpeed - EPS)".  Давайте разберем ситуацию более подробно. Дана неубывающая функция f(t) (t = currentTime, f(t) = currentTime + addTime - distance / potterSpeed). Нужно на некотором отрезке найти первую точку t, в которой f(t) >= 0. Значение f(t) вычисляется с погрешностью. Это вычислительная погрешность, связанная лишь с погрешностью вычисления операций извлечения корня, деления, и т.п. Обозначим реально вычисляемое значение за g(t) = f(t) + d(t), где d(t) как раз и есть вычислительная погрешность . d(t) - это величина порядка 10 - 16 - 10 - 17, точнее не буду высчитывать, боюсь наврать. В программе условие f(t) >= 0 заменяется на g(t) > -EPS. Это означает, что ищется такое t, для которого f(t) > -d(t) - EPS. Если предположить, что мы делаем бесконечное количество итераций бинпоиска и подставляем t с любой степенью точности, то в итоге процесс сойдется к такому t, что f(t) = -EPS - d(t). Т.е. f(t) получится примерно на EPS меньше, чем нам нужно. Теперь обратимся к формуле, по которой определяется f(t). f(t) - это время, величина того же порядка, что и t. Фактически в нее линейно входит t. В итоге t получится на величину порядка EPS меньше, чем правильное значение. Но различие во времени на EPS влечет различие на EPS * 10000 в расстоянии, которое и приводит к WA, если брать, например, EPS = 10 - 9. Если брать EPS = 10 - 11, как вывел автор, WA не будет. С другой стороны, в неравенстве f(t) > -d(t) - EPS величина EPS "уравновешивает" только вычислительную погрешность d(t), которая значительно поменьше 10 - 11. Если функция строго монотонная, то EPS можно убрать, и при бесконечном количестве итераций найдется t, отличающееся от правильного в большую или меньшую сторону не более чем на вычислительную погрешность. Случай константной функции (когда начальные положения и скорости совпадают) тогда придется обработать отдельно.

Вывод:
1. Брать EPS = 10 - 11, как предлагает автор, можно. Это не приведет к WA, но этот EPS будет просто лишний.
2. Брать EPS = 0 тоже можно. Тогда нужно отдельно проверять один случай.

Простите, если мои рассуждения не совсем строгие. Цель части разбора, посвященной проблемам с EPS, в том, чтобы объяснить участникам, что 
1. WA по задаче - это их собственная вина, а не вина автора, сделавшего слишком жесткие тесты (к счастью, этот момент все правильно поняли).
2. Возникших проблем можно было избежать, работая с EPS более аккуратно и внеся в свой код совсем небольшие изменения.
3. В некоторых случаях полезно привыкнуть писать код таким образом, чтобы в нем возникало поменьше сомнительных моментов. Например, делать фиксированное количество итераций вместо использования EPS. Ведь при использовании EPS каждый раз надо думать, каким его выбрать.

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

Вообще тут глупо рассуждать на тему, правильно ли писать эту строчку так или неправильно. Все зависит не только от того, какой EPS, а где и зачем он используется. Лучше пусть каждый возьмет свой код и доработает его до правильного решения, а потом строго докажет, как оно работает. Высказанных идей и рекомендаций для этого вполне достаточно.