Thread: Need optimization

I find k a little strange. I wonder what it's purpose is? Is it's limit also 10^5?

Anyway, the first thing you might do is to not rotate the array at all. Just keep an index (iterator/pointer/whatever) to the current "first" element. This also obviates the need to copy the array over and over for all the queries. Now you can just set the index back to 0.

Also, I notice that you are passing the vector by value so that it's copied. You should pass by reference. I'll post a rewrite of your code in a few minutes.

And shouldn't you be re-setting c to zero in your input loop? I don't think you want the total cummulative number of !'s, but just the latest streak.

Yes k has a limit of 10^5.

ok, but, what about the consecutive ones, how to calculate them, after not rotating the array?? should I run a loop from the current till i reaches max size, then set i back to 0 till, the current-1 ??

I tried passing by reference, I was still getting over time limit(sorry this code was not the latest, only this had comments in it )
regarding c, no am, just taking the whole value uptill the ith '?' and rotating the original array by that much step, notice how I give temp=arr for each loop..

I'll try the not rotating idea and show you the code.

Also, you are copying arr to temp so that each set of rotations will always start from the first configuration. But that's not how I interpret the problem. I think each set of rotations is supposed to start where the previous ones have left off. Still, this is just a "correctness" fix, not a performance fix.

EDIT: I can't comprehend your findones routine but it's hard to believe it's any faster than just searching though the vector.

here's the code that I came up with after your comments(this is giving wrong answer to the problem though, also it's still timing out on big input) ,maybe i did something wrong

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;


typedef vector<int> vi;


int max_ones(vector<int> arr,int curr,int k)
{   
    int res=-1;int n=arr.size();


    for(int i=curr;i<n;)
    {
        int c=0;
        while(arr[i]==1)
        {
            c++;i++;
            if(i==n)
            {
                for(int j=0;j<curr;)
                {
                    while(arr[j]==1)
                        {c++;j++;}
                    if(c>res) res=c;
                    c=0;j++;
                }
            }
        }


            if(c>res) res=c;
            i++;
    }
    if(res<=k) return res;
    return k;
}


int main() {




    #ifndef ONLINE_JUDGE
        freopen("inp.txt", "r", stdin);
        freopen("output.txt","w", stdout);
    #endif
        LL n,q,k;cin>>n>>q>>k;  //n is length of sequence of 1s and 0s , q is number of queries k is upperbound to max ones
        vi arr(n); 
    
        for(int i=0;i<n;i++) {cin>>arr[i];} 
        int current=0;
        vi queries; 
        string quer;cin>>quer;  //input quer string
        int c=0;
       
        for(int i=0;i<quer.length();i++)
        {
            if(quer[i]=='!')
            {
                current++;
                if(current>=n)
                    current=current%n;
            }
            else if(quer[i]=='?')
            {
                cout<<max_ones(arr,current,k)<<"\n";
            }


        }


    return 0;
}

Is there any efficient way to get maximum number of ones ? I don't see any better than O(n) ???

Consider:
0110011111011100

The maximum number of 1's is 5. No matter how it's rotated the maximum (possible) will be 5. However, it's possible for it to be rotated in such a way that the max is less than 5. Here is is rotated 7 positions right, now the max is 3.
1101110001100111

Since you are dealing with a single sequence of 1's and 0's read at the beginning of the program upon which you perform a large number of queries, some preprocessing may be fruitful. I'm not sure exactly what, though.

As for counting the max consecutive 1's, this is the simple way to do it. But I think you need something better. Note that I've passed the vector by reference! That's important, although it's not going to speed it up that much.

Code:

int findone(vi &nums, int first, int k) {
    int high = 0, cnt = 0;
    int i = first;
    do {
        if (nums[i])
            ++cnt;
        else {
            if (cnt > high)
                high = cnt;
            cnt = 0;
        }
        i = (i + 1) % nums.size();
    } while (i != first);
    return high < k ? high : k;
}

Still, that k bugs me. It smells like a hint....

Yeah, I didn't even try compiling it. I needed to check for a new high once more after the loop.
However, I think you may be "rotating" in the wrong direction, too, passing in the wrong input.
Rotating to the right moves the "first" element index backwards.

Code:

#include <bits/stdc++.h>
using namespace std;
 
int findone(vector<int> &nums, int first, int k) {
    int high = 0, cnt = 0;
    int i = first;
    do {
        if (nums[i])
            ++cnt;
        else {
            if (cnt > high)
                high = cnt;
            cnt = 0;
        }
        i = (i + 1) % nums.size();
    } while (i != first);
    if (cnt > high) high = cnt;
    return high < k ? high : k;
}
 
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n; // length of sequence of 1s and 0s
    int q; // number of queries
    int k; // upperbound to max ones
    cin >> n >> q >> k;
 
    vector<int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i]; 
 
    int first = 0;
    char ch;
    for (int i = 0; i < q; i++) {
        cin >> ch;
        if (ch == '!') {
            if (--first < 0)
                first = arr.size() - 1;
        }
        else
            cout << findone(arr, first, k) << '\n';
    }
}

Time limit is exceeding in it.
I think, the approach should be changed, not rotating the array was a good start for performance but calculating max 1's each time maybe giving high overhead, which we need to remove somehow..

The code looks correct to me, but I did warn you that it was unlikely to beat the time limit. Those kinds of problems can't usually be solved by a brute force approach. You need to find a "trick".

Do you have any specific input for which the code in post#8 gives the wrong output?

Anyway, I feel like I don't really understand the problem. k seems totally pointless. And the way I understand it, you could just keep track of where the two largest streaks of 1's are situated with respect to the current "first" element.

My bad, I ran the wrong file .. the code works fine, just can't beat the time limit.

Do you have something in mind , about this "tricky" approach, I can't think of any, maybe a pattern or something like that ??

track of two largest streaks ?? how ?? can you maybe show a code snippet of that or something? cause I don't know what you mean by that ...

Well, correct me if I'm wrong, but if in a 1500 bit sequence you knew that the two longest streaks of 1's were one beginning at position 100 going for 42 bits and another starting at position 1202 going for 37 bits, then what is the longest run of 1's if I move the start of the sequence to position 110? What about position 102?

But if that trick actually worked, then it seems too simple, doesn't it? Can you post the link so I can read the original description myself?

I figured out why my trick won't work, and also what k is all about. You need to find the largest run of 1's <= k. So if the max is > k, you can't just return k. You need to return the run of 1's that's no greater than k, i.e., it could be less than k.

Suppose you had run's of these lengths: 2, 5, 6, 7, 3.
If k is 4, then the answer is 3 (not 4).

So the counting routine (the slow one!) should be more like this:

Code:

int count_max_ones(vector<int> &nums, int first, int k) {
    int high = 0, cnt = 0;
    int i = first;
 
    do {
        if (nums[i])
            ++cnt;
        else {
            if (cnt <= k && cnt > high)
                high = cnt;
            cnt = 0;
        }
        i = (i + 1) % nums.size();
    } while (i != first);
 
    if (cnt <= k && cnt > high)
        high = cnt;
 
    return high;
}