Need help with finding a linear algorithm

[Nineshadow]

We have a binary representation of a number , let's say 101101001100 . A subsequence from the original binary representation is called <something> (forgot the exact name) if it contains (strictly) more bits of value 1 than bits of value 0. The maximal subsequence of this kind is , obviously , the longest subsequence formed from the original binary representation which follows the rule specified above. In our case, that would be 10110100110 (the original number without the last 0) .

The restriction of the length of binary representation is 300 000 from what I can remember (the binary representation is not longer than 300 000 digits of 0-s and 1-s)

 

The problem here is to find the length of the maximal subsequence, and if there's more than just 1 , also to output the number of them. For the maximum of points, I have to implement it in a linear algorithm.

So far, I've thought about looking at the edge of a subsequence, left and right, starting from the original sequence , check some stuff, change the left and right pointers if it's the case, check again, etc. I've implemented it , it works, but it's not fast enough. I'm currently trying to optimize it using bitwise operations , maybe that will work better, but I doubt it. I'm also trying to see if I can solve it just by using binary operators somehow.

@Ciccioo

[Bene]

We have a binary representation of a number , let's say 101101001100 . A subsequence from the original binary representation is called <something> (forgot the exact name) if it contains (strictly) more bits of value 1 than bits of value 0. The maximal subsequence of this kind is , obviously , the longest subsequence formed from the original binary representation which follows the rule specified above. In our case, that would be 10110100110 (the original number without the last 0) .

The restriction of the length of binary representation is 300 000 from what I can remember (the binary representation is not longer than 300 000 digits of 0-s and 1-s)

 

The problem here is to find the length of the maximal subsequence, and if there's more than just 1 , also to output the number of them. For the maximum of points, I have to implement it in a linear algorithm.

So far, I've thought about looking at the edge of a subsequence, left and right, starting from the original sequence , check some stuff, change the left and right pointers if it's the case, check again, etc. I've implemented it , it works, but it's not fast enough. I'm currently trying to optimize it using bitwise operations , maybe that will work better, but I doubt it. I'm also trying to see if I can solve it just by using binary operators somehow.

@Ciccioo

 

 

Let segment from i to j has M more 1's than 0's, 

and segment from i+1 to j+1 has N more 1's than 0's, (M, N can be negative)

 

then either N==N, or M-N=2 or M-N=-2,

 

i ..................j j+1

0xxxxxxxxxxxx0

0xxxxxxxxxxxx1

1xxxxxxxxxxxx0

1xxxxxxxxxxxx1

 

then segment from i to j+1 has (M+N)/2 1's than 0's.

 

Algorithm:

 

1.Allocate two array of the same length of input segment, (int32 type?)

2. initialize one array according to the bits of input segment (1 and -1 for 1's and 0's)

do 

  average of adjacent cells, put result into another array, 

  if all value are 0 or negative, then stop

  else swap two array and continue

 

The result are stored in the array which still has positive value(s), The offset these positive values are the start index, the iteration times are the length.

 

[Bene]

 

 

seg.png

 

Let segment from i to j has M more 1's than 0's, 

and segment from i+1 to j+1 has N more 1's than 0's, (M, N can be negative)

 

then either N==N, or M-N=2 or M-N=-2,

 

i ..................j j+1

0xxxxxxxxxxxx0

0xxxxxxxxxxxx1

1xxxxxxxxxxxx0

1xxxxxxxxxxxx1

 

then segment from i to j+1 has (M+N)/2 1's than 0's.

 

Algorithm:

 

1.Allocate two array of the same length of input segment, (int32 type?)

2. initialize one array according to the bits of input segment (1 and -1 for 1's and 0's)

do 

  average of adjacent cells, put result into another array, 

  if all value are 0 or negative, then stop

  else swap two array and continue

 

The result are stored in the array which still has positive value(s), The offset these positive values are the start index, the iteration times are the length.

 

 

There is a mistake, if M==N, for 0xxxxxxx0 case result is (M+N)/2-1, 

but for 1xxxxxxxxxx1 case shouldbe (M+N)/+1,

So it depends on the bits at index i,