## 116 - Unidirectional TSP

Moderator: Board moderators

jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania
I stumbled upon this topic and... I'm amazed. This should definetly get some admin atention!!!

I submitted code on 116 and got AC. You may think I'd have nothing to complain about, but still: wk is right, 10 comes before 2 in lexicographical order. My code did not take that into account (I just did number order) and got AC. This is an error that I and the problem setter aparently overlooked. It should be fixed.

If we are wrong, pls reply.
Understanding a problem in a natural way will lead to a natural solution

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
I think when it says "lexicographically" they mean by comparing the first elements, then the second ones if the first ones were equal, and so on - but the pairwise-element comparison is numerical and not based on the actual characters.

At least, that's how I interpreted it.

It would seem to be a silly complication if it actually meant to put 10 before 2 (which is the only exception since there are at most 10 rows) - this would be a simple change to programs that solve the actual path finding problem, and wouldn't really add anything to the task other than confusion - maybe it should be reworded to avoid this.

snublefot
New poster
Posts: 6
Joined: Wed May 25, 2005 8:21 pm

### Rutime Error (SIGABRT)

I get a runtime error (SIGABRT) when I submit this code: I have never encountered the problem b4, so I don't know how to handle it...

/* @JUDGE_ID: 34812AC 116 Java */
import java.util.*;
import java.io.*;

class Key{
double dummy2=0.00000000000000001;
double dummy1=0.00000000000005;
public int iq, weight,name;
public double key;
int a,b;
public Key(int IQ, int W,int N){
name=N;
iq= IQ;
weight=W;
key=(double)weight;
key-=(double)iq*dummy1;
}
}
class Node{
int value;
Node parent;
Node left,right;
public Node(Node p,int v){
parent=p;
value=v;
}
public boolean isLeaf(){
return(left == null && right == null);
}
}

