OJ Board

Posted: **Mon Jan 29, 2007 5:50 pm**

Hi! I ve tried every test input i found in this forum and they all seem to work fine. Why am i still getting wrong answer? :/
I used DP from right to left. Any Ideas? Thanx in advance!

Code: Select all

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) {
        Main myObj = new Main();
        myObj.myMethod();
    }
    void myMethod() {
        String input,cells;
        StringTokenizer idata,data;
        int r,c,min,min1,last_row;
        while((input = Main.ReadLn(255)) != null){
            idata = new StringTokenizer(input);
            r=Integer.parseInt(idata.nextToken());
            c=Integer.parseInt(idata.nextToken());
            int [][]Matrix=new int[r][c];
            int [][]Minimum=new int[r][c];
            for (int i=0;i<r;i++) {
                cells=Main.ReadLn(255);
                data = new StringTokenizer(cells);
                for (int y=0;y<c;y++) {
                    Matrix[i][y]=Integer.parseInt(data.nextToken());
                }
            }
            for (int i=0;i<r;i++) {
                Minimum[i][c-1]=Matrix[i][c-1];
            }
            for (int j=c-2;j>=0;j--) {
                for (int i=0;i<r;i++){
                    min=Minimum[(i+r-1)%r][j+1];
                    if (min>Minimum[(i+1)%r][j+1]){
                        min=Minimum[(i+1)%r][j+1];
                    }
                    if (min>Minimum[i][j+1]){min=Minimum[i][j+1];
                    }
                    Minimum[i][j]=Matrix[i][j]+min;
                }
            }
            min1=Minimum[0][0];
            last_row=0;
            for (int i=1; i<r; i++)
                if (min1>Minimum[i][0]){ min1 = Minimum[i][0];last_row=i;}
            System.out.print(last_row+1);
            for (int j=1;j<c;j++) {
                int min2=Minimum[(last_row-1+r)%r][j];
                int pos=(last_row-1+r)%r;

                if (Minimum[last_row][j]<min2){
                    min2=Minimum[last_row][j];pos=last_row;
                }else if (Minimum[last_row][j]==min2 && last_row<pos){
                    min2=Minimum[last_row][j];pos=last_row;}

                if (Minimum[(last_row+1)%r][j]<min2){
                    min2=Minimum[(last_row+1)%r][j];pos=(last_row+1)%r;
                }else if (Minimum[(last_row+1)%r][j]==min2 && (last_row+1)%r<pos){
                    min2=Minimum[(last_row+1)%r][j]; pos=(last_row+1)%r;}
                last_row=pos;
                System.out.print(" "+(pos+1));
            }
            System.out.println();
            System.out.println(min1); }


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

}

[/code]

Posted: **Sun Jul 22, 2007 2:23 pm**

Hello!

Could you tell me please what is special with the output in this task? My program generates the same output for sample tests as in the tasks, without any trailing spaces, and gets a Presentation Error.

Posted: **Mon Jul 23, 2007 4:57 am**

It's kind of hard to answer when I can't see your code.....

Posted: **Mon Jul 23, 2007 3:42 pm**

Use existing threads.

Posted: **Thu Jul 26, 2007 6:52 am**

After a long time getting WA, I finally evolved to PE

.

I'm printing the output exactly as described: one line with the path (integers separated by a single space) and one line with the minimum weight.

I already tried adding / removing the extra spaces at the end of each path line and the extra newline at the end of the output, but I keep getting "presentation error".

Can this be a problem with the lexicographical ordering? I have tested all the inputs on this forum and everything seems to be fine.

Thanks for any tips!

Posted: **Thu Jul 26, 2007 3:41 pm**

viniciusweb wrote: Can this be a problem with the lexicographical ordering? I have tested all the inputs on this forum and everything seems to be fine.
Thanks for any tips!

No. PE means you have done something worng in printing.

Posted: **Thu Jul 26, 2007 9:59 pm**

I got AC adding an extra "\n" at the end of output and removing the extra space at the end of each line describing the path.

Posted: **Sat Jun 13, 2009 10:44 am**

Hi all,

First, I want to thank jackie for wonderful test cases from which I recognized the bugs in my code.

