Всем привет!
При решении нетривиальных задач на контестах существуют два противоположных подхода. Первый (условно назовем его "научный") — полноценно решать математическую задачу, доказывая все факты и идеи; второй ("магический") — надеяться на свою интуицию и не тратить время на формальные доказательства, доверяя утверждениям, которые кажутся правильными. Также ко второму подходу относятся reverse-engineering подходы вроде "что мог иметь в виду этот автор задачи" и "что вообще тут можно закодить за время контеста".
Раньше я всегда считал, что все применяют исключительно первый подход, а второй — удел шаманов-экстремалов. Однако все чаще я встречаю людей, даже не понимающих, зачем могут потребоваться формальные доказательства на контестах; так что моя вера в доминирование "научного" подхода пошатнулась. Но я до сих пор уверен, что область применимости этого подхода гораздо шире, чем шаманского (например, командные соревнования, где время за компом очень дорого; или регулярные контесты с рейтингом, где важна стабильность; ну и в жизни "после" спортивного программирования работать придется именно так). Однако похоже, что "магия" иногда дает более хорошие результаты благодаря увеличению дисперсии (например, для не самых сильных участников на отборах на суровые онсайты: за счет большей дисперсии вероятность попасть в топ-N увеличивается).
Собственно, предлагаю в комментариях к этому посту обсудить преимущества и недостатки обоих подходов, а также собрать статистику, кто каким подходом пользуется. Поскольку голосований на codeforces к сожалению нет, предлагаю использовать первые комментарии к этому посту.
Плюсуйте этот комментарий, если вы доказываете на контестах все или почти все нетривиальные утверждения.
Плюсуйте этот комментарий, если вы доказываете то, что можете доказать, но если не получается сделать это быстро — то пробуете закодить решения с правдоподобными идеями.
Плюсуйте этот комментарий, если вы никогда или почти никогда не доказываете нетривиальные утверждения, доверяя своей интуиции или внематематическим соображениям.
Минусуйте этот комментарий для сохранения баланса вклада.
непонятно, зачем подобные комменты, нам не жалко
раз минусуют, значит кому-то жалко?
Чтобы не пошатнулась вера в дисперсию (распределения вклада).
Наверное, надо на более видном месте это написать.
В силу своей тупости, 99% задач решаю либо на интуиции, либо "баян, уже решал". Подход отстойный, стараюсь переучиваться, потому что с повышением сложности задач он перестаёт работать совсем.
Минус один человек доказывает все на контестах.
Потом пришел eatmore, их стало ноль.
Мы в команде иногда пытаемся ценить время. Если это примерно начало контеста, то почти всегда добиваемся доказательства алгоритма. Если уже почти конец, то забиваем на доказательства, если идея хоть чуть-чуть на правду похожа.
Бывает так, что иногда проще проверить идею, потратить попытку, чем пытаться найти ей объяснение. Конечно, иногда это чревато тем, что мы хватаемся за неправильную идею и начинаем её пропихивать. А иногда этот подход даёт неплохой profit.
Оптимальная стратегия -- делать все с точностью до наоборот. В начале контеста решать очевидные задачи, где очевидное решение очевидно работает. А в конце -- доказывать все нетривиальные идеи, это разумно, так как легко нарваться на правдоподобную лажу.
Естественно, в задачах типа А+В мы не доказываем единственность суммы и прочую херню. Если решение очевидно, то пишем сразу.
Иногда, если компьютер простаивает, начинаем писать идею, по ходу иногда доказывается.
Порой попадаются такие задачи в которых можно легко угадать решение (которое еще и просто пишется), а доказать идею даже за контест очень трудно. В таких случаях нужно просто правильно закодить и послать. Я сторонник первой идеи, о чем постоянно жалею. Пример: задача. Ответом этой задачи является тройка взвешенных средних значений. На контесте, чтобы решить эту задачу я выписал частные производные по трем переменным приравнял их 0 честно нашел решение и получил (через 1 час) вот это чудо. Когда мы после контеста обсуждали кто, как и что решил мой сокомандник (который быстро сдал эту задачу) сказал так: "Я ничего не доказывал, просто угадал ответ и все".
Мне кажется, что лучше сочетать оба подхода, но предпочитать все-таки первый. Доказательство решений внесет свой вклад в повышение стабильности, ну а если доказать не получается, а интуиция работает правильно — в таких случаях получится решить больше задач, чем соперники, которые все доказывают.
Вопрос: можно ли считать доказательством нестрогие логические рассуждения (вида "написал/нарисовал что-то на бумажке и опа — вот оно, очевидное решение")?
Можно считать это "предпосылкой к доказательству", если отсутствуют фразы "такого, наверное, не бывает".
А большее лично мне редко нужно.
Не всегда бывает возможно все доказать. Например, часто встречаются задачи, где надо написать какой-нибудь перебор и увидеть, что бывает не очень много состояний. Шаманство? Да, но это необходимое шаманство.
Или вот еще один пример: в какой-нибудь задаче, где надо что-то посчитать, написать тупое решение для маленьких чисел и втыкать в распечатку ответов. Считать ли это шаманством? Обычно, прочитав обфусцированное условие, написав перебор, и увидев какой-нибудь треугольник паскаля по модулю два, хочешь скорее сдать задачу, по которой уже столбик плюсов, а не разбираться с тем нонсенсом, который придумал автор.
Шаманство как отсутствие формальных доказательств — это не всегда попытка пропихнуть что-то, что случайно придумал. На последнем финале мы в последней из сданных задач написали переборное решение и проверили стресстестом факт, казавшийся очень правдоподобным, после чего написали решение, использующее его, и получили свой AC. Такое использование магии вполне оправданно, особенно с учетом reverse engineering-a "что мог иметь в виду автор" и "что могли написать все остальные команды".
Вообще, сложно себе представить "честное" решение задачи, абсолютно никак не использующее reverse-engineering. Сама мысль вроде "а не попробовать ли свести это к потоку" уже в некотором смысле подразумевает "а что может хотеть от нас автор". Задачи в ограничениях на входные данные часто подсказывают решение (n<=20 => перебор масок, n <= 5000 => что-нибудь за квадрат), а монитор контеста сообщает нам информацию о сложности задачи. С такими "подсказками" можно придумать и полностью доказать решение, но отнести такой способ к "научному" подходу или к "шаманству" однозначно нельзя.
Каждый из нас немного шаман и в этом нет ничего плохого (за исключением синезеленых, вылезающих с тупой жадностью на 470 из 500, которая потом проходит систесты. как им не стыдно).
Для синезелёных на одну жадность найдётся десять динамик. ;)
Ну да, иногда приходтся сдавать задачи не вполне математически честными методами. Однако с некоторыми примерами я не согласен. "_Например, часто встречаются задачи, где надо написать какой-нибудь перебор и увидеть, что бывает не очень много состояний_" — если автор при этом не умеет доказывать, что состояний всегда мало, то задача подготовлена халтурно: вдруг есть тест, на котором состояний много, но автор про него не знает? Надеяться на слабые тесты — в последнее время довольно успешная стратегия, но ИМХО категорически неправильная.
Под не-reverse-engineering методами я имел в виду те методы, которые использовались бы для решения задачи, если не было бы известно, что это задача с контеста или что кто-то до этого её решил. "_Напечатать табличку и посмотреть при небольших n_" вполне используется при решении реальных задач в науке, правда, после этого обычно всё же доказывают найденную закономерность. "_А не попробовать ли свести к потоку_" — тоже абсолютно научный метод, поток — один из "молотков", позволяющих решать большие классы задач, так что пытаться его применить совершенно нормально.
По остальным примерам возражений у меня нет, например, на ограничения я и сам смотрю при решении задач. Под шаманством я скорее имел в виду немного другие ситуации. Например, когда человек пишет жадность, не имея не малейшего понятия, с чего она вообще должна работать, и обосновывает это аргументами вроде "а почему бы и нет" или "ничего сложнее жадности тут за время контеста не получится закодить" (реальные примеры).
Что касается перебора, бывает, когда тест всего один или их мало, и совесть автора может быть чиста. Но даже и без этого задачу могут дать, например, нехорошая задача G. Надеяться на слабые тесты — это скорее знать, что тест против твоего решения существует, но надеяться, что о нем не знает или не подумал автор.
В условиях контеста ее можно доказать или не доказать, результат скорее всего будет один и тот же (АС). Если автор специально придумает сложную формулу для чисел от 1 до n, стоит ли тратить время? (за исключением случая, когда автор тролль и ответы от 1 до n получаются только для маленьких чисел, но такого, к сожалению, ни разу не встречал)
Но ведь к задаче линейного программирования вряд ли кто-нибудь будет сводить задачу на контесте. Дело-то вот в чем.
Про синезеленых и их жадность на жадности я осведомлен, но здесь я хочу лишь сказать, что шаманство в малых дозах полезно и даже необходимо.
"ну и в жизни "после" спортивного программирования работать придется именно так"
Если говорить "про жизнь", например, то, работая 2+ лет в области количественных исследований на финансовых рынках, могу сказать, что и здесь "шаманизм" обычно работает гораздо лучше "научных" решений (именно не так же, как зачастую в задачах, имеющих точный ответ, а лучше — поскольку в задачах прогнозирования наилучшего решения, как правило, не бывает, в том смысле, что оно заведомо недостижимо).
Так что шаманизм — это тру, научный подход — занудство =)
Здесь сложно провести границу между "научным" и "инженерным" подходом. В научном надо опираться на аксиоматику, в инженерном — на эмпирические данные. Научный подход применим только для корректных строго формализованных задач, на практике такое бывает редко, поэтому в пограничных областях вроде программирования правильно смешивать — распиливаем/обобщаем задачу, где можно применять "научные" методы (важнейший параметр практических задач — соотношение результата и трудозатрат), применяем, в остальном — угадываем и экспериментируем. В конечном итоге все равно важно, взлетит самолет или не взлетит — доказательства мало кого волнуют.
Обычно, наверное, действительно сложно отделить "научный" и "инженерный" подходы, но в моей области это возможно.
Например, в теории финансов есть множество моделей ценообразования активов, в том числе позаимствованных из физики (например, GBM), поэтому здесь также возможен строго "научный" подход. Однако обычно он работает хуже технического анализа, который официальная финансовая наука, к слову, считает абсолютно бесполезной и антинаучной штукой.
Доказывать идеи — это неплохо. Не всегда, правда, получается придумать доказательство во время контеста, но после контеста можно спокойно сесть и подумать, почему так. Лично я считаю, что угадывать решение вполне нормально, главное — угадать правильно. В конце концов, во время контеста важна каждая минута, и, если вы сдадите не доказанное решение — вы от этого только выиграете(еще раз повторюсь — когда начинаете писать идею — должна быть твердая уверенность что идея правильная).
Совершенно другое дело — когда автор дает задачу, где интуитивно понятно, что будет мало состояний — но доказательство этой малости не было получено. Вот лично мне такие задачи не нравятся(не знаю правда, как остальным). Понятное дело, что нужно уметь решать всякие задачи — но слушать на разборе про авторское шаманство, честно говоря, не очень прикольно:(. Хочется на разборе увидеть математическую стройность.
Утверждение. Если в голосовании есть три пункта:
Всегда А
Всегда Б
Когда имеет смысл -- А, когда имеет смысл -- Б
Всегда выиграет третий.
По теме, я даже где-то использовал термин "доказательства в стиле ICPC". Допустим что утверждение Х ложно. Тогда не понятно, как решить задачу с заданными ограничениями. Отсюда очевидно, что утверждение Х верно.
Вообще, люди очень много внимания уделяют ограничениям, и часто решают задачи отталкиваясь от них. На одном из codechef была задача такого вида: есть дерево, в нем вершины пронумерованы от 1 до N, но не обязательно в порядке какого-то обхода. Для каждой вершины известна сумма номеров ее детей. Надо найти корень. Вершин 30. Решение простое -- это сумма от 1 до N минус сумма сумм номеров детей. Но ограничение в 30 заставляло людей думать в совсем другую сторону, и многие в итоге задачу не сдали. Было бы ограничение в сто тысяч, сдали бы все :)