Thread: Need optimization

If you've seen as many of these problems as me, you'd be suspicious of that k value, too. It's idiotic if it's only purpose is for you to find the largest run of 1's and then either return that or k, whichever is smaller. It's silly. For k to have meaning, it needs to stop some easy method that would otherwise work (or alternatively to constrain the problem so that it's solvable at all). My idea of determining the top two streaks and using only that information to answer the queries would apparently work. You should be able to code that up pretty easily. Determine the two largest runs of 1's (possibly including a run that wraps around the end to the beginning) and then determine how much of each of them is visible for each query.

Hey, if it works, it works and my hunch is wrong. If it doesn't work, I have an idea for dealing with the harder problem.

EDIT: Just read the page again and it does sound like you're right. I don't understand the point of k, then. Why not just return the longest?

Originally Posted by john.c

EDIT: Just read the page again and it does sound like you're right. I don't understand the point of k, then. Why not just return the longest?

There is a time limit. The k should allow a faster result return in some cases.

Tim S.

So I coded the way you told, it did pass the limit, but is giving Segmentation fault error, and I can't seem to find the error

Code:

int streak_1_head,streak_1_tail,streak_2_head,streak_2_tail;
        int start_ones[n]={};//stores the place where each run of 1's start
        vector<int> temp_ones;//stores the count of ones and then sort this to get head and tails..
        for(int i=0;i<n;)
        {   
            int c=0;int temp_head=i;int flag=0;
            while(arr[i]==1)
            {   
                if(flag==0) {temp_head=i;flag=1;} //flag needed to secure head of the run
                c++;i++;
            }
            start_ones[temp_head]=c;
            temp_ones.push_back(c);
            i++;
        }
        int last_temp;  //THIS IS case for wrapping of 1's 
        if(arr[0]==1 && arr[n-1]==1)
        {
            temp_ones.push_back(temp_ones[0]+temp_ones[temp_ones.size()-1]);
            last_temp=temp_ones[temp_ones.size()-1];
            for(int i=n-1;i>=0;i--)
            {
                if(start_ones[i]!=0)
                    {start_ones[i]=temp_ones[temp_ones.size()-1];break;}
            }
        }


        sort(temp_ones.begin(),temp_ones.end(),compa); //sort in decreasing order




        for(int i=0;i<n;i++)
        {
            if(start_ones[i]==temp_ones[0])
            {
                streak_1_head=i;
                streak_1_tail=(start_ones[i]+i-1)%n; //CASE for wrapping 1's 
            }
            else if(start_ones[i]==temp_ones[1])
            {
                streak_2_head=i;
                streak_2_tail=(start_ones[i]+i-1)%n;
            }
        }


       // cout<<streak_1_head<<" "<<streak_1_tail<<"\n";
        int current=0;// "first" pointer
        for(int i=0;i<quer.length();i++)
        {
            if(quer[i]=='!')
            {
                current--;
                if(current<0)
                    current=n-1;
            }
            else
            {
                int max1a=temp_ones[0],max1b=0,max2a=temp_ones[1],max2b=0;
                //DIFFERENT CASES FOR CHECKING HOW CURRENT BREAKS THE RUNS....
                if(current>=streak_1_head && current<=streak_1_tail)
                {
                    max1a=streak_1_tail-current+1;
                    max1b=temp_ones[0]-max1a;
                }
                 if(current>=streak_2_head && current<=streak_2_tail)
                {
                    max2a=streak_2_tail-current+1;
                    max2b=temp_ones[1]-max2a;    
                }


                 if(streak_1_head>streak_1_tail && current<=streak_1_tail) //special case for wrapped ones
                {
                    max1a=streak_1_tail-current+1;
                    max1b=temp_ones[0]-max1a;
                }
                if(streak_2_head>streak_2_tail && current<=streak_2_tail) //special case for wrapped ones
                {
                    max2a=streak_2_tail-current+1;
                    max2b=temp_ones[1]-max2a;
                }
                //cout<<max1a<<" "<<max1b<<"\n";
                int max1=std::max(max1a,max1b);
                int max2=std::max(max2a,max2b);
                int final_max=std::max(max1,max2);
                if(final_max>k) final_max=k;


                cout<<final_max<<"\n";  //the result is correct am just getting SIGSEGV error please help
                   
            }
        }

sc7: I understand that you've run into a problem with your code so you're frustrated, but if there are people who have sufficient interest to wade through your code, they would eventually do so. You really shouldn't go about posting in other people's topics to request for help on this as that is rude, and randomly messaging people who have not commented on your topic in the hope that they would help is rather excessive.

If you do want to increase the likelihood that someone will help you debug your code:

• Format your code properly, especially where indentation is concerned.
• Use descriptive names.
• Write well named functions that do one thing and do it well.
• In natural language, explain step by step the most recent incarnation of your algorithm, with reference to how it is supposed to solve the problem.
• Post a complete program, one that others can compile and run. It would be best to provide test input and corresponding expected output, and since there would be no actual output with a segmentation fault, use a debugger to find out roughly where does the segmentation fault occur with the given test input, and explain that in your post.

Now, it is possible that the first three might slow you down in competitive programming when you know what you're doing, and so I can understand that competitive programmers may not value such practices. That's fine, but if you want to get other people to help you, then these practices that are fairly standard for writing readable, maintainable code now become useful.