Page 12 of 16

Posted: Thu May 11, 2006 11:43 am
by 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

Posted: Thu May 11, 2006 12:45 pm
by Beenuxers
Hi, Arif... Thanks for ur sample and reference ... I can understand it... Now i'm gonna fix my code... Thx.... :wink:

Finally i got acc... :D

Posted: Tue May 16, 2006 6:09 am
by 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... ^^.

Posted: Tue May 16, 2006 12:12 pm
by emotional blind
Dont post your accepted code
it just spoils the program
so remove it immedieately
congaratulation for getting AC

Posted: Sat May 27, 2006 7:57 am
by Beenuxers
Ok... I've already removed my code... ^^.

Problem 116 - Presentation Error !

Posted: Fri Jun 30, 2006 3:32 pm
by 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.

116 - using DP, but still TLE

Posted: Fri Jul 07, 2006 10:49 pm
by 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;
	}
}
				
				

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

Posted: Sat Sep 23, 2006 10:19 pm
by 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 ........

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

Posted: Sun Sep 24, 2006 10:00 am
by tan_Yui
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.

Posted: Wed Dec 13, 2006 6:56 pm
by 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]

Posted: Wed Dec 13, 2006 7:33 pm
by Jan
Calculate the table from right to left. Then it would be easier to find the lexicographically smallest path.

Posted: Mon Jan 01, 2007 6:46 am
by 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!

Posted: Wed Jan 03, 2007 5:06 pm
by 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 ....

Posted: Thu Jan 04, 2007 1:36 pm
by 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.

Posted: Thu Jan 04, 2007 5:39 pm
by 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 :D