Thread: Need optimization

  1. #16
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    393
    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?
    Last edited by john.c; 4 Days Ago at 08:21 PM.
    Simplicity is the ultimate sophistication.

  2. #17
    Registered User
    Join Date
    Nov 2018
    Posts
    25
    I understand why you are emphasising so much on the k value, in the beginning, even I thought that the answer is very dependent on k, then realised, no it's an idiotic way to make this problem unique maybe...
    your approach doesn't sound that easy but I'll try it and get back to you.

  3. #18
    Registered User
    Join Date
    May 2009
    Posts
    3,449
    Quote Originally Posted by john.c View Post
    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.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  4. #19
    Registered User
    Join Date
    Nov 2018
    Posts
    25
    How?? the result is calculated arithmetically, I need to find the max run of 1's anyhow for each query and check at the end whether it is smaller than or greater than k, and return my result...

  5. #20
    Registered User
    Join Date
    Nov 2018
    Posts
    25
    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
                       
                }
            }
    Last edited by sc7; 4 Days Ago at 11:30 PM.

  6. #21
    Registered User
    Join Date
    Nov 2018
    Posts
    25
    @john.c can you please debug this ??

  7. #22
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,041
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #23
    Registered User
    Join Date
    Nov 2018
    Posts
    25
    Sorry for messaging you privately and posting in other's thread, but I was desperate to get my code right I think...
    I did provide proper naming and indentation and the algorithm is already discussed in this thread.
    Sadly I don't know how the debugger works, I'll work on it after this, but the thing is in my IDE (sublime text) it's working perfectly with a large input .. but it shows segmentation error on an online IDE, and that's why I don't understand what to see here, even checked all boundary cases and such...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help w/optimization
    By dudeomanodude in forum C++ Programming
    Replies: 3
    Last Post: 02-08-2008, 02:45 PM
  2. optimization
    By strickey in forum C++ Programming
    Replies: 7
    Last Post: 04-19-2007, 05:28 AM
  3. Optimization.
    By Lithorien in forum C++ Programming
    Replies: 14
    Last Post: 10-07-2004, 12:21 AM
  4. optimization
    By krithi in forum C Programming
    Replies: 9
    Last Post: 01-19-2003, 10:52 AM
  5. IDE optimization
    By Traveller in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 07-04-2002, 02:01 AM

Tags for this Thread