Иногда вы можете придумать ту или иную идею решения задачи, которая будет работать почти всегда, за исключением нескольких особо подлых случаев. Например, в какой-нибудь геометрической задаче может оказаться, что три точки лежат на одной прямой, или при сортировке может обнаружится несколько одинаковых чисел и т.п. — и это сломает ваш алгоритм. Вероятность таких случаев может быть бесконечно мала (ясно, что если вы возьмёте три случайные точки на плоскости, то почти наверняка они не окажутся на одной прямой), но мы ведь прекрасно знаем, что жюри вполне может подсунуть вам любую подлость. Обычно приходится что-то особенное придумывать, чтобы обработать такие случаи.
Но есть одна простая идея, которая может помочь. Я её никогда практически не использовал, и использовать её надо, конечно, с осторожностью (впрочем, как и любую другую идею: любую идею нельзя использовать слепо, всё, что вы делаете, вы должны понимать), но иногда она, возможно, может вас выручить. Идея состоит в том, чтобы немного подправить тест, в частности, подправить случайным образом. Если вы подправляете тест случайным образом, то наверняка в новом тесте не будет никаких подлых случаев (если эти подлости действительно так редки), только надо подправлять аккуратно. Сильно менять тест, конечно, нельзя — вы должны так изменить тест, чтобы ответ на него не изменился или изменился в пределах допустимой погрешности — но, с другой стороны, надо изменить тест так, чтобы ваша собственная программа заметила изменение (иначе зачем вы его меняли? :) ). В частности, в задачах с вещественными числами вы не будете сравнивать оператором =, надо сравнивать с конечной точностью — а тогда ваше небольшое изменение теста может оказаться незамеченным... В общем, как всегда, что бы вы ни делали, надо думать.
Т.к. я сам эти идеи почти не использовал, то буду приводить те примеры, которые мне сейчас пришли в голову. Я не уверен, что все они корректны, т.е. что во всех примерах эти идеи действительно работают, но представление о том, что можно делать, вы, наверное, получите.
Например, если в задаче построения выпуклой оболочки вам мешали тройки точек, лежащие на одной прямой, то, если вы перед поиском оболочки чуть-чуть, причём случайным образом, сдвинете каждую точку, то таких троек не будет. Ещё пример, и тоже на выпуклую оболочку (так уж получилось). Если мне память не изменяет, я однажды видел такой вариант реализации выпуклой оболочки. Они брали точку на плоскости (не из тех, которые даны во входном файле), которая гарантированно будет внутри оболочки, сортировали все точки по полярному углу относительно неё, и работали дальше. Выбрать такую точку можно было просто — например, как центр тяжести всех точек, но тут могли быть две подлости: во-первых, выбранная точка могла совпасть с какой-нибудь точкой из входного файла, во-вторых, выбранная точка могла случайно оказаться на прямой, соединяющей какие-нибудь две точки из входного файла. Оба этих случая были бы проблемами для их алгоритма, их надо было бы обрабатывать особо. Поэтому они давали каждой точке из входного файла случайный вес и считали центр тяжести таких взвешенных точек. За счёт случайности весов никаких таких подлостей не могло быть. Обратите внимание, кстати, что эта идея никак не портит сам тест, т.е. ответ на тест все равно точно получится правильный. Это аналогично выбору случайного разделительного элемента в QSort’е. Этот пример я привожу не для того, чтобы сказать, что именно так и надо писать выпуклую оболочку — никак нет, её надо писать не так — но для того, чтобы вы поняли, что random можно активно использовать, даже не обязательно вредя тесту.
И ещё пример. Была задача типа такой: на плоскости задано N прямоугольников. Человеку надо пройти из точки A в точку B, не заходя внутрь прямоугольников. При этом он может пролезать в щели сколько угодно маленькой, но ненулевой, ширины. При написании программы у меня возникла проблема именно с этой ненулевостью. Было довольно нетривиально допустить любые щели, но не допустить нулевых. Потому я просто чуть-чуть расширил каждый прямоугольник, так, чтобы бывшие нулевые щели стали вообще закрытыми (прямоугольники будут накладываться), а любые остальные щели остались бы ненулевыми. Не помню, по-моему, у меня программа не получила полный балл по каким-то другим причинам, но идея расширения мне нравится до сих пор.
В общем, основная идея этой темы — что различные подлые случаи можно обрабатывать особо, а можно пытаться их избежать. Можно думать в этом направлении. Думайте, изобретайте.