StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
19309344
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
8
CommunityOwnedDate
CreationDate
2013-10-11T02:33:07.980
FavoriteCount
0
LastActivityDate
2015-12-14T04:36:08.137
LastEditDate
2015-12-14T04:36:08.137
LastEditorUserId
895932
OwnerUserId
895932
ParentId
19306692
PostTypeId
2
Score
12
ViewCount
0
LastEditorDisplayName
text
Body
<h1>Latest answer (O(log n) complexity)</h1> If we believe the conjecture by templatetypedef and Aleksi Torhamo (update: proof at the end of this post), there is a closed form solution <code>count(n)</code> calculable in <code>O(log n)</code> (or <code>O(1)</code> if we assume logarithm and bit shifting is <code>O(1)</code>): Python: <pre class="lang-python prettyprint-override"><code>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 </code></pre> C++: <pre class="lang-cpp prettyprint-override"><code>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; } </code></pre> This code can calculate the result for <code>n=100,000,000</code> (and even <code>n=1e24</code> in Python!) correctly in no time1. I have tested the codes with various values for <code>n</code> (using my <code>O(n)</code> solution as the standard, see Old Answer section below), and they still seem correct. This code relies on the two conjectures by templatetypedef and Aleksi Torhamo2. <s>Anyone wants to proof those? =D</s> (Update 2: PROVEN) 1By no time, I meant almost instantly 2The conjecture by Aleksi Torhamo on <code>f</code> function has been empirically proven for <code>n<=100,000,000</code> <hr /> <h1>Old answer (O(n) complexity)</h1> I can return the count of <code>n=1,000,000</code> (the result is <code>475712</code>) in 1.358s (in my iMac) using Python 2.7. Update: It's 0.198s for <code>n=10,000,000</code> in C++. =) Here is my idea, which achieves <code>O(n)</code> time complexity. <h1>The Algorithm</h1> <h2>Definition of <code>f(n)</code></h2> Define <code>f(n)</code> as the number of bits that will be set on bitvector of length <code>n</code>, assuming that the first and last bit are set (except for <code>n=2</code>, where only the first or last bit is set). So we know some values of <code>f(n)</code> as follows: <pre><code>f(1) = 1 f(2) = 1 f(3) = 2 f(4) = 2 f(5) = 3 </code></pre> Note that this is different from the value that we are looking for, since the initial bit might not be at the first or last, as calculated by <code>f(n)</code>. For example, we have <code>f(7)=3</code> instead of 4. Note that this can be calculated rather efficiently (amortized <code>O(n)</code> to calculate all values of <code>f</code> up to <code>n</code>) using the recurrence relation: <pre><code>f(2n) = f(n)+f(n+1)-1 f(2n+1) = 2*f(n+1)-1 </code></pre> for <code>n>=5</code>, since the next bit set following the rule will be the middle bit, except for <code>n=1,2,3,4</code>. Then we can split the bitvector into two parts, each independent of each other, and so we can calculate the number of bits set using <code>f( floor(n/2) ) + f( ceil(n/2) ) - 1</code>, as illustrated below: <pre> 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) </pre> we have the <code>-1</code> in the formula to exclude the double count of the middle bit. Now we are ready to count the solution of original problem. <h2>Definition of <code>g(n,i)</code></h2> Define <code>g(n,i)</code> as the number of bits that will be set on bitvector of length <code>n</code>, following the rules in the problem, where the initial bit is at the <code>i</code>-th bit (1-based). Note that by symmetry the initial bit can be anywhere from the first bit up to the <code>ceil(n/2)</code>-th bit. And for those cases, note that the first bit will be set before any bit in between the first and the initial, and so is the case for the last bit. Therefore the number of bit set in the first partition and the second partition is <code>f(i)</code> and <code>f(n+1-i)</code> respectively. So the value of <code>g(n,i)</code> can be calculated as: <pre><code>g(n,i) = f(i) + f(n+1-i) - 1 </code></pre> following the idea when calculating <code>f(n)</code>. Now, to calculate the final result is trivial. <h2>Definition of <code>g(n)</code></h2> Define <code>g(n)</code> as the count being looked for in the original problem. We can then take the maximum of all possible <code>i</code>, the position of initial bit: <pre> g(n) = maxi=1..ceil(n/2)(f(i) + f(n+1-i) - 1) </pre> Python code: <pre class="lang-python prettyprint-override"><code>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() </code></pre> <h1>Complexity Analysis</h1> Now, the interesting thing is, what is the complexity of calculating <code>g(n)</code> with the method described above? We should first note that we iterate over <code>n/2</code> values of <code>i</code>, the position of initial bit. And in each iteration we call <code>f(i)</code> and <code>f(n+1-i)</code>. Naive analysis will lead to <code>O(n * O(f(n)))</code>, but actually we used memoization on <code>f</code>, so it's much faster than that, since each value of <code>f(i)</code> is calculated only once, at most. So the complexity is actually added by the time required to calculate all values of <code>f(n)</code>, which would be <code>O(n + f(n))</code> instead. So what's the complexity of initializing <code>f(n)</code>? We can assume that we precompute every value of <code>f(n)</code> first before calculating <code>g(n)</code>. Note that due to the recurrence relation and the memoization, generating the whole values of <code>f(n)</code> takes <code>O(n)</code> time. And the next call to <code>f(n)</code> will take <code>O(1)</code> time. So, the overall complexity is <code>O(n+n) = O(n)</code>, as evidenced by this running time in my iMac for <code>n=1,000,000</code> and <code>n=10,000,000</code>: <pre> > 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 </pre> And as a by-product of memoization, the calculation of lesser value of <code>n</code> will be much faster after the first call to large <code>n</code>, as you can also see in the sample run. And with language better suited for number crunching such as C++, you might get significantly faster running time I hope this helps. =) <h2>The code using C++, for performance improvement</h2> The result in C++ is about 68x faster (measured by <code>clock()</code>): <pre> > ./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 </pre> Code in C++: <pre class="lang-cpp prettyprint-override"><code>#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); } } </code></pre> <hr /> <h2>Proof</h2> note that for the sake of keeping this answer (which is already very long) simple, I've skipped some steps in the proof Conjecture of Aleksi Torhamo on the value of <code>f</code> <pre> 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 </pre> The result above can be easily proven using induction on the recurrence relation, by considering the four cases: <ul> <li>Case 1: (1) for even <code>k</code></li> <li>Case 2: (1) for odd <code>k</code></li> <li>Case 3: (2) for even <code>k</code></li> <li>Case 4: (2) for odd <code>k</code></li> </ul> <pre> 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 </pre> So by induction the conjecture is proven. Conjecture of templatetypedef on the best position <pre> 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. </pre> The proof: <pre> 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) </pre> And so the conjecture is proven.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POFast way to place bits for puzzle
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USjusthalf
UserOwnerUserId
1. USjusthalf
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POFast way to place bits for puzzle
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.