116 - Unidirectional TSP

[emotional blind]

Ok
think about fibonacci
a fibonacci series is like

Code: Select all

1 1 2 3 5 8 13 ...

Now if you trying to find n(th) fibonacci..
you may try recursion

Code: Select all

fib(int n){
      if(n==1||n==2)return 1;
      else return fib(n-1)+fib(n-2);
}

Here for fib(5)

Code: Select all

fib(5)=              fib(4)                          +                     fib(3)
          fib(4) =     fib(3)        +  fib(2)             fib(3)=fib(2)+fib(1)
                   fib(3)=fib(1)+fib(2)

the tree look like this

Code: Select all

                                     5
                                 /        \
                                4          3
                              /   \       /  \
                            3     2     2    1
                           / \
                          2  1

look at the tree
fib(3) calculated 2 times
fib(2) 3 times
fib(1) 2 times

these overlapping should be optimized by dp
see DP solution here using an array fib[n]

Code: Select all

fib[1]=fib[2]=1;
for(j=3;j<=n;j++)fib[j]=fib[j-1]+[j-2]

it is linear algorithm
do you understand this sample of DP approach?


OH yes you may visit here
http://online-judge.uva.es/board/viewtopic.php?t=10565
some more discussion is going there

[Beenuxers]

Hi, Arif... Thanks for ur sample and reference ... I can understand it... Now i'm gonna fix my code... Thx....

[Beenuxers]

I have changed my dp technique, so i got acc... What i don't realize so far is i do not need to trace the path one by one, i only need to store the minimum value for the path... And also i just realized that the dp table can help me to print the path... ^^.

[emotional blind]

Dont post your accepted code
it just spoils the program
so remove it immedieately
congaratulation for getting AC

[Beenuxers]

Ok... I've already removed my code... ^^.

[sangram]

Can anyone please tell me what can be wrong in my code ? I am not posting it here as it is already accepted ... but I got a presentation error.

Please help ! I want to know what the problem could be ?
For the test input given on the problem page, I seem to be getting the exactly same output.

[Dzhefri]

This, essentially, is my algorithm:

• Read data into a matrix (the data matrix)
  Create another matrix (the sum matrix), the last column of which is copied from the data matrix
  For each column (except the last) of the data matrix, starting from the last column:
  • For each element of that column:
    • Look at the corresponding position on the sum matrix, and then look at the 3 elements to the right (i.e., directly to the right, to the upper right, and the lower right). Select the lowest of these 3 values.
      Into the corresponding position of the sum matrix (i.e., the position to the left of the 3 elements mentioned above), write (element selected above + current data-matrix element)
  Select the element of the first column whose value is lowest, and return that.

Of course, it's slightly more complicated, because you have to keep track of the path that led to this minimum weight, but with all this taken into account, this algorithm is still O(n*m), (where m and n are the dimensions of the input) right? Why then do I always get TLE?? Here's my code:

Code: Select all

#include <iostream>
#include <vector>
#include <deque>
#include <map>
using namespace std;

struct path_sum {
	deque<int> path;
	int sum;
	path_sum(deque<int> p, int s): path(p), sum(s) {}
	path_sum(path_sum ps, int p, int s) {
		path = ps.path;
		sum = ps.sum;
		path.push_front(p);
		sum += s;
	}
	path_sum() {} //I had to add this because of line 61
};


//note that this would mess up if b is not positive
const int mod(int a, int b) {
	if (a >= 0) return a%b;
	else {
		a += b;
		return mod(a,b);
	}
}

