Thread: Segmentation error

  1. #16
    Registered User
    Join Date
    Nov 2018
    Posts
    25
    I am finding it hard to understand your code, why are you inputting bit twice ?? whats init ?? is that checking if array[0] and array[n-1] both have 1s ?what is place function doing ??
    I really didn't get the record structure as well....

    This is what I am trying to do:
    - I am simply using the counting of 1s to get the first position of every run there is, then I will check if there is a possible run that wraps this, then I will remove the first run saved and last run saved, because I will be combining them now.
    - after this, I simply take 2 heads and 2 tails(if more than 2 runs are there)
    -If there is a tail that wraps it will be >=n and i will use modulus to make it normal..I think I am getting the positions of the runs right, I am having a bit trouble in the outputting part,
    here's what I am doing:

    - If my counts of runs contains only 1 element, meaning only 1 streak, I will check if the 1st tail of the run is greater than n if it is %, and then I will check if current(first pointer) is lying between the streak if it is cut the streak and find max between them, and min between this and k.
    - If I have more than 1 streak, I will first check if any is getting greater than n, if %, then I will check if any is being cut by the current pointer, and then I will have 3 streaks,I will get maximum and minimum between k and print it...
    Still getting wrong answer tho

  2. #17
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    393
    If you don't "get" the Record struct then you simply don't know C++.
    I don't "get" your alg, either!
    Anyway, you sound a little upset.
    Take a break.
    Listen to a tune: Pojama People
    Simplicity is the ultimate sophistication.

  3. #18
    Registered User
    Join Date
    Nov 2018
    Posts
    25
    Yes, maybe I don't know C++ ... but isn't what this forum is for, making others understand what you're trying to do, maybe I am a little frustrated and not thinking straight coz I have been banging my head over this for a week and now that I know I am very close,I am a little desperate... but if we simply said others that you didn't get this, you don't know c++..then its cool with me. anyways, I don't mean this in any disrespectful way, You have been kind enough to give your time for my problem and I am grateful..

  4. #19
    Registered User john.c's Avatar
    Join Date
    Dec 2017
    Posts
    393
    You're upset, but don't put it on me. Just remember the golden rule: nobody cares.
    Simplicity is the ultimate sophistication.

  5. #20
    Registered User
    Join Date
    Nov 2018
    Posts
    25
    never put it on you dude, instead thanked you. cool. good chat.

  6. #21
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    36,689
    ulimit Man Page - Linux - SS64.com
    Consider that the online checking tool may have specified a much lower memory budget for submitted programs.

    Presumably with (perhaps) the intention of preventing brute-force algorithms which see fit to allocate large chunks of memory.

    There may be nothing actually functionally wrong with your code, so long as the platform is willing to give you the memory you need.

    But if the platform won't give you the memory, then segfault is what awaits you.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #22
    Registered User
    Join Date
    Nov 2018
    Posts
    25
    I am not getting segmentation error now, just the implementation is wrong still..some test cases are working perfectly while others giving wrong answer

  8. #23
    Registered User
    Join Date
    Jun 2017
    Posts
    153
    What wrong results did you get, what input did you use?
    Can you post the lastest code?

  9. #24
    Registered User
    Join Date
    Nov 2018
    Posts
    25
    can't see whtats the wrong output, online site doesn't show that, just correct or wrong, some of my test cases passes but some don't:

    Algo:
    Look for two longest streaks of 1s, for rotation keep a pointer(current) and look how much of both of these streaks is being shown, if breaked then divide in two parts and see which is max, the max one is then seen with k, if greater than k then print k, else print max..

    Code:
    #include <iostream>
    #include <cmath>
    #include <algorithm>
    #include <limits>
    #include <vector>
    #include <bitset>
    #include <cstdlib>
    #include <cstdio>
    #include <cstring>
    #include <time.h>
    #include <list>
    #include <set>
    #include <map>
    #include <queue>
    #include <cctype>
    #include <list>
    #include <iterator>
    #include <iosfwd>
    
    
    using std::cin;
    using std::cout;
    using std::vector;
    using std::string;
    using std::map;
    using std::max;
    using std::min;
    
    
    const int MAX=1e5+5;
    
    
    int start_ind_count_ones[MAX];
    bool compa(int a,int b)
    {
        if(a>b) return true;
        return false;
    }
    int main(){
        
    
    
            int n,q,k;cin>>n>>q>>k;  //n->number of elements in input_arrayay,q->number of queries, k->maximum consecutive ones there could be
            vector<int> input_array(n); //input_arrayay for storing numbers
            
            int count_no_of_zero=0;
            for(int i=0;i<n;i++) {cin>>input_array[i];if(input_array[i]==0) count_no_of_zero++;} //elements only of form 1 or 0
        
            string query_string;cin>>query_string;  //query_stringy string which contains only '?' and '!'
            
            if(count_no_of_zero==n) //if all 0s print 0s
            {
                for(int i=0;i<q;i++)
                {
                    if(query_string[i]=='?')
                        cout<<"0\n";
                }
                return 0;
            }
            else if(count_no_of_zero==0) //If all are 1s then print minimum of n-1 or k
            {
    
    
                for(int i=0;i<q;i++)
                {
                    if(query_string[i]=='?')
                        cout<<min(n,k)<<"\n";
                }
                return 0;
            }
            int head_of_1_long_streak=0,tail_of_1_long_streak=0,head_of_2_long_streak=0,tail_of_2_long_streak=0;
            //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=0;int flag=0;
                while(i<n && input_array[i]==1)
                {   
                    if(flag==0) {temp_head=i;flag=1;} //flag needed to secure head of the run
                    c++;i++;
                }
                if(temp_head<n)
                    {start_ind_count_ones[temp_head]=c;
                if(c!=0)
                 temp_ones.push_back(c);}
                i++;
            }
           
            vector<int> new_temp;
            if(temp_ones.size()!=1 && input_array[0]==1 && input_array[n-1]==1) //if array is like [1,....,1]
            {
                int x,y;
                x=temp_ones[0];y=temp_ones[temp_ones.size()-1];
                vector<int> extra(temp_ones.begin()+1,temp_ones.end()-1);  //this is done so that if we have [1,1,0,1,1,1] then we only see one streak of 1s i.e from 3 till 7(here 7 means 1, since this wraps the array)
                new_temp=extra;
                new_temp.push_back(x+y);//push the wrapped length(or count of ones with wrapped 1s)
                for(int i=n-1;i>=0;i--)
                {
                    if(start_ind_count_ones[i]!=0)
                        {start_ind_count_ones[i]=new_temp[new_temp.size()-1];break;}
                }
            }
    
    
            sort(new_temp.begin(),new_temp.end(),compa); //sort in decreasing order
    
    
            for(int i=0;i<n;i++)
            {
                if(start_ind_count_ones[i]==new_temp[0]) // HERE WE will see new_temp[0] contains the longest runs of 1, so we will match this with the array that stored the first index of all the runs
                {
                    head_of_1_long_streak=i;
                    tail_of_1_long_streak=start_ind_count_ones[i]+i-1; //if run is wrapped we will see tail of run as >=n later we will use mod 
                }
                else if( new_temp.size()>=2 && start_ind_count_ones[i]==new_temp[1]) //do same for 2nd longest
                {
                    head_of_2_long_streak=i;
                    tail_of_2_long_streak=start_ind_count_ones[i]+i-1;
                }
            }
    
    
    
    
         // cout<<head_of_1_long_streak<<" "<<tail_of_1_long_streak<<" "<<head_of_2_long_streak<<" "<<tail_of_2_long_streak<<"\n";
            int current=0;// "first" pointer
            for(int i=0;i<q;i++)
            {
                if(query_string[i]=='!') //query for rotation we can simply move the pointer which shows the first element
                {
                    current--;
                    if(current<0)
                        current=n-1;
                }
                else
                {
                    if(new_temp.size()==1) //IF there is only 1 longest run of ones
                    {
                        if(tail_of_1_long_streak>=n)//wrapped 1s
                        {
                            int temp_tail=tail_of_1_long_streak%n;
                            
                            if(current<=temp_tail)   // if the current is in between wrapped ones in the begining
                            {
                                int max_1=temp_tail-current+1;
                                int max_2=new_temp[0]-max_1;
    
    
                                cout<<min(max(max_1,max_2),k)<<"\n";
                            }
                            else if(current>=head_of_1_long_streak)  //if the current is in between wrapped ones in the end
                            {
                                int max_11=current-head_of_1_long_streak+1;
                                int max_12=new_temp[0]-max_11;
    
    
                                cout<<min(max(max_11,max_12),k)<<"\n";
                            }
                            else //this is the case if current doesn't cut the streak of ones
                            {
                                cout<<min(new_temp[0],k)<<"\n";
                            }
                        }
                        else //If we don't have a wrapped ones case then simple breaking of streak
                        {
                            if(current<=tail_of_1_long_streak && current>=head_of_1_long_streak)
                            {
                                int max_1a=tail_of_1_long_streak-current+1;
                                int max_2a=new_temp[0]-max_1a;
    
    
                                cout<<min(max(max_1a,max_2a),k)<<"\n";
                            }
                            else
                                cout<<min(new_temp[0],k)<<"\n";
                        }
                       
                    }
                    else  //case for 2 longest streaks
                    {
                        int new_tail=tail_of_1_long_streak;int new_temp_tail=tail_of_2_long_streak;
                        if(tail_of_1_long_streak>=n) 
                        {
                            new_tail=tail_of_1_long_streak%n;
                        }
                        else if(tail_of_2_long_streak>=n)
                        {
                            new_temp_tail=tail_of_2_long_streak%n;
                        }
                        int max1=new_temp[0];int max2=new_temp[1];
                        int max11=0;int max22=0;
                        if(current<=new_tail && (tail_of_1_long_streak!=new_tail || current>=head_of_1_long_streak))
                        {
                            max1=new_tail-current+1;
                            max11=new_temp[0]-max1;
                        }
                        else if(current>=head_of_1_long_streak && tail_of_1_long_streak!=new_tail)
                        {
                            max1=current-head_of_1_long_streak+1;
                            max11=new_temp[0]-max1;
                        }
                        else if(current<=new_temp_tail && (tail_of_2_long_streak!=new_temp_tail || current>=head_of_2_long_streak))
                        {
                            max2=new_temp_tail-current+1;
                            max22=new_temp[1]-max2;
                        }
                        else if(current>=head_of_2_long_streak && tail_of_2_long_streak!=new_temp_tail)
                        {
    
    
                            max2=current-head_of_1_long_streak+1;
                            max22=new_temp[1]-max2;
                        }
    
    
    
    
    
    
                       // cout<<max1<<" "<<max11<<"\n";
    
    
                        cout<<min(max(max(max1,max11),max(max2,max22)),k)<<"\n";
                    }
                }
            }
    
    
            //cout<<query_string.length()<<"\n";
            //cout<<tick()<<"\n";
        return 0;
    }

  10. #25
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    36,689
    TBH, you could do better with some functions to break up your 200+ line main.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Segmentation Error
    By legase in forum C Programming
    Replies: 7
    Last Post: 12-29-2012, 11:20 AM
  2. Segmentation Error Help!
    By Blah937 in forum C++ Programming
    Replies: 13
    Last Post: 07-08-2011, 09:04 PM
  3. Segmentation Error
    By Native in forum C Programming
    Replies: 2
    Last Post: 10-26-2010, 08:41 AM
  4. segmentation error
    By callkalpa in forum C Programming
    Replies: 2
    Last Post: 12-13-2009, 03:27 AM
  5. Segmentation Error / Bus Error in ANSI
    By drag0n69 in forum C Programming
    Replies: 10
    Last Post: 02-05-2008, 09:45 AM

Tags for this Thread