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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

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

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

Post by emotional blind »

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

Andrey
New poster
Posts: 16
Joined: Sat Mar 05, 2005 8:25 pm
Location: Ukraine,Vinnitsa

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

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

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

Post by 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
New poster
Posts: 16
Joined: Sat Mar 05, 2005 8:25 pm
Location: Ukraine,Vinnitsa

!

Post by 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???
Sorry for my English!!

Andrey
New poster
Posts: 16
Joined: Sat Mar 05, 2005 8:25 pm
Location: Ukraine,Vinnitsa

!

Post by 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;
}}
Sorry for my English!!

oldbam
New poster
Posts: 17
Joined: Tue Sep 14, 2004 9:30 am

116 How to find lexikografically smallest path?

Post by 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?
Life is beautifull !!!

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

Post by 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
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by 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...
Understanding a problem in a natural way will lead to a natural solution

zorion
New poster
Posts: 2
Joined: Mon May 02, 2005 9:41 am
Contact:

Post by 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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by 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
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

P116 - Why it gets WA?

Post by 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);
} 
Giorgi Lekveishvili

jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania

Post by 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...)
Understanding a problem in a natural way will lead to a natural solution

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

Post by emotional blind »

so you got accepted now?

zorion
New poster
Posts: 2
Joined: Mon May 02, 2005 9:41 am
Contact:

Post by zorion »

WA
always Wrong Answer

I can't understand

All examples seem right

Post Reply

Return to “Volume 1 (100-199)”