... Прошлые выходные не предвещали ничего необычного. По хорошей традиции я опять урвал 1 место по решению задач среди студентов ВГПУ.
Когда я вернулся домой, то вскоре обнаружил список задач, разосланных тренером на решение в течении недели. Решил не откладывать решение и около полуночи сел за решение.
До 4 часов успел сдать 2 из них и довольный пошёл спать.
На следующий день я решил продолжить решение. И тут началось...
за 1 день я каким то чудом смог уложить 6 из 7 задач. Такой "прыти" я сам от себя не ожидал. Тренер тоже был слегка в шоке. Но вечер запомнился решением одной задачи про "Никифора" с Тимуса.
Переборное решение сразу было откинуто, как бесперспективное. Ради смеха решил попробовать следующее:
Очевидно, что каждое 7 число делится на 7. То есть вероятность получить ответ, который бы делился на 7 путём случайной перестановки цифр с отсечением заранее не верных вариантов была было примерно 1 к 7.
В результате я написал программу, которая случайным образом выбирала - какую цифру из данного числа ставить на текущее место.
Сперва получил пару раз WA. Допилил и тут же получил AC со вменем
работы около 0.5 сек (Java).
PS: Тренер сказал, что это было глупо на это полагаться и больше не следует возвращаться к подобной практике использования "подгонки" брут форса за счёт такой "черной магии".
И вот какой у меня вопрос к Вам, как более опытным и успешным участникам соревнований - как Вы относитесь к подобному подходу (использование вероятности) в решении задач, где она в принципе не нужна. Помогало ли она когда нибудь, есть ли смысл вообще задумываться о подобных решениях задач.
UPD: Буду очень признателен, если кто нибудь более точно подсчитает - за сколько попыток создания возможного ответа такая программа выдаст действительно правильный ответ.
То, что ты писал о вероятности появления числа, делящегося на 7, как 1 к 7, то это корректно для произвольного числа. У нас же числа не совсем произвольные (т.к. могут содержать лишь определенные цифры).
Но, я знаю иное решение этой задачи. И из него следует то, что грубая оценка самого худшего случая для вероятности выпадения числа, кратного 7, равна 1 / 24.
Есть 2 типа ситуаций, в которых проходят решения, существенно основанные на random-е.
1. Можно легко посчитать вероятность успеха рандомизированного решения и доказать, что N-е число попыток даст вероятность, близкую к 1.
2. Совсем непонятно, как оценить вероятность. Решение наверняка совсем неправильное, но проходит все тесты жюри. При этом совершенно невозможно специально завалить это решение тестом.
За долгую историю моих выступлений я (или команда) сдавал решения и 1-го, и 2-го типа по нескольким задачам, причем по некоторым это в самом деле выглядело магией. Решения 2-го типа очень часто оказывались на самом деле генетическими алгоритмами:). Если интересно - могу повспоминать примеры таких задач.
О подобных решениях задач следует задумываться в основном тогда, когда достаточно долго не можешь придумать четкое решение, а время в конце контеста остается.
Есть строка s , длиной до 2000 символов. Надо проверить, верно ли, что существует строка t, которая как подпоследовательность встречается не менее чем C(s) / 2 раз, где C(s) - число подпоследовательностей строки s.
Решение: несколько раз повторим следующую процедуру. Выберем случайную подпоследовательность. Посчитаем, сколько раз она встречается в строке. Если это число не меньше половины числа всех подпоследовательностей, тогда ответ на задачу найден. Если после N повторений такая подпоследовательность так и не нашлась, то полагаем, что ее и не существует.
Посчитаем, какова вероятность ошибки, т.е. того, что такая подпоследовательность есть, а мы ее не нашли. Тогда на каждом шаге мы должны были случайным образом подпоследовательность из множества, чья мощность не превосходит C(s) / 2, вероятность чего не более чем 0.5. Поэтому вероятность ошибиться после N повторений есть 2-N .
Детали реализации: подсчет количества вхождений строки как подпоследовательность осуществляется несложной квадратной динамикой. Однако нельзя себе позволить считать точное количество вхождений, т.к. размер чисел будет огромным. Используем следующее предположение: невозможно придумать достаточно длиную строку, в которой какая-то последовательность встречается некоторое число раз, близкое к C(s) / 2, но не равное ему. Тогда динамику считаем 2 раза: один раз - по большому простому модулю, чтобы проверить на равенство C(s) / 2, другой раз - в double, чтобы сравнить.
вообще, конечно, можно и без перебора. можно число распилить на два куска:
A* 10000 + (перестановка из 1,2,3,4 ). перестановками цифр младшей части можно получить любой остаток от деления на 7 (то есть 0,1,2,3,4,5,6). соответственно какой бы остаток не дала старшая часть, всегда найдется подходящая перестановка цифр младшей, что бы свсеси все в 0.
Можно немного улучшить время, если убрать все числа все нули и пробовать перебирать :
(все не нулевые цифры числа)(перестановка {1,2,3,4}) (нули в количестве, равном количеству нулей в "входном" числе)
можно вообще табличку сделать, с помощью калькулятора... и сразу по остатку от старшей части, брать значение из таблицы...
var num, sol : string;
tests, i : integer;
cc : array ['0'..'9'] of integer;
function DoIt( p, ost : integer ) : boolean;
var i : char;
begin
result := false;
if p > length(num) then begin
result := ost = 0;
exit;
end;
for i := '0' to '9' do begin
if (cc[i] > 0) and ((i>'0') or (p>1)) then begin
dec( cc[i] ); sol[p] := i;
result := DoIt( p+1, ( ost * 10 + ( ord(i) - 48 ) ) mod 7 );
if result then exit;
inc( cc[i] );
end;
end;
end;
begin
readln( tests );
{}
while tests > 0 do begin
dec( tests );
readln ( num );
{}
fillchar( cc, sizeof( cc ), 0 );
for i := 0 to length(num ) do inc( cc[ num[i] ] );
{}
sol := num;
if DoIt( 1, 0 ) then writeln( sol ) else writeln( 0 );
end;
end.
А вообще, конечно, обсуждаем вроде бы не тему как решить эту задачу, а о применимости подобных методов в условиях соревнований, и мнение именно по этому поводу хочется услышать.
http://acm.timus.ru/problem.aspx?space=1&num=1219
кто объяснит почему тут катит рандомное решение? и существует ли ни рандомное?
Решение решению рознь.
Может добавите конкретики к Вашему?
Телепатические модули сейчас слишком дорогие...
Да, клево) Не заметил этого 10 месяцев назад.
А как ты вообще про это вспомнил?
некропостить там! :Dнекрофилия )P.S.: Я кстати иногда тоже тот ещё кладоискатель)