int main() {
	int x, y;
	while (cin >> x) {
		cin >> y;
		vector<vector<int> > matrix;
		for (int i = 0; i < x; ++i) {
			vector<int> iv;
			for (int j = 0; j < y; ++j) {
				int temp;
				cin >> temp;
				iv.push_back(temp);
			}
			matrix.push_back(iv);
		}
		
		map<int, map<int, path_sum> > bp_matrix; //best path matrix, i.e., info on the best path from that element
		
		//initialize the last column of bp_matrix
		for (int i = 0; i < x; ++i) {
			deque<int> temp_id;
			temp_id.push_front(i);
			path_sum temp_ps(temp_id, matrix[i][y-1]);
			bp_matrix[i][y-1] = temp_ps;
		}
		
		//fill in the rest of bp_matrix
		for (int i = y - 2; i >= 0; --i) {//for each column
			for (int j = 0; j < x; ++j) { //for each element in each column
				//find the optimal element whose y is one more than this
				//and whose x is mod(+- 1 of this, x)
				int opt_elem = mod(j - 1, x); //i.e., the x coordinate of the presumed optimal element
											 //which we initialize with 1 less
				//comare the assumed opt_elem to the other two possibilities
				for (int k = 0; k <= 1; ++k) {
					if (bp_matrix[opt_elem][i+1].sum > bp_matrix[mod(j+k,x)][i+1].sum) {
						opt_elem = mod(j+k,x);
					} else if ((bp_matrix[opt_elem][i+1].sum == bp_matrix[mod(j+k,x)][i+1].sum) && (mod(j+k,x) < opt_elem)) {
						opt_elem = mod(j+k, x);
					}
				}
				
				path_sum temp_ps(bp_matrix[opt_elem][i+1], j, matrix[j][i]);
				bp_matrix[j][i] = temp_ps;
			}
		}
		
		//find the optimal path and report
		
		int opt_path = 0;
		for (int i = 1; i < x; ++i) {
			if (bp_matrix[i][0].sum < bp_matrix[opt_path][0].sum) {
				opt_path = i;
			}
		}
		
		for (int i = 0; i < bp_matrix[opt_path][0].path.size(); ++i) {
			cout << bp_matrix[opt_path][0].path[i]+1 << " ";
		}
		cout << endl << bp_matrix[opt_path][0].sum << endl;
	}
}
				
				

[ayeshapakhi]

anyone pls help me.......... i got several wa in 116...
i tried to solve it dynamically... by storing possible paths with respedtive costs and for paths i stored a parent array...
from the last column i traversed back for lexicografically smallest path...
my output is okay for all the inputs found in this board....
i cant find what i'm missing...
help pls.........
source code's here:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 105

typedef struct
{
	long in;
	long long val;
}
beta;

int comp(const void *a,const void *b)
{
	beta *x,*y;

	x=(beta *)a;
	y=(beta *)b;

	if( x->val == y->val) return (int)(x->in - y->in);
	return (int)(x->val - y->val);	
}
beta tt[3];
char min_path[N],temp[N];
long all_paths[N][N],end,r,c,count,point;
long long all[N][N],mat[N][N],pre[N][N],cost;
void print_path(long row,long col);

void main()
{
	//freopen("hati.txt","r",stdin);
	long i,j,k=0;

	while( scanf("%ld%ld",&r,&c) == 2)
	{
		if(k !=0) printf("\n");
		k++;
		for(i=0; i<r; i++)
			for(j=0; j<c; j++) scanf("%lld",&mat[i][j]);

		for(i=0; i<r; i++)
		{
			all[i][0]=mat[i][0];
			pre[i][0]=-1;
		}

		for(i=1; i<c; i++)
		{
			for(j=0; j<r; j++)
			{
				tt[0].in=(r+j-1)%r;
				tt[0].val=all[(r+j-1)%r][i-1];

				tt[1].in=j;
				tt[1].val=all[j][i-1];

				tt[2].in=(j+1)%r;
				tt[2].val=all[(j+1)%r][i-1];

				qsort(tt,3,sizeof(beta),comp);

				all[j][i]=mat[j][i]+ tt[0].val; 
				pre[j][i]=tt[0].in;
			}
		}
		cost=all[0][c-1];
		end=0;

		for(i=1; i<r; i++)
		{
			if( all[i][c-1] < cost )
			{
				cost=all[i][c-1];
				end=i;
			}
		}
		count=0;
		for(i=end; i<r; i++)
		{
			if( all[i][c-1] == cost)
			{
				print_path(i,c-1);
				count++;
			}
		}
		for(i=0; i<c; i++) min_path[i]=(char)(all_paths[0][i]+'0');
		min_path[i]='\0';
		point=0;
		for(i=0; i<count; i++)
		{
			for(j=0; j<c; j++) temp[j]=(char)(all_paths[i][j]+'0');
			temp[j]='\0';
			if( strcmp(temp,min_path) < 0)
			{
				strcpy(min_path,temp);
				point=i;
			}
		}
		for(i=0; i<c; i++)
		{
			if( i != 0)printf(" %ld",all_paths[point][i]+1);
			else printf("%ld",all_paths[point][i]+1);
		}

		printf("\n%lld",cost);
		
	}
}