I would also like to contribute two more test cases which I made myself to break my code (sorry if someone else has already posted, my bad for not searching the forum thoroughly

).

Input

Code: Select all

1 10
536870911 536870911 536870911 536870911
536870911 536870911 536870911 536870911
536870911 536870911

2 10
536870911 536870911 536870911 536870911
536870911 536870911 536870911 536870911
536870911 536870911 536870911 536870911
536870911 536870911 536870911 536870911
536870911 536870911 536870911 536870911

Output

Code: Select all

1 1 1 1 1 1 1 1 1 1
5368709110
1 1 1 1 1 1 1 1 1 1
5368709110

Posted: **Wed Dec 16, 2009 10:33 am**

Hi all, Anyone help me check my code. I get PE with this.

Code: Select all

const
        fin='';
        fout='';
        maxn=1000 + 10;

        dy:array[1..3]of longint=(1,1,1);
        dx:array[1..3]of longint=(1,0,-1);

type
        diem = record
                x,y:longint;
        end;

var
        fi,fo:text;
        m,n,x,y:longint;
        a:array[0..maxn,0..maxn]of longint;
        trace:array[0..maxn,0..maxn]of diem;

        f:array[0..maxn,0..maxn]of int64;

        res:int64;

procedure readfile;
var
        i,j:longint;
begin
        readln(fi,m,n);
        for i:=1 to m do
         begin
                for j:=1 to n do
                 read(fi,a[i,j]);
         end;

        readln(fi);
end;

procedure solve;
var
        i,j,k,u,v:longint;
begin
        for i:=1 to m do
         begin
                trace[i,n].x:=0;
                trace[i,n].y:=0;

                f[i,n]:=a[i,n];
         end;

        for j:=n - 1 downto 1 do
         for i:=1 to m do
          begin
                f[i,j]:=high(int64);

                for k:=1 to 3 do
                 begin
                        u:=i + dx[k];
                        v:=j + dy[k];

                        if u = 0 then u:=m;
                        if u > m then u:=1;

                        if f[u,v] + a[i,j] < f[i,j] then
                         begin
                                f[i,j]:=f[u,v] + a[i,j];
                                trace[i,j].x:=u;
                                trace[i,j].y:=v;
                         end
                        else
                         if f[u,v] + a[i,j] = f[i,j] then
                          if trace[i,j].x > u then
                           begin
                                trace[i,j].x:=u;
                                trace[i,j].y:=v;
                           end;
                 end;
          end;

        res:=high(int64);

        for i:=1 to m do
         if f[i,1] < res then
          begin
                res:=f[i,1];
                x:=i;
                y:=1;
          end;
end;

procedure gettrace(u,v:longint);
var
        ux,vx:longint;
begin
        write(fo,u,' ');

        ux:=trace[u,v].x;
        vx:=trace[u,v].y;
        if(ux <> 0)and(vx <> 0)then
         gettrace(ux,vx);
end;

procedure print;
begin
        gettrace(x,y);
        writeln(fo);
        writeln(fo,res);
end;

BEGIN
        assign(fi,fin);reset(fi);
        assign(fo,fout);rewrite(fo);

        while not eof(fi) do
         begin
                readfile;
                solve;
                print;
         end;

        close(fi);
        close(fo);
END.

Posted: **Fri Aug 13, 2010 7:06 am**

did you handle the case of one column only ???? so you won't need space after path as it will me one character only .... also make sure there is no extra spaces at the end of output ... and my AC code was with only one space separating each row number in the path more than one space got me PE
Regards

Posted: **Tue Feb 15, 2011 1:50 am**

hi all,

i keep getting RTE and can't figure out why - maybe someone can give me a hint what i'm doing wrong

thanks in advance

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.Reader;

public class Main {
	
	static int matrix[][];
	static int dimension[];
	
