0

Problem Statement

Mark is an undergraduate student and he is interested in rotation. A conveyor belt competition is going on in the town which Mark wants to win. In the competition, there's A conveyor belt which can be represented as a strip of 1xN blocks. Each block has a number written on it. The belt keeps rotating in such a way that after each rotation, each block is shifted to left of it and the first block goes to last position.

There is a switch near the conveyer belt which can stop the belt. Each participant would be given a single chance to stop the belt and his PMEAN would be calculated.

PMEAN is calculated using the sequence which is there on the belt when it stops. The participant having highest PMEAN is the winner. There can be multiple winners.

Mark wants to be among the winners. What PMEAN he should try to get which guarantees him to be the winner.

Definitions

  • PMEAN = (Summation over i = 1 to n) (i * i th number in the list) where i is the index of a block at the conveyor belt when it is stopped. Indexing starts from 1.

Input Format

  • First line contains N denoting the number of elements on the belt.
  • Second line contains N space separated integers.

Output Format

  • Output the required PMEAN

Constraints

  • 1 ≤ N ≤ 10^6
  • -10^9 ≤ each number ≤ 10^9

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main (void)
{
    int n;
    cin>>n;
    vector <int> foo;
    int i = 0,j = 0,k,temp,fal,garb=0;
    while (i < n)
    {
        cin>>fal;
        foo.push_back(fal);
        i++;

    }
    vector<int> arr;
    //arr.reserve(10000);
    for ( i = 0; i < n; i++ )
    {
        garb = i+1;
        arr.push_back(garb);    
    }
    long long product = 0;
    long long bar = 0;

    while (j < n)
    {
        i = 0;
        temp = foo[0];
        while ( i < n-1 )
        {
            foo[i] = foo[i+1];
            i++;
        }
        foo[i] = temp;
        for (  k = 0; k < n; k++ )
            bar = bar + arr[k]*foo[k];    

        if ( bar > product )
            product = bar;    

        j++;
    }
    return 0;

}

My Question:

What I am doing is basically trying out different combinations of the original array and then multiplying it with the array containing the values 1 2 3 ...... and then returning the maximum value. However, I am getting a segmentation fault in this.

Why is that happening?

user3776323
  • 43
  • 6
  • 5
    You're indexing beyond the bounds of the vectors. Use `push_back` to add new elements, instead of using `operator[]`. Also, try using a debugger. – Praetorian Aug 12 '14 at 18:27
  • 3
    for future reference, valgrind is an awesome tool for debugging segfaults and memory leaks – davidicus Aug 12 '14 at 18:31

1 Answers1

3

Here's some of your code: 

vector <int> foo;
int i = 0;
while (i < n)
{
    cin >> fal;
    foo[i] = fal;
    i++;
}

When you do foo[0] = fal, you cause undefined behavior. There's no room in foo for [0] yet. You probably want to use std::vector::push_back() instead.

This same issue also occurs when you work on vector<int> arr;

And just as an aside, people will normally write that loop using a for-loop:

for (int i=0; i<n; i++) {
    int fal;
    cin >> fal;
    foo.push_back(fal);
}

With regards to the updated code:

  • You never increment i in the first loop.
  • garb is never initialized.
Community
  • 1
  • 1
Bill Lynch
  • 80,138
  • 16
  • 128
  • 173
  • If I would have used the `reserve space` command, then would have I been able to do it directly? – user3776323 Aug 12 '14 at 18:42
  • @user3776323: No. See this post for an explanation: http://stackoverflow.com/questions/13029299/stdvectorresize-vs-stdvectorreserve – Bill Lynch Aug 12 '14 at 18:43
  • Also, even after using push_back, it shows the error now as, `terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc Aborted (core dumped)` – user3776323 Aug 12 '14 at 18:48
  • Without seeing the exact code that you're running, it will be very difficult for me to guess where that error is coming from. – Bill Lynch Aug 12 '14 at 18:58
  • You never increment `i` in the first loop. `garb` is never initialized. – Bill Lynch Aug 12 '14 at 19:03