116 - Unidirectional TSP

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu May 11, 2006 11:43 am

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
New poster
Posts: 6
Joined: Mon Mar 13, 2006 6:29 am
Location: Jakarta
Contact:

Post by Beenuxers » Thu May 11, 2006 12:45 pm

Hi, Arif... Thanks for ur sample and reference ... I can understand it... Now i'm gonna fix my code... Thx.... :wink:
Do better for a better tomorrow.... ;)

Beenuxers
New poster
Posts: 6
Joined: Mon Mar 13, 2006 6:29 am
Location: Jakarta
Contact:

Finally i got acc... :D

Post by Beenuxers » Tue May 16, 2006 6:09 am

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... ^^.
Last edited by Beenuxers on Sat May 27, 2006 7:56 am, edited 1 time in total.
Do better for a better tomorrow.... ;)

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Tue May 16, 2006 12:12 pm

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

Beenuxers
New poster
Posts: 6
Joined: Mon Mar 13, 2006 6:29 am
Location: Jakarta
Contact:

Post by Beenuxers » Sat May 27, 2006 7:57 am

Ok... I've already removed my code... ^^.
Do better for a better tomorrow.... ;)

sangram
New poster
Posts: 8
Joined: Fri Jun 30, 2006 3:27 pm
Contact:

Problem 116 - Presentation Error !

Post by sangram » Fri Jun 30, 2006 3:32 pm

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
New poster
Posts: 8
Joined: Mon May 15, 2006 8:46 am

116 - using DP, but still TLE

Post by Dzhefri » Fri Jul 07, 2006 10:49 pm

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
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

116 wa..........asking for help!!

Post by ayeshapakhi » Sat Sep 23, 2006 10:19 pm

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
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 116 wa..........asking for help!!

Post by tan_Yui » Sun Sep 24, 2006 10:00 am

I don't know what is wrong in your code, but please check this input.
BJM wrote: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
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Wed Dec 13, 2006 6:56 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Dec 13, 2006 7:33 pm

Calculate the table from right to left. Then it would be easier to find the lexicographically smallest path.
Ami ekhono shopno dekhi...
HomePage

niangjun
New poster
Posts: 3
Joined: Mon Dec 18, 2006 11:40 am

Post by niangjun » Mon Jan 01, 2007 6:46 am

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
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

Post by mukeshtiwari » Wed Jan 03, 2007 5:06 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jan 04, 2007 1:36 pm

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.
Ami ekhono shopno dekhi...
HomePage

User avatar
Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

Post by Spykaj » Thu Jan 04, 2007 5:39 pm

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 :D

Post Reply

Return to “Volume 1 (100-199)”