Lesson 5: Fish (Fish)

Lesson 5: Fish
https://codility.com/programmers/lessons/5

The simplest solution for this problem is to use the stack.
We prepare a stack only for those fish going downstream.

The arrays of the fish size/direction are scanned from the beginning to the end. 

If the fish at the current scanning position is going downstream, we put it onto the stack. 

When the fish at the current position is going upstream, it starts eating up the fish going downstream from the stack. If it mets a bigger fish than itself, it dies then. If there is no more fish on the stack, it means it can reach the upper end of the river. This means it survives. We count up the surviver counter.

The total number of the survived fish is the survivors (heading upstream) and those on the stack (heading downstream).

This solution gives the 100% score as below.

#include <alloca.h>

int solution(int A[], int B[], int N) 
{
    int memsize = sizeof(int) * N;

    //stack (memory & index)
    int* down   = (int*)alloca(memsize);
    
    int d = 0;

    //the counter for the fish that reached to the end of the river.    
    int cnt_reached = 0;

    int i;
    for (i = 0; i < N; i++){        
        
        //if the fish is going upstream,
        //check if it can reach the upper end.
        if (B[i] == 0){
            while(1){
                //if there is no more fish against it,
                //it reaches the upper end.
                if (d == 0){
                    cnt_reached++;
                    break;
                }
                //met a bigger one, they it is eaten..
                if (down[d - 1] > A[i]){
                    break;
                }
                //we keep on eating the fish...
                d--;
            }
            continue;
        }
        //the fish is going downstream. push it to the stack.
        down[d] = A[i];
        d++;
    }
    
    return cnt_reached + d;
}