	public static void main(String[] args) {
		AcmReader in = new AcmReader();
		dimension = in.readInts();
		while(dimension != null && dimension.length > 0){
			matrix = new int[dimension[0]][dimension[1]];
			for(int i = 0; i< matrix.length; i++)
				matrix[i]=in.readInts();
			compute(matrix[0].length-2);
			System.out.println(backTrace());
			dimension = in.readInts();
		}
		try {
			in.close();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		System.exit(0);
		
	}
	
	private static String backTrace(){
		int [] rowNr = new int[dimension[1]];
		int minIndex=-1;
		int minValue = Integer.MAX_VALUE;
		
		for(int i = 0; i<dimension[0]; i++)
			if(matrix[i][0]<minValue){
				minValue = matrix[i][0];
				minIndex = i;
			}
		rowNr[0]=minIndex;
		for(int j = 1; j< dimension[1]; j++){
			minIndex=(rowNr[j-1]+dimension[0]-1)%dimension[0];
			int minVal=matrix[minIndex][j];
			int tmpIndex = minIndex;
			for(int i=1; i<3;i++){
				tmpIndex = (tmpIndex+1)%dimension[0];
				if(matrix[tmpIndex][j]<minVal){
					minVal=matrix[tmpIndex][j];
					minIndex=tmpIndex;
				}					
			}
			rowNr[j]=minIndex;
		}
		StringBuilder sb = new StringBuilder();
		sb.append((1+rowNr[0]));
		for(int i = 1; i<rowNr.length; i++)
			sb.append(" " + (1+rowNr[i]));
		sb.append("\n"+matrix[rowNr[0]][0]);
		return sb.toString();
		
		
	}

	private static void compute(int j) {
		if(j<0 || j >= matrix[0].length-1) return;
	
		for(int i = 0; i<matrix.length; i++){
			matrix[i][j]=matrix[i][j]+getMin(
					matrix[i][j+1], 
					matrix[(i+1)%dimension[0]][j+1], 
					matrix[(i+dimension[0]-1)%dimension[0]][j+1]); 
		}
		compute(j-1);
	}
	
	private static int getMin(int a, int b, int c){
		return (a<b)?((a<c)?a:c):((b<c)?b:c);
	}

}

class AcmReader extends BufferedReader {

	public AcmReader(Reader in) {super(in);}
	public AcmReader(){super(new InputStreamReader(System.in));}
	public int readInt() {
		try {return Integer.parseInt(this.readLine().trim());} 
		catch (Exception e){e.printStackTrace();}
		System.exit(1);
		return 0;}
	