void print_path(long row,long col)
{
	if( pre[row][col]== -1 )
	{
		all_paths[count][col]=row;
		return;
	}
	print_path((long)pre[row][col],col-1);
	all_paths[count][col]=row;
	return;
}

thanks ........

[tan_Yui]

I don't know what is wrong in your code, but please check this input.

http://online-judge.uva.es/board/viewto ... 4&start=15

Code: Select all

4 29
1 -1 0 0 1 -1 -1 -1 1 1 0 1 -1 -1 -1 0 -1 -1 1 -1 1 0 0 -1 0 -1 1 1 0
-1 1 0 -1 -1 0 1 0 -1 -1 -1 -1 1 1 0 -1 -1 0 -1 -1 1 -1 1 0 -1 1 0 1 -1
0 0 1 0 -1 1 0 0 1 1 0 -1 1 1 -1 -1 1 0 0 1 1 0 -1 1 0 -1 -1 1 1
1 -1 -1 -1 -1 -1 0 0 0 1 -1 0 0 0 -1 -1 0 -1 0 1 0 -1 1 0 1 1 -1 0 1

Output is :

Code: Select all

2 1 4 4 3 4 1 1 2 2 2 2 1 1 1 2 1 1 2 1 4 4 1 1 2 1 4 1 2
-25

By the way,
you should not make new thread if there are any same threads already in the board, as you know.

Best regards.

[mukeshtiwari]

hi all for this problem i use left to right dynamic programming so i m getting the
total minimum cost but i m not getting how to find out lexicographically
shortest path .here is my code ....plz explain ur
algorithm to find lexicographically shortest path.i could not understand ur algorithm sunnycare .my program works fine if one path exist but if more than one path exist then
it's not giving lexicographically smallest path.what i m doing is
i m finding last column(n-1) minimum value and note down the row number (let
it be i).now in second last column(n-2) i searched out minmium value in row
i-1,i and i+1 becoz of problem property. and i keep doing this until i reach
the 0th column.doing this i m not getting what i suppose to find out
...lexicographically smallest path.plz help...

Code: Select all

#include<stdio.h>

	int min1(int k,int m,int n)
		{
				int min;
				min=k;
				if(min>m)
				 min=m;
				if(min>n)
				  min=n;
				return(min);
		}
	main()
	{

		int m1[100][100],a[100][100],i,j,m,n,min,k,arr[100],t,min2,t1,t2,t3,v1;
		while(scanf("%d%d",&m,&n)==2)
		 {
			for(i=0;i<m;i++)
				for(j=0;j<n;j++)
					scanf("%d",&a[i][j]);
			
			for(i=0;i<m;i++)
				m1[i][0]=a[i][0];
			for(j=1;j<n;j++)
				for(i=0;i<m;i++)
					m1[i][j]=a[i][j]+min1(m1[(i+m-1)%m][j-1],m1[i][j-1],m1[(i+1)%m][j-1]);

			/*for(i=0;i<m;i++)
				{
					for(j=0;j<n;j++)
						printf("%d    ",m1[i][j]);
						printf("\n");
				}
			printf("\n");*/
			min2=m1[0][n-1];
			k=0;
			for(i=1;i<m;i++)
				if(m1[i][n-1]<min2)
				  {
					min2=m1[i][n-1];
					k=i;
					
				  }
			//printf("k=%d min=%d\n",k+1,min2);
			arr[n-1]=k;
			//printf("min=%d arr[%d]=%d\n",min2,n-1,arr[n-1]);
			for(j=n-2;j>=0;j--)
			 {
				//printf("j=%d ",j);
				min=m1[(arr[j+1]+m-1)%m][j];
				t1=(arr[j+1]+m-1)%m;
				t=t1;
				if(min>m1[arr[j+1]][j])
				 {
					min=m1[arr[j+1]][j];
					t2=arr[j+1];
					t=t2;
				 }
				else if(min==m1[arr[j+1]][j])
				 {
					t2=arr[j+1];
					if(t1>t2)
					  t=t2;
					else 
					  t=t1;
				 }
				
				if(min>m1[(arr[j+1]+1)%m][j])
				{
					min=m1[(arr[j+1]+1)%m][j];
					t3=(arr[j+1]+1)%m;
					t=t3;
					
				}
				
				else if(min==m1[(arr[j+1]+1)%m][j])
				  {
					t3=(arr[j+1]+1)%m;
					if(t>t3)
					  t=t3;
				  }
				arr[j]=t;
				//printf("min=%d arr[%d]=%d\n",min,j,t);
			 }
		
			for(i=0;i<=n-1;i++)
				printf("%d ",arr[i]+1);
				printf("\n%d\n",min2);
		}
	}

