Ronzii's Blog

Just your average geek's blog

Circular Track Problem

You have a circular track containing fuel pits at irregular intervals. The total amount of fuel available from all the pits together is just sufficient to travel round the track and finish where you started. Given the the circuit perimeter, list of each fuel pit location and the amount of fuel they contain, find the optimal start point on the track such that you never run out of fuel and complete circuit.

#include <iostream>
using namespace std;
int circularTrackIndex(int dist[], int refill[],int n)
{
    if(n==0) return -1;
    int fuel = 0, start=0;
    for(int i=0; i<n; i++)
    {
        fuel+=refill[i]-dist[i];
        if(fuel<0)
        {
            start = i+1;
            fuel = 0;
        }
    }
    return start;
}
int main()
{
    // dist[i] is distance between pit i and i +1
    int dist[] = { 3, 10, 2, 4, 6, 9};
    // refill[i] is fuel available at pit[i]
    int refill[] = { 3, 4, 6, 3, 7, 11};
    int n = sizeof(refill)/sizeof(refill[0]);
    cout<<circularTrackIndex(dist,refill,n);
    return 0;
}
Advertisements

March 22, 2012 Posted by | C++, Dynamic Programming | , , , , | Leave a comment

Maximum Sum Submatrix

Method 1 : 

This is in O(n^4) using dynamic programming. A huge improvement over the naive o(n^6), where the complexity to calculate the sum of a sub matrix was O(n^2). This time has been reduced to O(1) using DP.

#include <iostream>
#include <climits>
#define N 3
using namespace std;
int sumMatrix[N][N];
void preComputeMatrix(int a[][N])
{
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
        {
            if(i==0 && j==0)
                sumMatrix[i][j] = a[i][j];
            else if(i==0)
                sumMatrix[i][j]+=sumMatrix[i][j-1] + a[i][j];
            else if(j==0)
                sumMatrix[i][j]+=sumMatrix[i-1][j] + a[i][j];
            else
                sumMatrix[i][j]+=sumMatrix[i-1][j]+sumMatrix[i][j-1]-sumMatrix[i-1][j-1] + a[i][j];
        }
    }
}
int computeSum(int a[][N],int i1,int i2,int j1,int j2)
{
    if(i1==0 && j1==0)
        return sumMatrix[i2][j2];
    else if(i1==0)
        return sumMatrix[i2][j2] - sumMatrix[i2][j1-1];
    else if(j1==0)
        return sumMatrix[i2][j2] - sumMatrix[i1-1][j2];
    else
        return sumMatrix[i2][j2] - sumMatrix[i2][j1-1]- sumMatrix[i1-1][j2] + sumMatrix[i1-1][j1-1];
}
int getMaxMatrix(int a[][N])
{
    int maxSum = INT_MIN;
    for(int row1=0; row1<N; row1++)
    {
        for(int row2=row1; row2<N; row2++)
        {
            for(int col1=0; col1<N; col1++)
            {
                for(int col2=col1; col2<N; col2++)
                {
                    maxSum = max(maxSum,computeSum(a,row1,row2,col1,col2));
                }
            }
        }
    }
    return maxSum;
}
int main( void )
{
    int a[N][N] = {{-1,-2,-3},{-10,-5,-15},{6,-8,-20}};
    preComputeMatrix(a);
    for(int i=0; i<N; i++)
    {
        for(int j=0; j<N; j++)
            cout<<sumMatrix[i][j]<<" ";
        cout<<endl;
    }
    cout<<getMaxMatrix(a);
    return 0;
}

Method 2
Kadane’s Algorithm 2D. Overall complexity is O(n^3)
Check out http://www.algorithmist.com/index.php/UVa_108 for the algorithm

#include <iostream>
#include <climits>
using namespace std;
int a[101][101];
int kadane2D(int n)
{
    int *columnSum = new int[n];
    int s=INT_MIN,S=INT_MIN,t;
    for(int row = 0; row<n; row++)
    {
        for(int i=0; i<n; i++) columnSum[i] = 0;
        for(int x = row; x<n; x++)
        {
            s = INT_MIN;
            t = 0;
            for(int i=0; i<n; i++)
            {
                columnSum[i]+=a[x][i];
                t+=columnSum[i];
                if(t>s)
                    s = t;
                if(t<0)
                    t = 0;
            }
            if(s>S)
                S = s;
        }
    }
    delete [] columnSum;
    return S;
}
int main( void )
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>a[i][j];
        }
    }
    cout<<kadane2D(n)<<endl;
    return 0;
}

March 16, 2012 Posted by | C++, Dynamic Programming | , , , , , , , | Leave a comment