class Main {
String s;
StringTokenizer st;
int[][] Array;
int[][] weights; //total minimum weights;
int[][] Paths;
int[][] keys;
Integer CC;
int r,c;

public void begin() {
while(true){
try{// fails at end of file
//System.out.println(s);
st = new StringTokenizer(s);
String num=st.nextToken();
CC = new Integer(num);
r=CC.intValue();
num=st.nextToken();
CC = new Integer(num);
c=CC.intValue();
Array=new int[r][c];
Paths=new int[r][c];
weights=new int[r][c];

int ints=r*c;//number of ints
String t=s;
st = new StringTokenizer(t);
while(st.countTokens()<ints+2){
t=t.concat(" "+s);
st = new StringTokenizer(t);
}
st.nextToken();//r
st.nextToken();//c
for(int i=0;i<r;i++){
for (int j=0;j<c;j++){
num=st.nextToken();
CC = new Integer(num);
Array[j]=CC.intValue();
}
}
calculate();
}
catch(Exception e){
for(;;)
return;
}
}
}
private void calculate() {
keys=new int[r][c];
for(int i=0;i<r;i++){keys=i;}
//Assign first level weights
for (int i=0;i< r;i++){
weights=Array;
}
//find the edges from col C1 to col C2
for(int c2=1;c2<c;c2++){
int c1=c2-1;
//i==0
{
Paths[c2]=0; //default=0
keys[c2]=0;
//line 1
if(weights[c1]<weights[c1]){
Paths[c2]=1;
}
//line r-1
if(weights[r-1][c1]<weights[Paths[c2]][c1]){
Paths[c2]=r-1;
}
//line 1
if(Paths[c2]!=1){
if(weights[c1]==weights[Paths[c2]][c1]){//same weight as line 0
if(compare(keys,keys[Paths[c2]])>0){
Paths[c2]=1;
}
}
}
//line r-1
if(Paths[r-1][c2]!=r-1){
if(weights[r-1][c1]==weights[Paths[c2]][c1]){//same weight as line 0
if(compare(keys[r-1],keys[Paths[c2]])>0){
Paths[c2]=r-1;
}
}
}
}

for (int i=1;i< r-1;i++){
Paths[c2]=i-1;
if(weights[c1]<weights[Paths[c2]][c1]){
Paths[c2]=i;
}
if(weights[i+1][c1]<weights[Paths[c2]][c1]){
Paths[c2]=i+1;
}
if(Paths[i][c2]==i-1){//no change in the last two if-statements
if(weights[i][c1]==weights[Paths[i][c2]][c1]){
if(compare(keys[i],keys[Paths[i][c2]])>0){
Paths[i][c2]=i;
}
}
}

if(Paths[i+1][c2]<i+1){//i+1 not smaller than i-1 and i and thus not chosen yet
if(weights[i+1][c1]==weights[Paths[i][c2]][c1]){
if(compare(keys[i+1],keys[Paths[i][c2]])>0){
Paths[i][c2]=i+1;
}
}
}
}
//i==r-1
{
Paths[r-1][c2]=0; //default=0
keys[r-1][c2]=0;
//line r-2
if(weights[r-2][c1]<weights[c1]){
Paths[r-1][c2]=r-2;
}
//line r-1
if(weights[r-1][c1]<weights[Paths[r-1][c2]][c1]){
Paths[r-1][c2]=r-1;
}

//line r-2
if(Paths[r-1][c2]!=1){
if(weights[r-2][c1]==weights[Paths[r-1][c2]][c1]){//same weight as line 0
if(compare(keys[r-2],keys[Paths[r-1][c2]])>0){
Paths[r-1][c2]=r-2;
}
}
}
//line r-1
if(Paths[r-1][c2]!=r-1){
if(weights[r-1][c1]==weights[Paths[r-1][c2]][c1]){//same weight as smallest weight
if(compare(keys[r-1],keys[Paths[r-1][c2]])>0){
Paths[r-1][c2]=r-1;
}
}
}
}
//update the weight
for (int i=0;i< r;i++){
weights[i][c2]=Array[i][c2]+weights[Paths[i][c2]][c1];
}
//update the keys

int[][] keys2=new int[r][c];
for (int i=0;i< r;i++){
for (int j=0;j< c;j++){
keys2[i][j]=keys[Paths[i][c2]][j];
keys2[i][c2]=i;
}
}
keys=keys2;
}
int counter=0;
int result=0;
for (int i=1;i< r;i++){
if(weights[i][c-1]<weights[result][c-1]){
result=i;
}

}
//counts the number of cells in the rightmost column whose values are smallest.
for (int i=0;i< r;i++){
if(weights[i][c-1]==weights[result][c-1]){
counter++;
}
}
int[] path=getPath(result);
if(counter!=1){

for (int i=0;i< r;i++){
if(weights[i][c-1]==weights[result][c-1]){
int[] temp=getPath(i);
if(compare(temp,path)>0){
path=temp;
result=i;
}
}
}
}
print(result, path);
}
public int compare(int[] a, int[] b){
//The smaller has prescedence, as we are sorting lexicographically
for(int i=0;i<a.length;i++){
if(a[i]<b[i]){return 1;}
if(a[i]>b[i]){return -1;}
}
return 0;//will be returned if they are equal;
}
public int[] getPath(int lastElement){

int[] path=new int[c];
path[c-1]=lastElement;

for(int i=c-2;i>-1;i--){
path[i]=Paths[path[i+1]][i+1];
}
return path;
}
public void print2(int result, int[] path){
for(int i=0;i<c;i++){
System.out.print(""+(path[i]+1)+" ");
}
System.out.println();
//System.out.println(weights[result][c-1]);
}
public void print(int result, int[] path){
for(int i=0;i<c;i++){
System.out.print(""+(path[i]+1)+" ");
}
System.out.println();
System.out.println(weights[result][c-1]);
}

public static void main(String[] args) {
Main main = new Main();
try{
main.begin();

}catch(Exception e){
for(;;){}
}

}
StringBuffer out = new StringBuffer();
int car = -1;
try {
while (true) {
if (car == '\r')
continue;
if ((car < 0) || (car == '\n'))
break;
out.append((char) car);
}
}
catch (IOException e) {
return (null);
}
if ((car < 0) && (out.length() == 0))
return (null);
return out.toString();
}
byte lin[] = new byte[maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
if ((car < 0) || (car == '\n'))
break;
lin[lg++] += car;
}
}
catch (IOException e) {
return (null);
}
if ((car < 0) && (lg == 0))
return (null);
return (new String(lin, 0, lg));
}
while (s.length() == 0) {
}
return s;
}
}

snublefot
New poster
Posts: 6
Joined: Wed May 25, 2005 8:21 pm

### runtime error (SIGARBT)