[/color]

[Jan]

Calculate the table from right to left. Then it would be easier to find the lexicographically smallest path.

[niangjun]

My prog worked for all the input given, but it still get WA, who can help me?

Code: Select all

program acm116;
type aa=array[1..100] of integer;
var a,d:array[1..100,1..100] of integer;
    f:array[1..10,1..100] of longint;
    rec1:aa;
    m,n:integer;    cost:longint;
    num:integer;

procedure init;
var i,j,k:integer;
begin
        fillchar(a,sizeof(a),0);
        for i:=1 to m do
         for j:=1 to n do read(a[i,j]);
end;

procedure calc;
var i,j,k,l,h:integer;
    o:array[1..3] of integer;
begin
        fillchar(f,sizeof(f),0);
        for i:=1 to m do f[i,n]:=a[i,n];
        for j:=n-1 downto 1 do
         for i:=1 to m do
          begin
           if (i>1) then o[1]:=i-1 else o[1]:=m;
           if (i<m) then o[3]:=i+1 else o[3]:=1;
           o[2]:=i;
           f[i,j]:=f[o[1],j+1];
           for k:=2 to 3 do if (f[o[k],j+1]<f[i,j]) then f[i,j]:=f[o[k],j+1];
           f[i,j]:=f[i,j]+a[i,j];
          end;
end;

procedure backtrack;
var i,j,k,h,x:integer;      l:longint;
    o:array[1..3] of integer;
begin
        cost:=f[1,1];
        for i:=2 to m do if (cost>f[i,1]) then cost:=f[i,1];
        k:=1;
        while (k<=m) and (cost<>f[k,1]) do k:=k+1;
        rec1[1]:=k;
        l:=cost-a[k,1];
        for j:=2 to n do
         begin
          if (k>1) then o[1]:=k-1 else o[1]:=m;
          if (k<m) then o[3]:=k+1 else o[3]:=1;
          o[2]:=k;
          x:=m+1;
          for h:=1 to 3 do if (f[o[h],j]=l) and (o[h]<x)
                 then x:=o[h];
          k:=x;
          rec1[j]:=k;
          l:=l-a[k,j];
         end;
end;

procedure output;
var i:integer;
begin
        for i:=1 to n-1 do write(rec1[i],' ');
        writeln(rec1[n]);
        writeln(cost);
end;

begin
        while not eof do
         begin
           m:=0; n:=0;
           readln(m,n);
           if(m*n<>0) then begin
                            init;
                            calc;
                            backtrack;
                            output;
                           end;
         end;
end.

Thanks!

[mukeshtiwari]

thnkx for reply and sorry for late response ....
i did not get how to calculate table from right to left ...plz tell me the algorithm ....

[Jan]

Imagine that you have to go from right to left. So,

Code: Select all

table[i][j] = min( table[(i+1)%row][j+1], table[i%row][j+1], table[(i-1)%row][j+1] );
mark[i][j] = i-1 or i or i+1 (which contains the least value)

Now the least value in the 0th column will be the starting position. And continue your process using the mark array.

Hope it helps.

[Spykaj]

In my code i changed:

Code: Select all

        scanf("%d",&T[i][j]);

to:

Code: Select all

        scanf("%d",&T[i][m-j+1]);

And answer:

Code: Select all

    for(j=1; j<m; j++){
      printf("%d ",O[j]);
    } printf("%d\n",O[m]);

to:

Code: Select all

    for(j=m; j>1; j--){
      printf("%d ",O[j]);
    } printf("%d\n",O[1]);

And i get ACC