Булева функция

Задача предусматривает несколько подходов решения. Наиболее предпочтительными являются рассмотрение всех частных случаев функции f и метод динамического программирования. Какие-либо методы перебора всевозможных булевых значений функции не гарантируют полного решения в силу больших ограничений на N. Однако, даже такой метод решения позволяет пройти более 40% предложенных тестов.

Рассмотрим метод, основанный на переборе всевозможных вариантов функции f. Очевидно, что всего существует 16 таких вариантов. Нам следует рассмотреть каждый в отдельности, и понять: какой ответ будет в каждом из них. Рассмотрим все такие случаи:

• f(1,1)=1: легко видеть, что в этом случае ответ, состоящий из N единиц, является оптимальным. Причем, здесь мы сразу рассматриваем 8 вариантов функции f: 0001, 0011, 0101, 0111, 1001, 1011, 1101 и 1111 (в формате входных данных, все оканчивающиеся на единицу);
• f="0000": в этом случае при любом наборе аргументов мы никогда не сможем получить в результате единицу, поэтому в данном случае ответом будет "No solution";
• f="0010": здесь ответом будет последовательность вида 10000.... (единица и N-1 нолей)
• f="0100", "0110": эти два варианта функции предполагают одинаковый ответ, который зависит от четности N. Если N-нечетно, то в качестве ответа будут все N единиц, в противном случае будут так же все единицы за исключением предпоследнего значения, т.е. последовательность вида 111...11101;
• f="1000": здесь ответом будет последовательность из N-1 единицы и одного ноля в конце кроме случая, когда N=2 (тогда ответом будет 00);
• f="1010": здесь ответ похож на предыдущий случай (N-1 единица и ноль в конце), но без частных случаев;
• f="1100": при нечетном N ответ будет состоять из всех N единиц, в противном случае в начале данной последовательности должен быть 0, а затем N-1 единица;
• f="1110": здесь ответом будет служить последовательность из N единиц в случае нечетного N, иначе ответ будет вида 111...110 (N-1 единица и 0 в конце).

Данное решение не вызывает сложностей в реализации, но требует аккуратного рассмотрения всех случаев. Заметим также, что сложность данного алгоритма равна O(N).

Данный вариант решения задачи заключается в использовании метода динамического программирования. Пусть a[i][j] - максимально возможное количество единиц в последовательности из i аргументов, таких что результатом вычисления функции будет значение j. В случае, когда такой последовательности не существует, то будем полагать a[i][j]=-1. Здесь у нас i=2..N, j=0..1 . В качестве начальных значений можно взять a[2][j], далее увеличивая i от 3 до N можно найти значение a[N][1], в котором и будет хранится искомое количество единиц конечного ответа (либо -1 в случае "No solution").

Для вычисления значения a[i][j] следует рассмотреть всевозможные пары (x,y) такие, что f(x,y)=j. Далее среди этих пар нужно выбрать максимальное значение (a[i-1][x]+y), которое и следует записать в a[i][j]. В случае отсутствия таких пар следует положить a[i][j]=-1. Поскольку в качестве ответа мы хотим получить не только число единиц, но и саму последовательность булевых значений, то для каждого значения a[i][j] следует запоминать ту пару (x,y) при которой был достигнут максимум, тогда по завершении процесса возможно будет восстановить всю последовательность значений.

С точки зрения сложности реализации данный алгоритм несколько сложнее предыдущего, однако является весьма приемлемым и имеет линейную сложность O(N).

[Обсуждение] [Все попытки] [Задача]