Run time Error on URI Online Judge

Question

I am trying the following problem on URI OJ

After buying many adjacent farms at the west region of Santa Catarina, the Star family built a single road which passes by all farms in sequence. The first farm of the sequence was named Star 1, the second Star 2, and so on. However, the brother who lives in Star 1 has got mad and decided to make a Star Trek in order to steal sheep from the proprieties of his siblings. But he is definitely crazy. When passes by the farm Star i, he steals only one sheep (if there is any) from that farm and moves on either to Star i + 1 or Star i - 1, depending on whether the number of sheep in Star i was, respectively, odd or even. If there is not the Star to which he wants to go, he halts his trek. The mad brother starts his Star Trek in Star 1, stealing a sheep from his own farm.

INPUT

The first input line consists of a single integer N (1 ≤ N ≤ 106), which represents the number of Stars. The second input line consists of N integers, such that the ith integer, Xi (1 ≤ Xi ≤ 10^6), represents the initial number of sheep in Star i.

OUTPUT

Output a line containing two integers, so that the first represents the number of Stars attacked by the mad brother and the second represents the total number of non-stolen sheep.

I tried to solve the following problem using Brute Force. But every time I submit, I am receiving a Command terminated by signal (11: SIGSEGV). As I searched this error occurs when we are trying to access a memory segment that does not exist, so what can I do to improve my code, and where is the error actually occurring. I tried looking up and came up with the fact the we can have a python list of size 536870912 safely, so I am guessing 10^6 being much smaller than this is also safe.

n = int(raw_input())
x = map(int, raw_input().split())
total, i, stolen, visited = sum(x), 0, 0, set()
while i in range(n) and x[i]:
    visited.add(i)
    stolen += 1
    x[i] -= 1
    if (x[i] + 1) % 2 == 1:
        i += 1
    else:
        i -= 1
print(str(len(visited)) + ' ' + str(total - stolen))

Max Size of Python List

Here are sample runs of my program

INPUT

8
1 3 5 7 11 13 17 19

EXPECTED OUTPUT

8 68

OUTPUT

8 68

INPUT

8
1 3 5 7 11 13 16 19

EXPECTED OUTPUT

7 63

OUTPUT

7 63

Answer 1

I don't know Python so I cannot help finding the bug, but I think your algorithm is buggy.

The problem says:

If there is not the Star to which he wants to go, he halts his trek.

However it seems that your algorithm also stops if there is no sheep left on a farm.

Anyway the problem looks quite simple in the form as you inserted so I think that the range of the first parameter is NOT

(1 ≤ N ≤ 106)

but rather

(1 ≤ N ≤ 10⁶)

In this case the size of the list could be a problem... especially if they limit the available memory for the code.

But actually you don't need to store all the input parameters! You can calculate the stolen sheep quite easily on the fly:

1. You start from the first farm.

2.1. If there are even number of sheep here then none of the following farms will be visited and 1 sheep will be stolen from here.

2.2. If there are odd number of sheep here then 1 sheep will be stolen right now, and 1 more when the mad star comes back (At that time there will be even number of sheep here and also in all of the previous farms so the mad start won't visit it any more.) We also have to handle the case when there is only one sheep at the farm because in this case only 1 sheep can be stolen here.

3. Handle the next farm

At the end you have to handle one more special case: If there were even number of sheep in each of the farms then exactly 1 sheep was stolen from each farm, because in this case the mad star never turns back. (And there is at least one sheep in each farm)

Here is a simple algorithm as a pseudo code:

int N= read();
boolean visit = true;
int visited = 0;
int total = 0;
int stolen = 0;
while(--N >0 ) {
  int x = read();
  total+=x;
  if(visit) {
    visited++;
    if(x%2 == 1) {
      stolen+=min(x,2);
    } else {
      stolen+=1;
      visit = false;
    }
  }
}
if(visit) {
  print(N + ' ' = (total-N));
} else {
  print(visited + ' ' + (total-stolen));
}