Hi. This code for problem 116 is giving me a runtime error (SIGARBT). I have no idea how to approax this problem, save for posting my frustration on the forum. Is this another everyday acm java bug, or is there really something wrong with my problem? (maybe both, I don't know..)

Here is the code:

/* @JUDGE_ID: 34812AC 116 Java */
import java.util.*;
import java.io.*;

class Key{
double dummy2=0.00000000000000001;
double dummy1=0.00000000000005;
public int iq, weight,name;
public double key;
int a,b;
public Key(int IQ, int W,int N){
name=N;
iq= IQ;
weight=W;
key=(double)weight;
key-=(double)iq*dummy1;
}
}
class Node{
int value;
Node parent;
Node left,right;
public Node(Node p,int v){
parent=p;
value=v;
}
public boolean isLeaf(){
return(left == null && right == null);
}
}

class Main {
String s;
StringTokenizer st;
int[][] Array;
int[][] weights; //total minimum weights;
int[][] Paths;
int[][] keys;
Integer CC;
int r,c;

public void begin() {
while(true){
try{// fails at end of file
//System.out.println(s);
st = new StringTokenizer(s);
String num=st.nextToken();
CC = new Integer(num);
r=CC.intValue();
num=st.nextToken();
CC = new Integer(num);
c=CC.intValue();
Array=new int[r][c];
Paths=new int[r][c];
weights=new int[r][c];

int ints=r*c;//number of ints
String t=s;
st = new StringTokenizer(t);
while(st.countTokens()<ints+2){
t=t.concat(" "+s);
st = new StringTokenizer(t);
}
st.nextToken();//r
st.nextToken();//c
for(int i=0;i<r;i++){
for (int j=0;j<c;j++){
num=st.nextToken();
CC = new Integer(num);
Array[j]=CC.intValue();
}
}
calculate();
}
catch(Exception e){
for(;;)
return;
}
}
}
private void calculate() {
keys=new int[r][c];
for(int i=0;i<r;i++){keys=i;}
//Assign first level weights
for (int i=0;i< r;i++){
weights=Array;
}
//find the edges from col C1 to col C2
for(int c2=1;c2<c;c2++){
int c1=c2-1;
//i==0
{
Paths[c2]=0; //default=0
keys[c2]=0;
//line 1
if(weights[c1]<weights[c1]){
Paths[c2]=1;
}
//line r-1
if(weights[r-1][c1]<weights[Paths[c2]][c1]){
Paths[c2]=r-1;
}
//line 1
if(Paths[c2]!=1){
if(weights[c1]==weights[Paths[c2]][c1]){//same weight as line 0
if(compare(keys,keys[Paths[c2]])>0){
Paths[c2]=1;
}
}
}
//line r-1
if(Paths[r-1][c2]!=r-1){
if(weights[r-1][c1]==weights[Paths[c2]][c1]){//same weight as line 0
if(compare(keys[r-1],keys[Paths[c2]])>0){
Paths[c2]=r-1;
}
}
}
}

for (int i=1;i< r-1;i++){
Paths[c2]=i-1;
if(weights[c1]<weights[Paths[c2]][c1]){
Paths[c2]=i;
}
if(weights[i+1][c1]<weights[Paths[c2]][c1]){
Paths[c2]=i+1;
}
if(Paths[i][c2]==i-1){//no change in the last two if-statements
if(weights[i][c1]==weights[Paths[i][c2]][c1]){
if(compare(keys[i],keys[Paths[i][c2]])>0){
Paths[i][c2]=i;
}
}
}

if(Paths[i+1][c2]<i+1){//i+1 not smaller than i-1 and i and thus not chosen yet
if(weights[i+1][c1]==weights[Paths[i][c2]][c1]){
if(compare(keys[i+1],keys[Paths[i][c2]])>0){
Paths[i][c2]=i+1;
}
}
}
}
//i==r-1
{
Paths[r-1][c2]=0; //default=0
keys[r-1][c2]=0;
//line r-2
if(weights[r-2][c1]<weights[c1]){
Paths[r-1][c2]=r-2;
}
//line r-1
if(weights[r-1][c1]<weights[Paths[r-1][c2]][c1]){
Paths[r-1][c2]=r-1;
}

//line r-2
if(Paths[r-1][c2]!=1){
if(weights[r-2][c1]==weights[Paths[r-1][c2]][c1]){//same weight as line 0
if(compare(keys[r-2],keys[Paths[r-1][c2]])>0){
Paths[r-1][c2]=r-2;
}
}
}
//line r-1
if(Paths[r-1][c2]!=r-1){
if(weights[r-1][c1]==weights[Paths[r-1][c2]][c1]){//same weight as smallest weight
if(compare(keys[r-1],keys[Paths[r-1][c2]])>0){
Paths[r-1][c2]=r-1;
}
}
}
}
//update the weight
for (int i=0;i< r;i++){
weights[i][c2]=Array[i][c2]+weights[Paths[i][c2]][c1];
}
//update the keys

int[][] keys2=new int[r][c];
for (int i=0;i< r;i++){
for (int j=0;j< c;j++){
keys2[i][j]=keys[Paths[i][c2]][j];
keys2[i][c2]=i;
}
}
keys=keys2;
}
int counter=0;
int result=0;
for (int i=1;i< r;i++){
if(weights[i][c-1]<weights[result][c-1]){
result=i;
}

}
//counts the number of cells in the rightmost column whose values are smallest.
for (int i=0;i< r;i++){
if(weights[i][c-1]==weights[result][c-1]){
counter++;
}
}
int[] path=getPath(result);
if(counter!=1){

for (int i=0;i< r;i++){
if(weights[i][c-1]==weights[result][c-1]){
int[] temp=getPath(i);
if(compare(temp,path)>0){
path=temp;
result=i;
}
}
}
}
print(result, path);
}
public int compare(int[] a, int[] b){
//The smaller has prescedence, as we are sorting lexicographically
for(int i=0;i<a.length;i++){
if(a[i]<b[i]){return 1;}
if(a[i]>b[i]){return -1;}
}
return 0;//will be returned if they are equal;
}
public int[] getPath(int lastElement){

int[] path=new int[c];
path[c-1]=lastElement;

for(int i=c-2;i>-1;i--){
path[i]=Paths[path[i+1]][i+1];
}
return path;
}
public void print2(int result, int[] path){
for(int i=0;i<c;i++){
System.out.print(""+(path[i]+1)+" ");
}
System.out.println();
//System.out.println(weights[result][c-1]);
}
public void print(int result, int[] path){
for(int i=0;i<c;i++){
System.out.print(""+(path[i]+1)+" ");
}
System.out.println();
System.out.println(weights[result][c-1]);
}

public static void main(String[] args) {
Main main = new Main();
try{
main.begin();

}catch(Exception e){
for(;;){}
}

}
StringBuffer out = new StringBuffer();
int car = -1;
try {
while (true) {
if (car == '\r')
continue;
if ((car < 0) || (car == '\n'))
break;
out.append((char) car);
}
}
catch (IOException e) {
return (null);
}
if ((car < 0) && (out.length() == 0))
return (null);
return out.toString();
}
byte lin[] = new byte[maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
if ((car < 0) || (car == '\n'))
break;
lin[lg++] += car;
}
}
catch (IOException e) {
return (null);
}
if ((car < 0) && (lg == 0))
return (null);
return (new String(lin, 0, lg));
}
while (s.length() == 0) {
}
return s;
}
}

