Algorithm : 1D Maxsum (Kadane algorithm with resulted sequence size >= 1)

// Written by Kevin C. Wong
// @JEngineTeam 2/9/2012

// This function is designed to solve uva108 maximum sum problem with dynamically programming.
// You can extend this to solve the 2D array in O(n^3).

//    http://acm.uva.es/p/v1/108.html 

// The original Kadane algorithm will return empty sequence if all array values are negative.
// We just return a sequence with single min value.

#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;


int max1d(int a[], int n, int &x1, int &x2)
{
    int max=0;
    int umax=a[0],ui=-1;
    int here=0;
    int c=0;
    x1=x2=-1;
    rep(i,0,n-1)
    {
        if(a[i]>=umax){umax=a[i];ui=i;};
        c+=a[i];
        if(c<0){here=i+1;c=0;};
        if(c>max){max=c;x1=here;x2=i;};
    }
    if(x1==-1){x1=ui;x2=ui;return umax;}
    return max;
}

My UVA 100 3n+1 Problem solution

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36





#include<iostream>


#define rep(i,a,b) for(int i=a;i<=b;i++)


using namespace std;


long trace2(long n)
{
    if(n<=1)return 1;
    
    long next1;
    if(n%2==0)
      next1=n/2;
    else
      next1=3*n+1;
    
    return trace2(next1)+1;
}


int main(int argc, char *argv[])
{
    int I=0,J=0,R=0;
    while(cin>>I>>J)
    {
        long t,max=0;
        if(I<J)
        {
            rep(i,I,J)
            {
                t=trace2(i);
                if(t>max){max=t;}
            }
        }
        else
        {
            rep(i,J,I)
            {
                t=trace2(i);
                if(t>max){max=t;}
            }
        }
        cout<<I<<" "<<J<<" "<<max<<endl;
    }
    return 0;
};

My UVA 394 MapMaker Solution

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=330


#include <iostream>
#include <fstream>
#include <vector>


using namespace std;


int main(int argc, char** arg)
{
    int N,R;
    cin>>N>>R;


    vector<string> name(N);
    long B[N];
    int size[N];
    long D[N];
    vector<long> upper[N];
    vector<long> lower[N];


    for(int i=0;i<N;i++)
    {
      cin>>name[i];
      cin>>B[i];
      cin>>size[i];
      cin>>D[i];
      upper[i].assign(D[i]+1,0l);
      lower[i].assign(D[i]+1,0l);
      for(int j=1;j<=D[i];j++)
      {
        cin>>lower[i][j]>>upper[i][j];
      }
    }
/*
    for(int i=0;i<N;i++)
    {
      cout<<name[i]<<endl;
      cout<<B[i]<<endl;
      cout<<size[i]<<endl;
      cout<<D[i]<<endl;
      for(int j=1;j<=D[i];j++)
      {
        cout<<lower[i][j]<<","<<upper[i][j]<<endl;
      }
    }
*/
    vector<long> cD[R];
    vector<string> cname(R);
    int cidx[R];


    for(int i=0;i<R;i++)
    {
      cin>>cname[i];
      cidx[i]=-1;
      for(int i2=0;i2<N;i2++)
        if(cname[i].compare(name[i2])==0)
          {cidx[i]=i2;break;}
      if(cidx[i]>=0)
      {
            cD[i].assign(D[cidx[i]]+1,0l);
            for(int i2=1;i2<=D[cidx[i]];i2++)
            {
                cin>>cD[i][i2];
            }
      }
    }


/*
    for(int i=0;i<R;i++)
    {
      cout<<cname[i]<<endl;
      cout<<cidx[i]<<endl;
      for(int i2=1;i2<=D[cidx[i]];i2++)
            cout<<cD[i][i2]<<",";
      cout<<endl;
    }
*/
    vector<long> cC[R];


    // main part
    for(int i=0;i<R;i++)
    {
      if(cidx[i]>=0&&cidx[i]<N)
      {
          cC[i].assign(D[cidx[i]]+1,0l);
          cC[i][D[cidx[i]]]=size[cidx[i]];
          for(int d=D[cidx[i]]-1;d>=1;d--)
          {
            cC[i][d]=cC[i][d+1]*(upper[cidx[i]][d+1]-lower[cidx[i]][d+1]+1);
          }


          cC[i][0]=B[cidx[i]];
          for(int d=D[cidx[i]];d>=1;d--)
            cC[i][0]-=lower[cidx[i]][d]*cC[i][d];
          long res=cC[i][0];
          for(int i2=1l;i2<=D[cidx[i]];i2++)
            res+=(cC[i][i2]*cD[i][i2]);


          cout<<cname[i]<<"[";
          for(int i2=1;i2<=D[cidx[i]];i2++)
          {
            if(i2!=1)
              cout<<", ";
            cout<<cD[i][i2];
          }
          cout<<"] = "<<res<<endl;
      }
    }


    return 0;
}

Algorithm: Convert large integer from any base to any base.

// Written by Kevin C. Wong
// @JEngineTeam 2/9/2012


// 2-64 Base conversion: from any to any.
// You can increase the base more than 64 by appending m
// ore various characters to the lookup string


#include <iostream>
#include <vector>


#define rep(i,a,b) for(int i=a;i<=b;i++)
#define drep(i,a,b) for(int i=a;i>=b;i--)


using namespace std;


string lookup="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz@_";