	public int[] readInts(){
		try {
			String str = this.readLine();
			if(str == null || str.length()<1) return null;
			String tmp[] = str.trim().split("[\\s]+");
			int[] result = new int[tmp.length];
			for(int i = 0 ; i<result.length ; i++)
				result[i]=Integer.parseInt(tmp[i]);
			return result;
		}
		catch (Exception e){e.printStackTrace();}
		System.exit(1);
		return null;}

}

Posted: **Sun Apr 24, 2011 10:58 pm**

After the test input leave a space or two, or a carriage return in the input file. There is an extra output line with the previous case input.
Why is this?

My code:

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<bitset>
#include<algorithm>
#include<sstream>
#include<cctype>

typedef long long LL;

#define REP(i,a,b) for(LL i=a;i<b;i++)

using namespace std;

int main()
{

LL num[101][101];
LL path[101][101];
LL temp,temp1;

LL row,col;
LL r,c;

bool flag = false;

while(!cin.eof()){
if(flag){
cout<<endl;
}
flag = true;
cin>>r;
cin>>c;

if(!r) continue;

REP(i,0,r){
REP(j,0,c){
cin>>num[j];
}
}

for(int i=c-2;i>=0;i--){
for(int j=0;j<r;j++){
if(j==0){
if(num[j][i+1]<=num[j+1][i+1]){
if(num[j][i+1]<=num[r-1][i+1]){
temp = num[j][i+1];
col = j;
}
else{
temp = num[r-1][i+1];
col = r-1;
}
}
else{
if(num[j+1][i+1]<=num[r-1][i+1]){
temp = num[j+1][i+1];
col = j+1;
}
else{
temp = num[r-1][i+1];
col = r-1;
}
}
}
else if(j==r-1){
if(num[0][i+1]<=num[j-1][i+1]){
if(num[0][i+1]<=num[j][i+1]){
temp = num[0][i+1];
col = 0;
}
else{
temp = num[j][i+1];
col = j;
}
}
else{
if(num[j-1][i+1]<=num[j][i+1]){
temp = num[j-1][i+1];
col = j-1;
}
else{
temp = num[j][i+1];
col = j;
}
}
}
else{
if(num[j-1][i+1]<=num[j][i+1]){
if(num[j-1][i+1]<=num[j+1][i+1]){
temp = num[j-1][i+1];
col = j-1;
}
else{
temp = num[j+1][i+1];
col = j+1;
}
}
else{
if(num[j][i+1]<=num[j+1][i+1]){
temp = num[j][i+1];
col = j;
}
else{
temp = num[j+1][i+1];
col = j+1;
}
}
}

path[j] = col;
num[j] += temp;
}

}

temp = num[0][0];
row = 0;

for(int i=0;i<r;i++){
if(num[0]<temp){
temp = num[0];
row = i;
}
}

cout<<row+1<<" ";

for(int i=0;i<c-1;i++){
cout<<path[row]+1<<" ";
row = path[row];
}

cout<<endl<<temp;

}

return 0;
}

Posted: **Sun May 15, 2011 8:48 pm**

getting wa

Code: Select all


#include <cstdio>
#include <iostream>
#define MAX 128
#define max(a,b)(a>b?a:b)
using namespace std;
struct node{
	int cost;
	int prev;
};
int arr[MAX][MAX];
node DP[MAX][MAX];

void print_path(int n,int j)
{
	if(n==-1) return;
	else print_path(DP[n][j-1].prev,j-1);
	printf("%d ",n+1);
}
int main()
{
	
	int n,m;
	int x;
	int y;
	int z;
	while(scanf("%d%d",&n,&m)==2)
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				scanf("%d",&arr[i][j]);
		for(int i=0;i<n;i++)
		{
			DP[i][0].cost=arr[i][0];
			DP[i][0].prev=-1;
		}
		
		for(int j=1;j<m;j++)
		{
			for(int i=0;i<n;i++)
			{
				
				if(i==0) x=n-1;
				else x=i-1;
				if(i==n-1) z=0;
				else z=i+1;
				y=i;
				
				DP[i][j].cost = DP[x][j-1].cost + arr[i][j];
				DP[i][j].prev=x;
				
				if((DP[i][j].cost > DP[y][j-1].cost + arr[i][j]) || ((DP[i][j].cost == DP[y][j-1].cost + arr[i][j])&&y<DP[i][j].prev))
				{
					DP[i][j].cost = DP[y][j-1].cost + arr[i][j];
					DP[i][j].prev=y;
				}
				if((DP[i][j].cost > DP[z][j-1].cost + arr[i][j]) || ((DP[i][j].cost == DP[z][j-1].cost + arr[i][j])&& z<DP[i][j].prev))
				{
					DP[i][j].cost = DP[z][j-1].cost + arr[i][j];
					DP[i][j].prev=z;
				}
			}
		}
		node tmp;
		tmp=DP[0][m-1];
		tmp.prev=0;
		for(int i=1;i<n;i++)
		{
			if(DP[i][m-1].cost < tmp.cost)
			{
				tmp.cost=DP[i][m-1].cost;
				tmp.prev=i;
			}
		}
		print_path(DP[tmp.prev][m-1].prev,m-1);
		printf("%d\n%d\n",tmp.prev+1,tmp.cost);
	}
	return 0;
}

Posted: **Sat Jun 18, 2011 11:54 am**

@shantanu18, can you please explain your dp relations?

Posted: **Sat Jun 18, 2011 2:53 pm**

Run as column major. update current position from (i-1)(i) (i+1) of previous column. handle (1st and last row).
In this code i tried to print from 1st occurrence in last column. But i also tried all possible path and output the sorted one. NO LUCK

Code: Select all

1 
1   1 <-- this place update from three of previous column
1

OJ Board

116 - Unidirectional TSP

116 - Need help with PE

Re: 116 Help me

116 - PE

Re: 116 - PE

116 RTE

Re: 116 Help me

Re: help in Problem 116

Re: help in Problem 116

Re: help in Problem 116