Ответ 1
Последний ответ (сложность O (log n))
Если мы полагаем, что гипотеза templatetypedef и Алекси Торхамо ( update: доказательство в конце этого сообщения), есть решение закрытой формы count(n), вычисленное в O(log n) (или O(1) если мы предположим, что логарифм и смещение битов O(1)):
Python:
from math import log
def count(n): # The count, using position k conjectured by templatetypedef
k = p(n-1)+1
count_left = k/2
count_right = f(n-k+1)
return count_left + count_right
def f(n): # The f function calculated using Aleksi Torhamo conjecture
return max(p(n-1)/2 + 1, n-p(n-1))
def p(n): # The largest power of 2 not exceeding n
return 1 << int(log(n,2)) if n > 0 else 0
С++:
int log(int n){ // Integer logarithm, by counting the number of leading 0
return 31-__builtin_clz(n);
}
int p(int n){ // The largest power of 2 not exceeding n
if(n==0) return 0;
return 1<<log(n);
}
int f(int n){ // The f function calculated using Aleksi Torhamo conjecture
int val0 = p(n-1);
int val1 = val0/2+1;
int val2 = n-val0;
return val1>val2 ? val1 : val2;
}
int count(int n){ // The count, using position k conjectured by templatetypedef
int k = p(n-1)+1;
int count_left = k/2;
int count_right = f(n-k+1);
return count_left + count_right;
}
Этот код может правильно вычислить результат для n=100,000,000 (и даже n=1e24 в Python!) правильно 1.
Я тестировал коды с различными значениями для n (используя мое решение O(n) в качестве стандарта, см. ниже раздел Старый ответ), и они по-прежнему кажутся правильными.
Этот код основывается на двух гипотезах: templatetypedef и Aleksi Torhamo 2. Кто-нибудь хочет доказать это? = D (Обновление 2: PROVEN)
1 Не сразу, я имел в виду почти мгновенно
2 Доказана гипотеза Алекси Торхамо о функции f для n<=100,000,000
Старый ответ (сложность O (n))
Я могу вернуть счетчик n=1,000,000 (результат 475712) в 1.358s (в моем iMac), используя Python 2.7. Обновление: это 0.198s для n=10,000,000 в С++. =)
Вот моя идея, которая достигает сложности O(n).
Алгоритм
Определение f(n)
Определите f(n) как число бит, которое будет установлено на битвектор длины n, при условии, что установлены первый и последний бит (кроме n=2, где установлен только первый или последний бит), Поэтому мы знаем некоторые значения f(n) следующим образом:
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 2
f(5) = 3
Обратите внимание, что это отличается от значения, которое мы ищем, поскольку исходный бит может быть не первым или последним, как рассчитывается f(n). Например, мы имеем f(7)=3 вместо 4.
Обратите внимание, что это можно вычислить достаточно эффективно (амортизируется O(n) для вычисления всех значений f до n) с использованием отношения рекуррентности:
f(2n) = f(n)+f(n+1)-1
f(2n+1) = 2*f(n+1)-1
для n>=5, так как следующий бит, установленный после правила, будет средним битом, за исключением n=1,2,3,4. Затем мы можем разбить битвектор на две части, каждая из которых независима друг от друга, и поэтому мы можем вычислить количество бит, установленных с помощью f( floor(n/2) ) + f( ceil(n/2) ) - 1, как показано ниже:
n=11 n=13
10000100001 1000001000001
<----> <----->
f(6)<----> f(7) <----->
f(6) f(7)
n=12 n=14
100001000001 10000010000001
<----> <----->
f(6)<-----> f(7) <------>
f(7) f(8)
мы имеем -1 в формуле, чтобы исключить двойной счет среднего бита.
Теперь мы готовы подсчитать решение исходной задачи.
Определение g(n,i)
Определите g(n,i) как число бит, которое будет установлено на битвектор длины n, следуя правилам в задаче, где начальный бит находится в i -th бит (на основе 1). Обратите внимание, что по симметрии начальный бит может быть от первого бита до ceil(n/2) -th бит. И в этих случаях обратите внимание, что первый бит будет установлен перед любым битом между первым и начальным, и так будет и для последнего бит. Поэтому число бит, установленное в первом разделе и втором разделе, равно f(i) и f(n+1-i) соответственно.
Итак, значение g(n,i) можно вычислить как:
g(n,i) = f(i) + f(n+1-i) - 1
следуя идее при вычислении f(n).
Теперь, чтобы вычислить конечный результат, тривиально.
Определение g(n)
Определите g(n) как счетчик в исходной задаче. Затем мы можем взять максимум всех возможных i, положение исходного бита:
g(n) = maxi=1..ceil(n/2)(f(i) + f(n+1-i) - 1)
Код Python:
import time
mem_f = [0,1,1,2,2]
mem_f.extend([-1]*(10**7)) # This will take around 40MB of memory
def f(n):
global mem_f
if mem_f[n]>-1:
return mem_f[n]
if n%2==1:
mem_f[n] = 2*f((n+1)/2)-1
return mem_f[n]
else:
half = n/2
mem_f[n] = f(half)+f(half+1)-1
return mem_f[n]
def g(n):
return max(f(i)+f(n+1-i)-1 for i in range(1,(n+1)/2 + 1))
def main():
while True:
n = input('Enter n (1 <= n <= 10,000,000; 0 to stop): ')
if n==0: break
start_time = time.time()
print 'g(%d) = %d, in %.3fs' % (n, g(n), time.time()-start_time)
if __name__=='__main__':
main()
Анализ сложности
Теперь интересно, какова сложность вычисления g(n) с помощью метода, описанного выше?
Мы должны сначала заметить, что мы перебираем значения n/2 значения i, положение начального бита. И на каждой итерации мы называем f(i) и f(n+1-i). Наивный анализ приведет к O(n * O(f(n))), но на самом деле мы использовали memoization на f, поэтому он намного быстрее, так как каждое значение f(i) вычисляется только один раз, самое большее. Таким образом, сложность фактически добавляется к времени, требуемому для вычисления всех значений f(n), который вместо этого был бы O(n + f(n)).
Итак, какая сложность инициализации f(n)?
Мы можем предположить, что перед вычислением g(n) мы предварительно сопоставляем каждое значение f(n). Обратите внимание, что из-за отношения повторения и memoization, генерируя все значения f(n), требуется время O(n). И следующий вызов f(n) займет O(1) время.
Таким образом, общая сложность O(n+n) = O(n), о чем свидетельствует это время работы в моем iMac для n=1,000,000 и n=10,000,000:
> python max_vec_bit.py Enter n (1 <= n <= 10,000,000; 0 to stop): 1000000 g(1000000) = 475712, in 1.358s Enter n (1 <= n <= 10,000,000; 0 to stop): 0 > > <restarted the program to remove the effect of memoization> > > python max_vec_bit.py Enter n (1 <= n <= 10,000,000; 0 to stop): 10000000 g(10000000) = 4757120, in 13.484s Enter n (1 <= n <= 10,000,000; 0 to stop): 6745231 g(6745231) = 3145729, in 3.072s Enter n (1 <= n <= 10,000,000; 0 to stop): 0
И как побочный продукт memoization, вычисление меньшего значения n будет намного быстрее после первого вызова большого n, как вы также можете видеть в примере прогона. И с языком, который лучше подходит для хрустания числа, такого как С++, вы можете значительно ускорить время работы
Надеюсь, это поможет. =)
Код с использованием С++ для повышения производительности
Результат в С++ примерно на 68x быстрее (измеряется clock()):
> ./a.out Enter n (1 <= n <= 10,000,000; 0 to stop): 1000000 g(1000000) = 475712, in 0.020s Enter n (1 <= n <= 10,000,000; 0 to stop): 0 > > <restarted the program to remove the effect of memoization> > > ./a.out Enter n (1 <= n <= 10,000,000; 0 to stop): 10000000 g(10000000) = 4757120, in 0.198s Enter n (1 <= n <= 10,000,000; 0 to stop): 6745231 g(6745231) = 3145729, in 0.047s Enter n (1 <= n <= 10,000,000; 0 to stop): 0
Код в С++:
#include <cstdio>
#include <cstring>
#include <ctime>
int mem_f[10000001];
int f(int n){
if(mem_f[n]>-1)
return mem_f[n];
if(n%2==1){
mem_f[n] = 2*f((n+1)/2)-1;
return mem_f[n];
} else {
int half = n/2;
mem_f[n] = f(half)+f(half+1)-1;
return mem_f[n];
}
}
int g(int n){
int result = 0;
for(int i=1; i<=(n+1)/2; i++){
int cnt = f(i)+f(n+1-i)-1;
result = (cnt > result ? cnt : result);
}
return result;
}
int main(){
memset(mem_f,-1,sizeof(mem_f));
mem_f[0] = 0;
mem_f[1] = mem_f[2] = 1;
mem_f[3] = mem_f[4] = 2;
clock_t start, end;
while(true){
int n;
printf("Enter n (1 <= n <= 10,000,000; 0 to stop): ");
scanf("%d",&n);
if(n==0) break;
start = clock();
int result = g(n);
end = clock();
printf("g(%d) = %d, in %.3fs\n",n,result,((double)(end-start))/CLOCKS_PER_SEC);
}
}
Доказательство
Обратите внимание, что для того, чтобы этот ответ (который уже очень длинный) прост, я пропустил некоторые шаги в доказательстве
Гипотеза Алекси Торхамо о значении f
For `n>=1`, prove that: f(2n+k) = 2n-1+1 for k=1,2,…,2n-1 ...(1) f(2n+k) = k for k=2n-1+1,…,2n ...(2) given f(0)=f(1)=f(2)=1
Результат, приведенный выше, можно легко доказать, используя индукцию по рекуррентному отношению, рассмотрев четыре случая:
- Случай 1: (1) для четного
k - Случай 2: (1) для нечетного
k - Случай 3: (2) для четного
k - Случай 4: (2) для нечетного
k
Suppose we have the four cases proven for n. Now consider n+1.
Case 1:
f(2n+1+2i) = f(2n+i) + f(2n+i+1) - 1, for i=1,…,2n-1
= 2n-1+1 + 2n-1+1 - 1
= 2n+1
Case 2:
f(2n+1+2i+1) = 2*f(2n+i+1) - 1, for i=0,…,2n-1-1
= 2*(2n-1+1) - 1
= 2n+1
Case 3:
f(2n+1+2i) = f(2n+i) + f(2n+i+1) - 1, for i=2n-1+1,…,2n
= i + (i+1) - 1
= 2i
Case 4:
f(2n+1+2i+1) = 2*f(2n+i+1) - 1, for i=2n-1+1,…,2n-1
= 2*(i+1) - 1
= 2i+1
Таким образом, по индукции доказана гипотеза.
Гипотеза templatetypedef в наилучшей позиции
For n>=1 and k=1,…,2n, prove that g(2n+k) = g(2n+k, 2n+1) That is, prove that placing the first bit on the 2n+1-th position gives maximum number of bits set.
Доказательство:
First, we have
g(2n+k,2n+1) = f(2n+1) + f(k-1) - 1
Next, by the formula of f, we have the following equalities:
f(2n+1-i) = f(2n+1), for i=-2n-1,…,-1
f(2n+1-i) = f(2n+1)-i, for i=1,…,2n-2-1
f(2n+1-i) = f(2n+1)-2n-2, for i=2n-2,…,2n-1
and also the following inequality:
f(k-1+i) <= f(k-1), for i=-2n-1,…,-1
f(k-1+i) <= f(k-1)+i , for i=1,…,2n-2-1
f(k-1+i) <= f(k-1)+2n-2, for i=2n-2,…,2n-1
and so we have:
f(2n+1-i)+f(k-1+i) <= f(2n+1)+f(k-1), for i=-2n-1,…,2n-1
Now, note that we have:
g(2n+k) = maxi=1..ceil(2n-1+1-k/2)(f(i) + f(2n+k+1-i) - 1)
<= f(2n+1) + f(k-1) - 1
= g(2n+k,2n+1)
Итак, гипотеза доказана.