parash93's blog

By parash93, history, 10 years ago, In English

Can someone list some matrix-implementation type problems? I really find myself unable to solve them. Please note that I am not referring to the DP problems involving Matrices.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By parash93, 10 years ago, In English

I found out the max sum subarray. The elements included in this list should be added to Ans (I am assuming that we placed '(' one element before the maxsumsubarray started, and we placed ')' after the last element of maxsumsubarray) Now subtract the elements which weren't included in this subarray, except the first element of the vector, which has to be added.

This doesn't work for sample test case 4: [{-11,-4,28,38,21,-29,-45,11,-58,-39,92,35,-56,-6,29,-2,61,10,-29,-63},{19,5,3,10,4,18,5,2,0,15},{-19,21,7,-66,38,-39,-22,24,-32,13}]

Can anyone explain why? Moreover, what is the correct way to solve this question?

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
vector<int> poss;
vector<int> pose;
int myposs,mypose;

int maxsum(vector<int> a)
{
    int i,n=(int)a.size(),sc;
    vector<int> S(a.begin(),a.end());
    poss.clear();
    pose.clear();
    
    for(i=0;i<n;i++)
    {
        poss.push_back(i);
        pose.push_back(i);
    }
    for(i=3;i<n;i++)
    {
        if(S[i]<S[i-1]+S[i])
        {
            S[i]=S[i-1]+S[i];
            poss[i]=poss[i-1];
        }
    }
    
    int m=INT_MIN;
    for(i=2;i<n;i++)
    {
        if(S[i]>m)
        {
            myposs=poss[i];
            mypose=pose[i];
            m = S[i];
        }
    }
    
    int j;
    
    if(!(myposs==0 && mypose==n-1))
    {
        if(myposs!=0)
            m=m+a[0];
        
        for(j=1;j<myposs;j++)
            m=m-a[j];
        
        for(j=mypose+1;j<n;j++)
            m=m-a[j];
        
    }

    
    int s = 0;
    
    for(i=0;i<n;i++)
    {
        if(i==0)
            s=s+a[i];
        else
            s = s-a[i];
    }
    
    if(s>m)
    {
        myposs=0;
        mypose=n-1;
        return s;
    }
    
    else
        return m;
}
class SuccessiveSubtraction2 {
public:
    vector <int> calc(vector <int> a, vector <int> p, vector <int> v) {
        
        int i,s,j,n=(int)a.size();
        vector<int> ans;
        
        for(i=0;i<(int)p.size();i++)
        {
            a[p[i]]=v[i];
            s=0;

            s = maxsum(a);
            
            ans.push_back(s);
        }
        
        return ans;
        
    }
};


http://community.topcoder.com/stat?c=problem_statement&pm=13699&rd=16318

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By parash93, 10 years ago, In English

How do we approach problems where while minimising the path from Source to Destination, we even have to keep the time of travel below a certain value? I am referring to problems such as FISHER: SPOJ

I saw a tutorial on this on TopCoder in the upper intermediate section, for using dijsktra's with another state, but couldn't really understand how to implement it.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it