Page 12 of 16
Posted: Thu May 11, 2006 11:43 am
by emotional blind
Ok
think about fibonacci
a fibonacci series is like
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....
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:
to:
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
