Page 9 of 16
Posted: Thu Mar 03, 2005 6:33 pm
lexicographically refers to the ordered set
<a, b, c, d, .. etc >

and not the string order.. at least in this case.

Posted: Sat Mar 05, 2005 12:17 pm
BUT LARRY--
i think your all output are not correct
isnt it...?
i have sent it..

### Help!! Problem 116!! Critical i/o!!

Posted: Tue Mar 22, 2005 10:32 pm
For the input

Code: Select all

``````12 14
1 2 2 1 1 1 1 1 1 1 1 1 1 2
1 1 2 2 1 1 1 1 1 1 1 1 1 1
1 1 1 2 2 1 1 1 1 1 1 1 1 1
1 1 1 1 2 2 1 1 1 1 1 1 1 1
1 1 1 1 1 2 2 1 1 1 1 1 1 1
1 1 1 1 1 1 2 2 1 1 1 1 1 1
1 1 1 1 1 1 1 2 2 1 1 1 1 1
1 1 1 1 1 1 1 1 2 2 1 1 1 1
1 1 1 1 1 1 1 1 1 2 2 1 1 1
1 1 1 1 1 1 1 1 1 1 2 2 1 1
1 1 1 1 1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 1 1 1 1 1 1 2 2
``````
output should be

Code: Select all

``````1 2 3 4 5 6 7 8 9 10 11 12 1 2
14
``````
But http://www.algorithmist.com says that output is

Code: Select all

``````2 2 3 4 5 6 7 8 9 10 11 12 1 2
14
``````

### Re: Help!! Problem 116!! Critical i/o!!

Posted: Thu Mar 24, 2005 1:59 am
My C code outputs same answers about the set of input written into the board, but I got WA too....

Code: Select all

``````1 2 3 4 5 6 7 8 9 10 11 12 1 2
14
``````
I think you are right.
But, first of all, this input is illegal because
For each specification the number of rows will be between 1 and 10 inclusive; the number of columns will be between 1 and 100 inclusive.

And, I prepared following input.
Is the set of my output correct ?

Code: Select all

``````10 1
0
1
2
3
4
5
6
-1
8
9
1 10
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
5 2
5 1
6 2
4 3
5 -1
9 -3
2 5
5 1 6 2 4
3 5 -1 9 -3
1 1
-7
6 6
1 2  3  4  5  6
2 3  4  5  6  7
3 4  5  6  7 -1
4 5  5  7 -1  9
5 6  7 -1  9  0
6 7  8  9  0 -1
6 6
1 2  3  4  5  6
2 3  4  5  6  7
3 4  5  6  7 -1
4 5  4  7 -1  9
5 6  7 -1  9  0
6 7  8  9  0 -1
6 6
1 2  3  4  5  6
2 3  4  5  6  7
3 4  5  6  7 -1
4 5  6  7 -1  9
5 6  7  1  0  0
6 7  8  9  0  0
3 10
107374182 107374182 107374182 107374182 107374182 107374182 107374182 107374182 107374182 107374185
107374182 107374182 107374182 107374182 107374182 107374182 107374182 107374182 107374182 107374185
107374182 107374182 107374182 107374182 107374182 107374182 107374182 107374182 107374182 107374185
``````
My output :

Code: Select all

``````8
-1
1 1 1 1 1 1 1 1 1 1
-10
1 5
2
2 1 2 1 2
2
1
-7
1 1 6 5 4 3
8
2 3 4 5 4 3
7
1 1 1 1 6 5
10
1 1 1 1 1 1 1 1 1 1
1073741823
``````
Thank you.

### !

Posted: Thu Mar 24, 2005 10:40 am

Code: Select all

``````8
-1
1 1 1 1 1 1 1 1 1 1
-10
1 5
2
2 1 2 1 2
2
1
-7
1 1 6 5 4 3
8
2 3 4 5 4 3
7
1 1 1 1 6 5
10
1 1 1 1 1 1 1 1 1 1
1073741823
``````
I also get WA! I don't understand why???

### !

Posted: Thu Mar 24, 2005 10:55 am
Why my code get WA???????

Here my code:

Code: Select all

``````#include <iostream.h>

long long a[11][101];
int n,m;

int min(int y,int x)
{
int y1=y-1,y2=y+1;
if (y1==0) y1=m;if (y2==m+1) y2=1;
if (a[y1][x]<=a[y][x]&&a[y1][x]<=a[y2][x]) return y1;
else if (a[y][x]<=a[y2][x]&&a[y][x]<=a[y1][x]) return y;
else return y2;
}

