Page 10 of 16

Posted: Tue May 10, 2005 1:35 pm
by jakabjr
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.

Posted: Wed May 11, 2005 4:38 am
by Quantris
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.

Rutime Error (SIGABRT)

Posted: Wed May 25, 2005 8:27 pm
by snublefot
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
s = readLn();
//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];

//reading array
int ints=r*c;//number of ints
String t=s;
st = new StringTokenizer(t);
while(st.countTokens()<ints+2){
s=readLn();
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[0]=i;}
//Assign first level weights
for (int i=0;i< r;i++){
weights[0]=Array[0];
}
//find the edges from col C1 to col C2
for(int c2=1;c2<c;c2++){
int c1=c2-1;
//i==0
{
Paths[0][c2]=0; //default=0
keys[0][c2]=0;
//line 1
if(weights[1][c1]<weights[0][c1]){
Paths[0][c2]=1;
}
//line r-1
if(weights[r-1][c1]<weights[Paths[0][c2]][c1]){
Paths[0][c2]=r-1;
}
//line 1
if(Paths[0][c2]!=1){
if(weights[1][c1]==weights[Paths[0][c2]][c1]){//same weight as line 0
if(compare(keys[1],keys[Paths[0][c2]])>0){
Paths[0][c2]=1;
}
}
}
//line r-1
if(Paths[r-1][c2]!=r-1){
if(weights[r-1][c1]==weights[Paths[0][c2]][c1]){//same weight as line 0
if(compare(keys[r-1],keys[Paths[0][c2]])>0){
Paths[0][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[0][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(;;){}
}

}
static String readLn() {
StringBuffer out = new StringBuffer();
int car = -1;
try {
while (true) {
car = System.in.read();
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();
}
static String readLn(int maxLg) {
byte lin[] = new byte[maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
car = System.in.read();
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));
}
public String readNELn() {
String s = readLn();
while (s.length() == 0) {
s = readLn();
}
return s;
}
}

runtime error (SIGARBT)

Posted: Wed May 25, 2005 8:33 pm
by snublefot
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
s = readLn();
//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];

//reading array
int ints=r*c;//number of ints
String t=s;
st = new StringTokenizer(t);
while(st.countTokens()<ints+2){
s=readLn();
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[0]=i;}
//Assign first level weights
for (int i=0;i< r;i++){
weights[0]=Array[0];
}
//find the edges from col C1 to col C2
for(int c2=1;c2<c;c2++){
int c1=c2-1;
//i==0
{
Paths[0][c2]=0; //default=0
keys[0][c2]=0;
//line 1
if(weights[1][c1]<weights[0][c1]){
Paths[0][c2]=1;
}
//line r-1
if(weights[r-1][c1]<weights[Paths[0][c2]][c1]){
Paths[0][c2]=r-1;
}
//line 1
if(Paths[0][c2]!=1){
if(weights[1][c1]==weights[Paths[0][c2]][c1]){//same weight as line 0
if(compare(keys[1],keys[Paths[0][c2]])>0){
Paths[0][c2]=1;
}
}
}
//line r-1
if(Paths[r-1][c2]!=r-1){
if(weights[r-1][c1]==weights[Paths[0][c2]][c1]){//same weight as line 0
if(compare(keys[r-1],keys[Paths[0][c2]])>0){
Paths[0][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[0][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(;;){}
}

}
static String readLn() {
StringBuffer out = new StringBuffer();
int car = -1;
try {
while (true) {
car = System.in.read();
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();
}
static String readLn(int maxLg) {
byte lin[] = new byte[maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
car = System.in.read();
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));
}
public String readNELn() {
String s = readLn();
while (s.length() == 0) {
s = readLn();
}
return s;
}
}

Posted: Fri May 27, 2005 12:36 am
by B.E
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.

What wrong with 116

Posted: Mon Jun 06, 2005 7:24 pm
by QulinXao
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.

Posted: Tue Jun 07, 2005 2:46 pm
by Christophoros
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[15][101]={0} , path[15][101]={0} , temp[15][101] ={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][1] = 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[1][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.

re

Posted: Sun Jun 12, 2005 7:22 am
by QulinXao
PLEASE HELP ME. WERE I am WRONG????
for all test from board my prog (see in top)gen good result
but judge get WA
where bug???

Posted: Tue Jun 14, 2005 2:00 pm
by Hardi
Don't be mad.
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

Posted: Tue Sep 27, 2005 3:59 am
by tan_Yui
I'm getting WA still now :(
Anyone please help me..

I want to know the meaning of the word : lexicographically

Of course, I read all past thread of this board,
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.

Posted: Tue Oct 11, 2005 3:10 pm
by tan_Yui
Could anyone help me about my above post? :cry:
And give me new input set....

Posted: Wed Oct 12, 2005 2:17 pm
by BJM
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

Posted: Wed Oct 12, 2005 3:36 pm
by tan_Yui
Thanks for your reply, BJM. :D
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. :)

Posted: Sat Oct 15, 2005 12:27 am
by BJM
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

Posted: Sat Oct 15, 2005 8:08 am
by tan_Yui
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.