B.E
New poster
Posts: 7
Joined: Tue May 24, 2005 5:20 am
it means that there is an invaild memory Reference
I not going to find it for u because it would take me weeks to read.
INDENT AND COMMENT and you will find.

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

### What wrong with 116

pls get me hint:what wrong with my source
for all test I can find here my prog gen right output:
const mm=10;mn=100;type l=longint;
var a,b,c:array[1..mm,1..mn] of l;o,q,m,n,t,x,y:l;
begin {assign(input,'inp.3');reset(input);}
while not eof do begin read(m,n);if(m<1)or(n<1) then break;
for y:=1 to m do for x:=1 to n do read(a[y,x]);
for y:=1 to m do b[y,n]:=a[y,n];
for x:=n downto 2 do begin o:=m;q:=1 mod m+1;
for y:=1 to m do begin t:=o;
if b[y,x]<b[t,x] then t:=y else if(b[y,x]=b[t,x])and(y<t) then t:=y;
if b[q,x]<b[t,x] then t:=q else if(b[q,x]=b[t,x])and(q<t) then t:=q;
o:=o mod m +1;q:=q mod m +1;
b[y,x-1]:=a[y,x-1]+b[t,x];c[y,x-1]:=t;
end;
end;
y:=1;for t:=2 to m do if b[t,1]<b[y,1] then y:=t;t:=y;
for x:=1 to n do begin
write(y);
if x<n then write(' ') else writeln;
y:=c[y,x];
end;
writeln(b[t,1]);
end;
end.

Christophoros
New poster
Posts: 5
Joined: Thu Nov 25, 2004 12:56 am
I am getting also WA in probllem 116 .
I didn't understand if the lexicographic order should be acording to the values or acording to the string (10 is before 2<=x<=9 ? )

If someone can have a look to the following code : (I assume that the order is acording to the value)

Code: Select all

``````#include <iostream>
#include <fstream>
using namespace std ;

long small(long x,long y,long z,long j);
long b={0} , path={0} , temp ={0} ;

