Thread: Segmentation error

  1. #1
    Registered User
    Join Date
    Nov 2018
    Posts
    32

    Segmentation error

    Following is the code to a problem I have been doing over course of 1 week , I came close, 1subtask(With huge input) is passing , but other testcases are showing Runtime error(SIGSEGV)(Segementation fault)

    The question problem: Contest Page | CodeChef

    Basic IDEA:
    - keep track of two of the longest streaks of ones and after each rotation query, change the pointer of the starting index(rotation) and check how this cuts both the streaks(making possibly 4 streaks) and out of which find the max and print.

    Problem:
    Segmentation error..

    The source code:
    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;
    
    
    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() {
        
    
    
            long long n,q,k;cin>>n>>q>>k; 
            vector<int> arr(n); 
    
    
            for(int i=0;i<n;i++) {cin>>arr[i];} 
    
    
            string query_string;cin>>query_string;  
    
    
            int highest_1_start_ind=0,highest_1_end_ind=0,highest_2_start_ind=0,highest_2_end_ind=0;
          
            vector<int> count_of_ones;
             for(int i=0;i<n;)
            {   
                int c=0;int starting_ind=0;int f=0;
                while(arr[i]==1)
                {   
                    if(f==0) {starting_ind=i;f=1;} 
    
    
                    c++;i++;
                }
                if(starting_ind<n)
                    {start_ind_count_ones[starting_ind]=c;
                count_of_ones.push_back(c);}
                i++;
            }
            int last_count_of_ones;  
    
    
            if(arr[arr.size()-1]==1 && arr[0]==1)
            {
                count_of_ones.push_back(count_of_ones[0]+count_of_ones[count_of_ones.size()-1]);
                
                last_count_of_ones=count_of_ones[count_of_ones.size()-1];
               
                for(int i=n-1;i>=0;i--)
                {
                    if(start_ind_count_ones[i]!=0)
                        {start_ind_count_ones[i]=count_of_ones[count_of_ones.size()-1];break;}
                }
            }
    
    
            sort(count_of_ones.begin(),count_of_ones.end(),compa); 
    
    
    
    
            for(int i=0;i<n;i++)
            {
                if(start_ind_count_ones[i]==count_of_ones[0])
                {
                    highest_1_start_ind=i;
                    highest_1_end_ind=(start_ind_count_ones[i]+i-1)%n; 
                }
                else if( count_of_ones.size()>=1 && start_ind_count_ones[i]==count_of_ones[1])
                {
                    highest_2_start_ind=i;
                    highest_2_end_ind=(start_ind_count_ones[i]+i-1)%n;
                }
            }
    
    
           int pointer_for_rotation=0;
            for(int i=0;i<q;i++)
            {
                if(query_string[i]=='!')
                {
                    pointer_for_rotation--;
                    if(pointer_for_rotation<0)
                        pointer_for_rotation=n-1;
                }
                else
                {
                    int max1a=count_of_ones[0],max1b=0,max2a=count_of_ones[1],max2b=0;
                 
                   if(pointer_for_rotation>=highest_1_start_ind && pointer_for_rotation<=highest_1_end_ind)
                    {
                        max1a=highest_1_end_ind-pointer_for_rotation+1;
                        max1b=count_of_ones[0]-max1a;
                    }
                    if(pointer_for_rotation>=highest_2_start_ind && pointer_for_rotation<=highest_2_end_ind)
                    {
                        max2a=highest_2_end_ind-pointer_for_rotation+1;
                        if(count_of_ones.size()>=1)
                            max2b=count_of_ones[1]-max2a;    
                    }
    
    
                    if(highest_1_start_ind>highest_1_end_ind && pointer_for_rotation<=highest_1_end_ind) 
                    {
                        max1a=highest_1_end_ind-pointer_for_rotation+1;
                        max1b=count_of_ones[0]-max1a;
                    }
                    if(highest_2_start_ind>highest_2_end_ind && pointer_for_rotation<=highest_2_end_ind)
                    {
                        max2a=highest_2_end_ind-pointer_for_rotation+1;
                        if(count_of_ones.size()>=1)
                            max2b=count_of_ones[1]-max2a;
                    }
                    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";  
    
    
                }
            }
    
    
        return 0;
    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Where's your example data?
    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.

  3. #3
    Registered User
    Join Date
    Nov 2018
    Posts
    32
    example testcase:
    5 5 3
    1 1 0 1 1
    ?!?!?
    output:
    2
    3
    3

    The test cases that got segmentation error are not shown,
    I took a random input of n= 10^5 elements and queries= 10^5
    It didn't show seg fault...

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    10^5 is an awful lot of guessing to come up with something which may or may not crash.
    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.

  5. #5
    Registered User
    Join Date
    May 2010
    Posts
    4,633
    The test cases that got segmentation error are not shown,
    The what good is the test case shown if it doesn't illustrate the problem. By the way what is your expected output with that input?

  6. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    What about input of all 1's or all 0's or 10101010... ?

    Your code is very complicated. I'll see if I can come up with something, not a whole solution but just finding the two largest streaks (including possible wraparound). Maybe it's more complicated than I think.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  7. #7
    Registered User
    Join Date
    Nov 2018
    Posts
    32
    I have checked with all 0s all 1s and 101010 , it works fine with all in my personal IDE, but shows SIGSEGV error on online one

  8. #8
    Registered User
    Join Date
    Nov 2018
    Posts
    32
    2
    3
    3 is the expected output..

  9. #9
    Registered User
    Join Date
    Nov 2018
    Posts
    32
    What I meant to say is that this could handle large inputs, but don't know if I am going out of bounds somewhere, or something like that ??

  10. #10
    Registered User
    Join Date
    May 2010
    Posts
    4,633
    is the expected output..
    Does that match with your actual output?

    What I meant to say is that this could handle large inputs, but don't know if I am going out of bounds somewhere, or something like that ??
    You say you're problem is a "segmentation fault" so show the input when you got the segmentation fault, not something that appears to be working.

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by jimblumberg View Post
    Does that match with your actual output?


    You say you're problem is a "segmentation fault" so show the input when you got the segmentation fault, not something that appears to be working.
    For these contest problems, you don't see the actual input your program is tested against (otherwise you could just print the right answers), so OP doesn't have the actual input.

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You don't need to write your own version of operator>, really.

    The loop at line 57 (as posted) can walk off the end of the array.

  13. #13
    Registered User
    Join Date
    Nov 2018
    Posts
    32
    I found the error its in the while loop
    while(arr[i]==1) //should contain i<n, Still am getting some correct testcases, some wrong, there is still something wrong(with my implementation)

  14. #14
    Registered User
    Join Date
    Nov 2018
    Posts
    32
    @tabstop, lol, yes thats correct, I finally got down and learned how to use a debugger, it helped.
    Still my code is giving some testcases as wrong and some correct...

  15. #15
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    This takes input n (number of bits) and then the n bits (separated by spaces). It prints the beginning position and length of the largest and second largest run's of 1's, incuding a run that "wraps" around from the end to the beginning (which would end up having position + length >= n).

    It still seems more complicated than necessary! (Although the Record object is mostly boilerplate and is totally basic.)
    Code:
    #include <iostream>
    using std::cout;
    using std::cin;
     
    struct Record {
        int pos, len;
     
        Record(int p=0, int n=0) : pos(p), len(n) {}
        void set(int p=0, int n=0) { pos = p; len = n; }
     
        Record& operator++() { ++len; return *this; }
        Record operator+=(const Record& rhs) { len += rhs.len; return *this; }
     
        operator bool()  { return len > 0; }
        bool operator!() { return len <= 0; }
        bool operator>(const Record& rhs) { return len > rhs.len; }
     
        friend std::ostream& operator<<(std::ostream& os, const Record& r) {
            return os << '[' << r.pos << ',' << r.len << ']';
        }
    };
     
    void place(Record& cur, Record& a, Record& b) { // Places cur into a, b
        if      (cur > a) { b = a; a = cur; }
        else if (cur > b) b = cur;
        cur.set(); // reset cur
    }
     
    int main() {
        int n = 0; // length of input sequence
        cin >> n;
     
        // Read initial bits. "Placing" of an initial run is deferred
        // as it may need to be added to a terminal run.
        int i = 0, bit = 1;
        for ( ; i < n && bit; ++i)
            cin >> bit;
     
        // Initial run length is usually i - 1 unless the sequence
        // was all 1's, in which case bit will be 1 instead of 0 here.
        Record a, b, cur, init(0, i - !bit);
     
        for ( ; i < n; ++i) {
            cin >> bit;
            if (bit) {
                if (!cur)       // beginning of a run
                    cur.set(i); //    so save start position
                ++cur;          // increment length
            }
            else if (cur)
                place(cur, a, b);
        }
     
        if (init) {            // If we have an initial run
            if (cur)           //   and also a terminal run
                cur += init;   //     add them together
            else
                place(init, a, b); // otherwise, process initial run normally
        }
     
        if (cur)
            place(cur, a, b); // process terminal run
     
        cout << a << " : " << b << '\n';
    }
    Anyway, if your's is finding the streaks properly then you probably aren't interested in it. But it does demonstrate that it can be done more simply.

    I've thought of some points about k:

    If there was only a single streak of 1's (b.len == 0) then the answer for all queries is min(a.len, k)

    Otherwise if a.len and b.len are both >= k then the answer for all queries is k

    Otherwise, if a.len == b.len, then the answer for all queries is min(a.len, k)

    Otherwise you need to process the queries.
    For each query:
    * if the current "first" element doesn't split a then the answer is min(a.len, k)
    * otherwise the answer is either one of the a's parts, or b (or k, of course).
    A little inaccuracy saves tons of explanation. - H.H. Munro

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