int minim(int y,int x)
{
int y1=y-1,y2=y+1;
if (y1==0) {y1=y;y=y2;y2=m;}
if (y2==m+1) {y2=y;y=y1;y1=1;}
if (a[y1][x]<=a[y][x]&&a[y1][x]<=a[y2][x]) return y1;
else if (a[y][x]<=a[y2][x]&&a[y][x]<=a[y1][x]) return y;
else return y2;
}

void main()
{
int i,j;
while (cin>>m>>n){
for (i=1;i<=m;i++) for (j=1;j<=n;j++)cin>>a[i][j];

for (i=n-1;i>0;i--) for (j=1;j<=m;j++)
a[j][i]+=a[min(j,i+1)][i+1];

int minimal=1;
for (i=2;i<=m;i++) if (a[i][1]<a[minimal][1]) minimal=i;
cout<<minimal<<' ';
i=1;
j=minimal;
while (i++<n){j=minim(j,i);cout<<j<<' ';}
cout<<endl;
cout<<a[minimal][1]<<endl;
}}
``````

### 116 How to find lexikografically smallest path?

Posted: Tue Apr 12, 2005 2:42 pm
Hi! Could you help me with finding lexikografically smallest path? I use DP from left to right. Should i check all the paths with the same weight from the last column and then find the smallest path or there is easier solution?

Posted: Wed Apr 13, 2005 5:15 am
hi ....i have solved this problem.....

my algorithm is:

1 use dp to calculate the minimal path , from left to right
2 find all area that in a minimal path , from right to left (O(n*n) )
3 the the area with the smalllest row in column 1 (found in step 2) is the start area;
4 then from left to the right you will easy find the answer ( each column will at most need 3 check).....

i really want to know others fast and simple algorithm....

Posted: Wed Apr 13, 2005 11:10 am
I use DP from right to left.
Then find in the first column the first row with max number. This is the start point.
Then until u reach last column, assuming u arrived at position matrix[j] do this:
a = (i+n-1)%n // to simulate circle effect
b = i;
c = (i+1)%n // to simulate circle effect
// where n is the number of rows
Sort a,b,c to get lexicographical order: test in this order if maxmat[j] == matrix[j] + maxmat[a (then b, then c)][j+1]
one of them will be right. The first of them which is right is the lexicographically correct.

complexity of DP is O(n*m), but the tracking back is way faster...

Posted: Mon May 02, 2005 9:55 am
I got WA. WHY???
I use DP from right to left.
(my tables are just arrays)

This is my code (it is not written in english, sorry):
(I've passed ALL tests i've fount)

Code: Select all

``````#include<iostream>

#define N 10
typedef long long int li;

using namespace std;

void inline
llegirtaula(li t[],int m,int n)
{
register int i,j=m*n;
for(i=0;i<j;i++){
cin>>t[i];
}
}

//it returns  t_[i][j]
inline li
valora(li t_[],int i_,int j_, int n_)
{
return t_[i_*n_+j_];
}

//t_[i][j]=valor
inline void
valora(li t_[],int i_,int j_, int n_, li valor)
{
t_[i_*n_+j_]=valor;
}

/*********************************************
* Voy a meterle en costos[] lo que cuesta
* y en camins por donde ha llegado a
* conseguir esos costes, en la primera col
* debe estar el minimo, y seguir camins
*********************************************/
//it WRITES
void inline
excriu(li costos[],li camins[],int m,int n)
{
li aux;
int auxc;
int min;

int j=0;
aux=valora(costos,0,j,n);
auxc=0;
for(int i=1;i<m;i++){
li act=valora(costos,i,j,n);
if(act<aux){
aux=act;
auxc=i;
}
}
min=aux;
while(j<n-1){
cout<<(1+auxc)<<" ";
auxc=valora(camins,auxc,j,n);
j++;
}
cout<<(1+auxc);
cout<<endl<<min<<endl;
}

//Aquesta es la funcio que amb PD calcula el minim cami