int main(){
long n , m , i , j , k , l , d ;
long minS ;

//	ifstream cin("in.txt",ios::in) ;

while (cin >> n >> m) {
for(i=1; i<=n ; ++i)
for(j=1 ; j<=m ; ++j) cin >> b[i][j] ;

for (i=1 ; i<=n ; ++i) path[i] = i ;

for(j=2; j<=m ; ++j){

for(k=1; k<=n ; ++k)
for(l=1 ; l<=j ; ++l) temp[k][l] = path[k][l] ;

for(i=1 ; i<=n ; ++i){
if (i==1) d = small(1,2,n,j-1) ;
else if (i==n) d = small(1,n-1,n,j-1) ;
else d = small(i-1,i,i+1,j-1) ;

for(k=1 ; k<j-1 ; ++k) { temp[i][k] = path[d][k] ; }
temp[i][j-1] = d ; temp[i][j] = i ; b[i][j] += b[d][j-1] ;  }

for(k=1; k<=n ; ++k)
for(l=1 ; l<=j ; ++l) path[k][l] = temp[k][l] ; }

minS = b[m] ; d = 1 ;
for(i=2; i<=n ; ++i)
if (minS>b[i][m]) { minS = b[i][m] ; d = i ; }
else if (minS==b[i][m]) {
for(j=1 ; j<=m ; ++j)
if (path[i][j]<path[d][j]) {d = i ; break ; }
else if (path[d][j]<path[i][j]) break ; }

for(j=1 ; j<m ; ++j) cout << path[d][j] << ' ' ; cout << d << endl ;
cout << minS << endl ;		}

return 0 ; }

long small(long x,long y,long z,long j){
long f , ret ;

ret = x ;
if (b[y][j]<b[x][j]) ret = y ;
else if (b[x][j]==b[y][j]) {
for(f=1 ; f<=j ; ++f)
if (path[x][f]<path[y][f])  break ;
else if (path[y][f]<path[x][f]) { ret = y ; break ; }}

if (b[ret][j]<b[z][j]) return ret ;
else if (b[ret][j]>b[z][j]) return z ;
else if (b[ret][j]==b[z][j]) {
for(f=1 ; f<=j ; ++f)
if (path[ret][f]<path[z][f])  return ret ;
else if (path[z][f]<path[ret][f]) return z ;
else if (f==j) return z ; } }
``````
thanx in advance for any help.

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

### re

for all test from board my prog (see in top)gen good result
but judge get WA
where bug???

Hardi
New poster
Posts: 12
Joined: Fri Jun 10, 2005 2:44 pm
Location: Estonia, P
The point of writing solutions for problems is having fun and educating yourself. I don't know where the bug is - I am still trying to solve problem no. 104
"There is no point in learning facts, which are derived from logic, if you can learn the logic to derive facts" - Hardi Pertel

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
I'm getting WA still now I want to know the meaning of the word : lexicographically

but I'm confused because it was complicated.

Is the priority level of '10' higher than '2 to 9' ?
Following is the input about them.
What's the right output?
10 2
2 1
1 1
2 1
2 2
2 2
2 2
2 2
2 2
2 1
1 1
10 2
2 2
2 2
2 2
2 2
2 2
2 2
2 2
2 1
1 1
2 1
Best regards.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Could anyone help me about my above post? And give me new input set....

BJM
New poster
Posts: 7
Joined: Sat Nov 16, 2002 3:28 pm
I just got AC on this one. In this case Lexicographically means that where there is a choice of two routes you must choose the one that starts with the lowest numbered row. If two routes start with the same row then the look at the second step and compare and so on. In each comparison the natural sequence of numbers applies 1<2<3<4<5<6<7<8<9<10.

The main difficulty is that the wrapping causes paths that end up with higher row numbers having a chance of starting with lower row numbers.

Code: Select all

``````For example
6 6
1 2 2 1 2 1
2 1 2 2 1 2
2 2 1 2 2 1
1 2 2 1 2 2
2 1 2 2 1 2
2 2 1 2 2 1

Should give

1 2 3 4 5 6
6

``````
If you need any other tips let me know.

BJM

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Thanks for your reply, BJM. Although I've gotten the judgement 'Wrong Answer' still now, I could know the meaning of lexicographically.
Your above reply helped to fix my recognition of this problem statement.

I'll try to check my code again.

By the way, if you have some the set of input more, please give me. I want to use them by my debugging.

Thank you. BJM
New poster
Posts: 7
Joined: Sat Nov 16, 2002 3:28 pm
If you paste your code on the board I'll have a scan when I get time.

This might be quicker than finding the right test case to pick out the problem.

BJM

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
This is my code which got WrongAnswer.
Thank you.

Code: Select all

``````/* C */
/* caution!! lexicographically order */
/* 1 < 2 < ... < 9 < 10 */

CUT AFTER Accepted
Thank you.
``````
Last edited by tan_Yui on Mon Oct 17, 2005 3:58 am, edited 1 time in total.