at1's blog

By at1, 9 years ago, In Russian,

Контест

  Мне контест очень понравился, как отличная тренировка решения ботвистых задач. Мне не нравится, когда условие неполно, некорректно, неоднозначно. Здесь же все условия интуитивно понятные (мне) и, вроде, абсолютно корректные.
  Также, по задачам подготовлены очень хорошие тесты (могу оценивать только то, что дорешал 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 продолжать смысла особого нет.
 
 
 
 
  • Vote: I like it
  • +16
  • Vote: I do not like it