Ответ 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!) правильно ¹.

Я тестировал коды с различными значениями для n (используя мое решение O(n) в качестве стандарта, см. ниже раздел Старый ответ), и они по-прежнему кажутся правильными.

Этот код основывается на двух гипотезах: templatetypedef и Aleksi Torhamo ². Кто-нибудь хочет доказать это? = D (Обновление 2: PROVEN)

¹ _{Не сразу, я имел в виду почти мгновенно}
² _{Доказана гипотеза Алекси Торхамо о функции 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)

Итак, гипотеза доказана.

Ответ 2

Итак, в перерыве с моей обычной традицией не выставлять алгоритмы у меня нет доказательств, думаю, я должен упомянуть, что есть алгоритм, который кажется правильным для чисел до 50 000+ и работает в O (log n) время. Это связано с Софью Вествуд, с которой я работал над этой проблемой около трех часов сегодня. Все это за нее связано. Эмпирически кажется, что он работает красиво, и это намного, намного быстрее, чем решения O (n).

Одно из наблюдений о структуре этой проблемы состоит в том, что если n достаточно велико (n & ge; 5), то, если вы положили 1 в любом месте, проблема распадается на две подзадачи: одну слева от 1 и одну право. Хотя 1s могут быть помещены в разные половины в разное время, возможное размещение будет таким же, как если бы вы решили каждую половину отдельно и объединили их вместе.

Следующее замечание следующее: предположим, что у вас есть массив размером 2 ^k + 1 для некоторого k. В этом случае предположим, что вы поместили 1 по обе стороны массива. Тогда:

• Следующий 1 расположен на другой стороне массива.
• Следующий 1 расположен посередине.
• Теперь у вас есть две меньшие подзадачи размером 2 ^k-1 + 1.

Важная часть этого состоит в том, что результирующая битовая диаграмма представляет собой чередующуюся последовательность из 1s и 0s. Например:

• При 5 = 4 + 1 получаем 10101
• При 9 = 8 + 1 получаем 101010101
• При 17 = 16 + 1 получаем 10101010101010101

Причина в том, что это имеет значение: предположим, что у вас есть n суммарных элементов в массиве и пусть k - наибольшее возможное значение, для которого 2 ^k + 1 & le; п. Если вы поместите 1 в положение 2 ^k + 1, то левая часть массива до этой позиции закончится тем, что будет чередоваться с чередующимися 1s и 0s, что помещает много единиц в массив.

Что не очевидно, так это то, что размещение 1 бит там, для всех номеров до 50 000, кажется, дает оптимальное решение! Я написал Python script, который проверяет это (используя рекуррентное отношение, подобное одному @justhalf), и кажется, что он работает хорошо. Причина, по которой этот факт настолько полезен, заключается в том, что очень легко вычислить этот индекс. В частности, если 2 ^k + 1 & le; n, то 2 ^k & le; n - 1, поэтому k & le; lg (n - 1). Выбор значения & lfloor; lg (n - 1) & rfloor; так как ваш выбор k затем позволяет вам вычислить битовый индекс, вычислив 2 ^k + 1. Это значение k может быть вычислено в O (log n) времени, и возведение в степень может быть выполнено в O (log n), так что общая продолжительность выполнения - & Theta; (log n).

Единственная проблема заключается в том, что я официально не доказал, что это работает. Все, что я знаю, это то, что это правильно для первых 50 000 ценностей, которые мы пробовали.: -)

Надеюсь, это поможет!

Ответ 3

Я присоединяю то, что у меня есть. Как и у вас, увы, время в основном O(n**3). Но, по крайней мере, это позволяет избежать рекурсии (и т.д.), Поэтому не взорвется, когда вы приблизитесь к миллиону;-) Обратите внимание, что это возвращает лучший найденный вектор, а не счет; например.

>>> solve(23)
[6, 0, 11, 0, 1, 0, 0, 10, 0, 5, 0, 9, 0, 3, 0, 0, 8, 0, 4, 0, 7, 0, 2]

Таким образом, он также показывает порядок, в котором были выбраны 1 бит. Самый простой способ получить счет - передать результат max().

>>> max(solve(23))
11

Или измените функцию, чтобы вернуть maxsofar вместо best.

Если вы хотите запускать номера порядка миллиона, вам нужно что-то радикально другое. Вы даже не можете позволить себе квадратичное время для этого (не говоря уже о таком подходе кубического времени). Вряд ли получится такое огромное улучшение O() от более привлекательных структур данных - я ожидаю, что это потребует более глубокого понимания математики проблемы.

def solve(n):
    maxsofar, best = 1, [1] + [0] * (n-1)
    # by symmetry, no use trying starting points in last half
    # (would be a mirror image).
    for i in xrange((n + 1)//2):
        v = [0] * n
        v[i] = count = 1
        # d21[i] = distance to closest 1 from index i
        d21 = range(i, 0, -1) + range(n-i)
        while 1:
            d, j = max((d, j) for j, d in enumerate(d21))
            if d >= 2:
                count += 1
                v[j] = count
                d21[j] = 0
                k = 1
                while j-k >= 0 and d21[j-k] > k:
                    d21[j-k] = k
                    k += 1
                k = 1
                while j+k < n and d21[j+k] > k:
                    d21[j+k] = k
                    k += 1
            else:
                if count > maxsofar:
                    maxsofar = count
                    best = v[:]
                break
    return best