An efficient algorithm for thhis problem

[jimky]

I came across this method to find the maximum number of 1s in a given binary array.
https://www.geeksforgeeks.org/length-longest-consecutive-1s-binary-representation/
Now I pose a different question, I want to find the maximum number of 1s by left shifting the binary array.
that is

if array is 1 1 1 0.I get 3.

then left shift it
new array is now 1 1 0 1.
whose answer is 2

and so on for all elements.

The O(n^2) algorithm is easy to get, but is there a more efficient algorithm of this?

[Browni3141]

It's amusing how many people come around asking the same question. Assuming this is for CodeChef, all I'm going to say is that you're thinking about the problem incorrectly, and hopefully that isn't already too much for me to say.

[ne555]

> you're thinking about the problem incorrectly
he's not thinking, that's the problem


Take some small cases and see the output for every number of shifting, you may notice something then.
for example, for 1, 1, 1, 0 you'll have

1110 -> 3
1101 -> 2
1011 -> 2
0111 -> 3

[Browni3141]

This was my strategy. The trick is to notice that if we connect both ends, the answer after shifts is usually the longest contiguous string of ones. I decided that the only important information is the position of the array (how many shifts have occurred), the indices of the best substring, and the value of the second best substring. From this information each query can be answered after any number of shifts by tracking the break point and seeing if the best substring is broken. If the best substring is broken then we select the greatest substring from{secondBest, best partition 1, best partition 2}. We cap the answer to K.

My algorithm required an exception for the case of all ones, which is what the 'flag' is for detecting.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    int N, Q, K;
    cin >> N >> Q >> K;
    vector <bool> data, temp;
    bool flag = 1;
    int j, bit;
    for (j = 0; j < N; j++)
    {
        cin >> bit;
        if (bit == 1)
            temp.push_back(bit);
        else
        {
            flag = 0;
            data.push_back(bit);
            break;
        }
    }
    while (++j < N)
    {
        cin >> bit;
        if (bit == 0)
            flag = 0;
        data.push_back(bit);
    }
    for (auto bit: temp)
        data.push_back(bit);
    int shift = temp.size();
    int bitsSet = 0, secondBest;
    pair <int, int> best(0, -1);
    for (int i = 0; i < data.size(); i++)
    {
        if (data[i] == 1)
            bitsSet++;
        else
        {
            if (bitsSet > best.second-best.first)
            {
                secondBest = best.second-best.first+1;
                best = pair <int, int>(i-bitsSet, i-1);
            }
            else if (bitsSet > secondBest)
                secondBest = bitsSet;
            bitsSet = 0;
        }
    }
    if (bitsSet > best.second-best.first)
    {
        secondBest = best.second-best.first+1;
        best = pair <int, int>(data.size()-bitsSet, data.size()-1);
    }
    else if (bitsSet > secondBest)
        secondBest = bitsSet;
    string queries;
    cin >> queries;
    for (auto ch: queries)
    {
        if (ch == '!')
            shift++;
        if (ch == '?')
        {
            if (flag)
            {
                cout << (N >= K ? K : N) << '\n';
                continue;
            }
            shift %= N;
            int result;
            if ((N-shift) > best.first && (N-shift) <= best.second)
            {
                int leftBranch = (N-shift)-best.first;
                int rightBranch = best.second-(N-shift)+1;
                result = (leftBranch > rightBranch ? leftBranch : rightBranch);
                result = (result > secondBest ? result : secondBest);
            }
            else
                result = best.second-best.first+1;
            cout << (result <= K ? result : K) << '\n';
        }
    }
    return 0;
}

[jonnin]

This was my strategy. The trick is to notice that if we connect both ends, the answer after shifts is usually the longest contiguous string of ones.

?? What input is that NOT the case? The only issue is if, when counting them, there are no zeros, in which case the answer is just the length of the original, 0-infinity shifts (if you mean rotates) all the same.

111110111 is 8. the longest string of ones in that, if it is a circular buffer, is 8. ?? All that remains is to compute how many shifts get you to the pattern.

[dhayden]

When the author of the CodeChef question doesn't know the difference between shift and rotate, it gives me an even lower opinion of codechef.

To be clear, I'm criticizing the codechef author, not the author of this question on cplusplus.com

[Browni3141]

jonnin wrote:

This was my strategy. The trick is to notice that if we connect both ends, the answer after shifts is usually the longest contiguous string of ones.