string convert(string s,int x, int y)
{
    if(x<=1||x>64)return "error";
    if(y<=1||y>64)return "error";
    if(s.compare("0")==0)return"0";
    int l=s.length();
    if(l==0)return"";    
    int ca=(int)lookup.find(s[l-1]);
    string b=convert(s.substr(0,l-1),x,y);
    int i=b.length()-1;
    
    string t;
    while(i>=0||ca>0)
    {
        int v=ca;
        if(i>=0)
        {
            v+=lookup.find(b.at(i))*x;
        }
        t=lookup[v%y]+t;
        ca=(int)(v/y);
        i--;
    }
  return t;   
}


int main(int argc, char** arg)
{
    cout<<convert("1A5A7A902342734022348904583904829045760724907593",12,12)<<endl;
    cout<<convert("1A5A7A902342734022348904583904829045760724907593",12,5)<<endl;
    cout<<convert("4312311240132203424023310434144444444224420004343440124243024330432321104",5,5)<<endl;
    cout<<convert("4312311240132203424023310434144444444224420004343440124243024330432321104",5,12)<<endl;
    cout<<convert("1",7,19)<<endl;
    cout<<convert("2",10,2)<<endl;
    cout<<convert("0000000",7,19)<<endl;
    cout<<convert("5",7,1)<<endl;
    return 0;
}

My Solution to Top Coder SRM 531 : Non RepeatPlayList

Problem:

http://community.topcoder.com/stat?c=problem_statement&pm=11774&rd=14724

My Solution:

There are two rules for a valid playlist

1 - At least M songs have to be played between any two occurrences of the same song. 

2 - Every songs at least played once.

Firstly, let us just consider the first rule.

1. If we list out all invalid and valid arrangements, they can be show in a big searching tree:

    

2. If the parent break the 1st rule, so as its children.

3. If a i-th layer node has more than M-1 ancestors, a valid node just can have N-M choices in next branch, so it will have N-M children.

Algorithm

Let us define DP[i] as following

DP[i]=numbers of leaves(playlists) in i-th layer.

DP[0]=1;

==>DP[i+1]=  DP[i]*(N-i) where i < M 

                 DP[i]*(N-M)     where i>=M

==>DP[i+1]=  DP[i]*(max(N-i,N-M)) 

==>DP[i]=  DP[i-1]*(max(N-i+1,N-M)) 

where 1<M<N<P<=100

====================================================

Now, let us consider the problem with both first and second rules.

1. Define rule2(N) = it is true when all songs 1....N have been played once.

2. If the parent meets rule2(N), so as its children.
    i.e. If a playlist uses N songs, it will be the same as it is longer.

3. If a playlist meets rule2(N-1), it must not meet rule2(N)

    i.e. If a playlist just uses N-1 songs, this playlist cannot use other songs.

4. If the parent meets rule2(j), only (N-j) choice of its children meet rule2(j+1).

    i.e. If a playlist is using j songs, the only way to make this playlist using j+1 songs is:
         Add a new song which is not belong to 1...j.
         And you can have N-j choices in this case.

Let us define DP[i][j] as following

DP[i][j] = # of playlist in ith layer (play list length=i), if we just consider j songs (1....j)

                  and the playlist meet the rules 1(non-repeat in last m song) 
                                                         and rule2(j)=(Just j songs are picked). 

DP[i][j] in i-th layer is contributed by the values of two types of playlist in its upper layer, (i-1)th layer.

Type 1 : Playlists has been counted in DP[i-1][N-1] but not counted in DP[i-1][N]


- This playlist meet Rule2(N-1), but must not meet Rule2(N).

   so, no playlist exist in both DP[i-1][N] and DP[i-1][N-1]

- If we want next level playlist meet Rule2(N),  there are only (1) choice on the song.

   That mean only one child for this node in layer (i-1)th.

- In general, there will be N-(j-1) choices for a new song in order to make this playlist meet rule2(j) .

==> DP[i][j] +=  DP[i-1][j-1]*(N-j+1)

Type 2 : Playlists were counted in DP[i-1][N]

All playlists have been counted in DP[i-1][N] meet rule 1 and 2.

5. If the parent meet the 2nd rule, so as its children.

6. If the parent break the 1st rule, so as its children.
==> If the parent keep the 1st rule, there should be N-M choices for a child to pick a new song  in order to keep rule1.
In general, there should be j-M choices for a playlist in D[i-1][j]

But please also notice that if(j<M), this playlist will fail to meet rule 2(M). (j songs are not enough.) 

==> DP[i][j] +=  DP[i-1][j]*(max(j-M,0))

Examples
N=50,M=5,P=100
1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,50,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,2450,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,117600,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,(i<j zero area)0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,5527200,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,254251200,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,417372479,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,252117430,947016478,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,921607339,682098833,774691803,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,260587143,675411789,746917981,762363706,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,938546765,231482425,354966845,435455513,494548030,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
(j<M zero area)
0,0,0,0,0,0,441303923,294465995,51957883,142129153,730918098,385508560,287373037,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,6304462,817911350,750747684,481885700,549775063,46444980,920175336,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,429981403,724825902,355267177,190083313,574078224,766342170,126311865,46487194,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,441303923,277335278,663677895,863756375,516370717,47801787,753445737,131497170,91923716,673538977,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
... <truncated> 

Hence, the C++ code will be:




#define rep(i,a,b) for(int i=a;i<=b;i++)
#define MOD 1000000007
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))


#include <iostream>
using namespace std;


class NoRepeatPlaylist
{
  public:
  int numPlaylists(int n,int m,int p)
  {
  ll dp[102][102];
  rep(i,0,101)rep(j,0,101)dp[i][j]=0;
dp[0][0]=1;
rep(i,1,p)
{
          rep(j,1,n)
 {
   dp[i][j]=(dp[i-1][j]*max(j-m,0)+dp[i-1][j-1]*(n-j+1))%MOD;
   }
  }
  return (int)dp[p][n];
  };
};