//DP from right to left. costos[] is the length of path,
//camins[] is next path node
void
cami(li t[],int m,int n,int actual,li costos[],li camins[])
{
register int i,j,aux=n-1;
li min1,min2,min3;

/*****************************************
* primero:	inicializar todo todito
* 		poniendo la ultima columna
* 		de costos i camins como
* 		toca
*
* segundo:	de derecha a izquierda
* 		calcular cual es el camino
* 		mas corto de lo que falta
* 		guardando los nodos
*
* observ:	guardar el camino mas corto
* 		que contiene (i,j) en
* 		costos(i,j)
* 		guardar el siguiente paso en
* 		camins(i,j)
*****************************************/

//primer paso
for(j=0;j<m;j++){
costos[aux]=t[aux];
camins[aux]=0;
aux+=n;
}

//segundo paso
for( j=n-2;j>=0;j--){//de dcha a izda
for(i=0;i<m;i++){
li aux;
min1=valora(costos,(m+i-1)%m,j+1,n);
min2=valora(costos,i  ,j+1,n);
min3=valora(costos,(i+1)%m,j+1,n);
aux=valora(t,i,j,n);

//inici casuistica per veure quin es el minim
if(min3<min1 ||(min3==min1 && (i==n-1 ||i==0)) ){
if(min3<min2|| (min3==min2 && i==n-1)){
valora(costos,i,j,n,min3+aux);
valora(camins,i,j,n,(i+1)%m);
}
else{
valora(costos,i,j,n,min2+aux);
valora(camins,i,j,n,i%m);
}
}
else{
if(min2<min1 || (min2==min1 && i==0)){
valora(costos,i,j,n,min2+aux);
valora(camins,i,j,n,i%m);
}
else{
valora(costos,i,j,n,min1+aux);
valora(camins,i,j,n,(m+i-1)%m);
}
}//fi de la casuistica
}
}
}

int
main()
{
int m;
int n;

while(cin>>m>>n){
li costos[m*n];
li inicial[m*n];
li camins[m*n];
llegirtaula(inicial,m,n);
//first search path
cami(inicial,m,n,0,costos,camins);
//second write path
excriu(costos,camins,m,n);
}

return 0;
}
``````
Sorry for my english

Posted: Mon May 02, 2005 11:42 am

http://online-judge.uva.es/board/viewtopic.php?t=7544

bye
keep posting.

### P116 - Why it gets WA?

Posted: Mon May 02, 2005 4:50 pm
Hi.
My solution gets WA on P116, but I don't know why.
If anyone has input in wich it gets WA, please post.
Here is my code:

Code: Select all

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

long I, J, M, N, B [100][100], C [100][100][100];
unsigned long Sol, A [100][100];

bool Check (int K, int X, int L, int Y, int N) {
int I;
for (I = 0; I < N && C [K][X][I] == C [L][Y][I]; I++);
if (C [K][X][I] < C [L][Y][I]) return 1;
return 0;
}

void Add (int K, int L, int N) {
for (int I = 0; I < L; I++) C [K][L][I] = C [N][L-1][I];
C [K][L][L] = K;
}

int main (void) {
while (scanf ("%d%d", &M, &N) != EOF) {
for (I = 0; I < M; I++)
for (J = 0; J < N; J++) scanf ("%d", &A [I][J]);
for (I = 0; I < M; I++) C [I][0][0] = I;
for (J = 1; J < N; J++)
for (I = 0; I < M; I++) {
long K = ((I-1)+M)%M;
unsigned long T = A [I][J];
if (A [K][J-1] < A [I][J-1] || (A [K][J-1] == A [I][J-1] && Check (K, J-1, I, J-1, J))) { A [I][J] = A [K][J-1]; Add (I, J, K); }
else { A [I][J] = A [I][J-1], Add (I, J, I); }
K = (I+1)%M;
if (A [I][J] > A [K][J-1] || (A [I][J] == A [K][J-1] && Check (K, J-1, I, J, J))) { A [I][J] = A [K][J-1]; Add (I, J, K); }
A [I][J] += T;
}
Sol = 2147483647;
for (I = 0; I < M; I++)
if (Sol > A [I][N-1]) Sol = A [I][N-1], J = I;
long K = N;
printf ("%d", C [J][N-1][0]+1);
for (I = 1; I < N; I++)  printf (" %d", C [J][N-1][I]+1);
printf ("\n%lu\n", Sol);
}
exit (0);
} ``````

Posted: Mon May 02, 2005 5:23 pm
My code got AC on this problem and it outputs the same numbers yours does (except for the last case, where my machine uses 16bit int, which owerflows; but it would run on the juge just the same I belive...)

Posted: Sat May 07, 2005 1:24 pm
so you got accepted now?

Posted: Mon May 09, 2005 8:51 am
WA