?? What input is that NOT the case? The only issue is if, when counting them, there are no zeros, in which case the answer is just the length of the original, 0-infinity shifts (if you mean rotates) all the same.

111110111 is 8. the longest string of ones in that, if it is a circular buffer, is 8. ?? All that remains is to compute how many shifts get you to the pattern.

Sorry, I didn't articulate myself very well. I mean that if you compute the greatest contiguous substring of ones in the "circular buffer." it is usually the same as the longest contiguous substring of ones when it is broken. My algorithm tracks the break-point to see if longest contiguous substring in the circular buffer is broken. When it is broken I calculate the greatest of:
{secondBest, best partition 1, best partition 2}

dhayden wrote:

When the author of the CodeChef question doesn't know the difference between shift and rotate, it gives me an even lower opinion of codechef.

Seems like you're just arguing semantics. The problem is pretty well defined to clear up ambiguity. I agree that "rotate" would be a better term, but does it really matter?

[jonnin]

It is CRITICAL actually. As a human, I can unravel what you said, but as a programmer, the term rotate means that the bit that fell off the end comes back onto the data on the other end. The term shift means it falls off the end and a zero comes on the other end. Its minor -- we can figure it out -- but its like going to your doctor and he tells you that your kidney needs to come out, no wait, I meant appendix, I always get those confused...

I see what you did. I understand it.
What I am asking is WHY, because I am slow today and don't see it.
What bit pattern needs you to use second best? I can't find a pattern where the answer is not simply the longest string of 1s you can find once you make it circular (apart from the all ones and all zeros anomaly cases, both of which are trivial to handle). Start on the 1 after any zero, count until you reach a zero, store the start & count, repeat until you get back to the zero you started with. Longest one wins. I don't see any case where you need anything more.

[tpb]

I feel that using a technical term incorrectly in a programming contest question is a problem. In general, the questions can be a little hard to understand, which then becomes part of the challenge. I started trying to solve them yesterday (not knowing the thing ended today!) and I found I had to read the question, study the example, re-read the question, then think about it on paper a bit to make sure I understood what was being asked.

Then I found that if you make a table, starting with their pathetic test inputs and extending them, the answer can jump right out (like the one with the scales that I was looking at the wrong way; turns out to be very simple).

[dhayden]

I thought about the problem some more. I believe can be solved in O(N+Q) time. You make one pass through the N elements in the string and then you can solve each query in constant time. It also requires constant space. All constants are very small.

[Browni3141]

Perhaps it's actually an advantage for then that I'm not very familiar with programming terms when reading these problems, hehe. Sorry for using the problem statement's incorrect terminology, jonnin.

In this example the second best substring matters at the point where the best substring is broken into smaller partitions (length 2) than the second best substring (length 3)

011101111 : max: 4
101110111 : max: 3
110111011 : max: 3

dhayden wrote:

I thought about the problem some more. I believe can be solved in O(N+Q) time. You make one pass through the N elements in the string and then you can solve each query in constant time. It also requires constant space. All constants are very small.

My algorithm performs the queries in constant time after the array is loaded.

[tpb]

It can obviously be solved in O(N+Q). And you certainly don't need to store the bits.

[jonnin]

110111011 : max: 3
I get 4 for this
111101110 (rotated above)

I did it with a 2 min hack that just concat the string to itself and then found the longest string of 1s. here that gives this:
110111011110111011

which isnt likely the 'best' possible algorithm, but its nothing like n squared that was asked about either.

[Browni3141]

tpb wrote:

It can obviously be solved in O(N+Q). And you certainly don't need to store the bits.

You're right you don't have to. I decided to do so because I thought it would make one of the calculations easier.

jonnin wrote:

110111011 : max: 3
I get 4 for this
111101110 (rotated above)

If the state of the array is 110111011 when the '?' query is performed, then the longest contiguous substring is 3. It doesn't wrap around. The reason I considered the wrap around was to generalized the data structure so that queries could be performed without manipulating the data.

[jonnin]

oh, I see. I thought that was the problem you wanted to solve, was finding the longest with any possible rotation. Nevermind my comments then.

[dhayden]

There's also this: "find the length of the longest contiguous subsequence of A with length ≤K such that each element of this subsequence is equal to 1" This seems to mean that you just output min(K, longestSequence) after finding the longest. Is that right or am I missing something?

[Browni3141]

That's right, dhayden.

The actual problem was never posted in this thread.

https://www.codechef.com/NOV18B/problems/HMAPPY1

I believe this problem is post very well there.