Uva 307 – Sticks

Category : Recursion + Pruning
Link : 307 – Sticks
Solution:

Observation:
1. The length must divide the total Length.Lets sum = summation of all length. So the answer should be a divisor of sum & at least >= max(Ai);
2. Normal Recursion without pruning will get TLE. To avoid TLE some technique (Standard) is used :

* Sort the array in descending order. This helps to limit the depth of recursion. When we take a bigger number,than Our search space become 	smaller, so our choice become smaller.
* 
		dfs(ind,sum,cnt) => { ind = position of current element, sum = running sum, cnt = # of elements already taken. }

		if(vis[ind] == 0) // Not taken
		{
			//check if we can add this to our running sum
			if(sum + a[ind] < LIM ) { // This is pruning
				// We go to another state.
			}
			if(sum + a[ind] == LIM ) {
				// We take this element.
				// go to next state
			}
		}
*	Skipping same valued element. This is a great optimization. 

See my solution:

#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define xx                      first
#define yy                      second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))

/*************************** END OF TEMPLATE ****************************/

const int N = 104;
int n;
int a[N];
int LIM = 0;
int nxt[N];
bool vis[N];

bool dfs(int ind,int sum,int cnt)
{
    if(cnt==n) return 1;
    for(int i = ind ;  i < n; i ++) {
        if(vis[i] == 0) {
            if(sum + a[i] <  LIM) {
                vis[i] = 1;
                if(dfs(i+1,sum + a[i],cnt+1)) return 1;
                vis[i] = 0;
                if(sum==0)return 0; 
                /*
                 This line is very important. This denotes we don't take anything and taking the ith element 
                 we can not reach destinition. So there is no solution where we can take the ith element .So
                 We return */

                while(i+1<n&& a[i]==a[i+1])i++; // Skipping
            }
            if(sum + a[i] == LIM ) {
                vis[i] = 1;
                if(dfs(0,0,cnt+1)) return 1; // One round is over, Now check for another 
                vis[i] =0;
                return 0;
            }
        }
    }
    return 0;
}

int main()
{
    
    while(scanf("%d",&n)==1 && n) {
        int sum = 0, iM = 0;
        for(int i = 0; i < n; i ++) {
            scanf("%d",&a[i]);
            sum += a[i];
            iM = max(iM, a[i]);
        }
        sort(a,a+n);
        reverse(a,a+n);
        for(int i = iM; i <= sum ;i ++ ) {
            if(sum % i) continue;
            LIM = i;
            memset(vis,0,sizeof vis);
            bool k = dfs(0,0,0);
            if(k) {
                printf("%d\n",i);
                break;
            }
        }
    }
    return 0;
}

Uva 1600 – Patrol Robot

Category : DFS + Pruning
Link : Uva 1600 – Patrol Robot

Solution:
* Recursive Search
* We keep a parameter step which denotes how many consecutive step we have taken through obstacles.
* After finding an answer we resize our limit for shortest path and prune those paths.
* If taking the best condition( No obstacles) the length of the path from the current is greater than limit , then prune this path

#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define xx                      first
#define yy                      second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))

/*************************** END OF TEMPLATE ****************************/

const int N = 20;
bool flag = 0;
int r,c,k;
int LIM ;
bool VIS[N][N];
int dir[] [2] = {{0,1},{0,-1},{1,0},{-1,0}};
int a[N][N];
bool ok(int x,int y)
{
    if(x>=0&&x<r && y>=0&&y<c) return 1;
    return 0;
}
void dfs(int x,int y,int step,int lev)
{
    if(step>k)return;
    if(x==r-1 && y==c-1){
        flag = 1;
        LIM = lev; // Updating Search limit
        return;
    }
    int pp = abs(r-1-x) + abs(c-1-y); // length of the best possible path from current state
    if(lev + pp >= LIM ) return ; // Pruning paths which will never give optimal
    for(int i = 0; i < 4; i ++) {
        int xprime= x + dir[i][0];
        int yprime =y + dir[i][1];
        if(ok(xprime,yprime) && VIS[xprime][yprime] == 0) {
            VIS[xprime][yprime] = 1;
            if(a[xprime][yprime]) {
                dfs(xprime, yprime, step + 1, lev + 1);
            }
            else dfs(xprime,yprime,0,lev+1);
            VIS[xprime][yprime] = 0;
        }
    }
}
int main()
{
    int t;
    cin >> t;
    while(t-- ) {
        cin >> r >> c >> k;
        for(int i = 0; i < r; i ++ )
            for(int j = 0; j < c; j ++ )
                cin >> a[i][j];
        flag = 0;
        LIM = r*c;
        VIS[0][0]= 1;
        dfs(0,0,0,0);
        if(flag) printf("%d\n",LIM);
        else printf("-1\n");
    }
    return 0;
}

Uva 11882 – Biggest Number

Category : DFS + BFS + Prunning
Link : Uva 11882

Solution:
What we need to do ?
1. Make the length of number as large as possible.
2. If two string have same length then compare them and output the larger one.

1. The Problem is similar to finding longest path in general graph. So there is no polynomial time algorithm for finding this.
So we can recursively search for such path. But as grid has about 30 cells, recursive algorithm without optimisation fails.

Pruning :
Definition: VIS[x][y] => denotes if (x,y) is already visited or not
1. From a given cell,
count = { # of cells that are yet not visited and reachable from this cell}
If length (current answer) + count <length( previously found answer ) :
then then we will never get optimal answer here.
2. If length (current answer) + count <length( previously found answer ) :
then we check what is best we can generate. appending the reachable cell in descending order. Lets call the appended ans = temp;
If temp < previously founded answer :
Then return; // Cause no way I can make greater answer.

If trouble in understanding, Please see the implementation

#include<bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define forn(i,n)               for( int i=0 ; i < n ; i++ )
#define mp                      make_pair
#define pb                      push_back
#define all(x)                  (x).begin(),(x).end()
#define PI                      acos(-1.0)
#define EPS                     1e-9
#define xx                      first
#define yy                      second
#define lc                      ((n)<<1)
#define rc                      ((n)<<1|1)
#define db(x)                   cout << #x << " -> " << x << endl;
#define ms(ara_name,value)      memset(ara_name,value,sizeof(ara_name))

/*************************** END OF TEMPLATE ****************************/

const int N = 16;
char grid[16][16];
int dp[16][16][50];
int iM = 0;
bool vis[N][N];
int dir[][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int r,c;
string ans;
vector<char> pv;
bool isless(string a,string b)//compare two string
{
    if(a.size() < b.size()) return 1;
    if(a.size() == b.size() && a < b) return 1;
    return 0;
}
bool ok(int x,int y)//validity checking
{
    if(x>=0&&x<r&&y>=0&&y<c&& grid[x][y]!='#') return 1;
    return 0;
}

void bfs(int x,int y)// calculation of count, character stored in a vector
{
    int mark[N][N];
    memset(mark,0,sizeof mark);
    mark[x][y]= 1;
    queue<pair<int,int> > q;
    q.push(mp(x,y));
    pv.clear();
    while(!q.empty()) {
        auto u = q.front(); q.pop();
        for(int i = 0; i < 4; i ++ ) {
            auto v = mp(u.xx + dir[i][0] , u.yy + dir[i][1]);
            if(ok(v.xx, v.yy) && vis[v.xx][v.yy] == 0 && mark[v.xx][v.yy] == 0 ) {
                pv.push_back(grid[v.xx][v.yy]);
                mark[v.xx][v.yy] = 1;
                q.push(v);
            }
        }
    }
}
void dfs(int x,int y, string np)
{
    if(isless(ans,np)) {
        ans = np;
    }
    else {
        bfs(x,y);
        if(np.size() + pv.size() < ans.size()) return; 
        if(np.size() + pv.size() == ans.size()) {
            sort(all(pv));
            string g = np;
            for(int i = pv.size()-1; i>=0 ; i--) {
                g += pv[i]; // generating the best possible answer
            }
            if(isless(g,ans)) return ;
        }
    }
    // Recursive Search
    for(int i = 0; i < 4; i ++) {
        int xp = x + dir[i][0], yp = y + dir[i][1];
        if(ok(xp,yp) && vis[xp][yp] == 0) {
            vis[xp][yp] = 1;
            dfs(xp,yp,np + grid[xp][yp]);
            vis[xp][yp] = 0;
        }
    }
    
}
int main()
{
 
    while(scanf("%d %d",&r,&c)==2){
        if(r==0&&c==0) break;
        for(int i= 0;i<r;i++)scanf("%s",grid[i]);
        for(int i = 0; i < r; i ++ ) {
            for(int j = 0; j < c ; j ++) {
                if(grid[i][j] != '#') {
                    vis[i][j] = 1;
                    string t = "";
                    t+= grid[i][j];
                    dfs(i,j,t);
                    vis[i][j] = 0;
                }
            }
        }
        printf("%s\n",ans.c_str());
        ans.clear();
        memset(vis,0,sizeof vis);
    }
    return 0;
}