116 - Unidirectional TSP

[Larry]

lexicographically refers to the ordered set
<a, b, c, d, .. etc >

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

[emotional blind]

BUT LARRY--
i think your all output are not correct
isnt it...?
i have sent it..

[Andrey]

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

WHY? Please HELP!!!!

[tan_Yui]

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.

[Andrey]

My C++ code outputs same answers about the set of input

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???

[Andrey]

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;
}}

[oldbam]

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?

[sunnycare]

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....

[jakabjr]

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...

[zorion]

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;

//it reads table from input
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

[emotional blind]

I hope this link will help you a lot
read carefully

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

bye
keep posting.

[KvaLe]

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);
} 

[jakabjr]

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...)

[emotional blind]

so you got accepted now?

[zorion]

WA
always Wrong Answer

I can't understand

All examples seem right