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

lotbsis
New poster
Posts: 1
Joined: Mon Jan 29, 2007 5:42 pm

Post by lotbsis » 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]

Dmitry R
New poster
Posts: 7
Joined: Sat Sep 17, 2005 10:42 am
Contact:

116 - Need help with PE

Post by Dmitry R » 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.

David Kjaer
New poster
Posts: 9
Joined: Sat Jul 07, 2007 5:47 pm
Location: Denmark

Post by David Kjaer » Mon Jul 23, 2007 4:57 am

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Jul 23, 2007 3:42 pm

Use existing threads.
Ami ekhono shopno dekhi...
HomePage

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Post by viniciusweb » 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!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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.
Ami ekhono shopno dekhi...
HomePage

viniciusweb
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Post by viniciusweb » 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.

ajkl
New poster
Posts: 2
Joined: Fri Jun 12, 2009 9:25 am

Re: 116 Help me

Post by ajkl » 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 :P).

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

kakalata
New poster
Posts: 1
Joined: Wed Dec 16, 2009 10:26 am

116 - PE

Post by kakalata » 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.


chucky316
New poster
Posts: 5
Joined: Mon Apr 12, 2010 11:18 am

Re: 116 - PE

Post by chucky316 » 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

incubi
New poster
Posts: 1
Joined: Tue Feb 15, 2011 1:45 am

116 RTE

Post by incubi » 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;}

}

varagrawal
New poster
Posts: 3
Joined: Sun Apr 24, 2011 10:33 pm

Re: 116 Help me

Post by varagrawal » 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;
}

shantanu18
New poster
Posts: 22
Joined: Tue Jul 20, 2010 9:55 pm

Re: help in Problem 116

Post by shantanu18 » 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;
}


zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: help in Problem 116

Post by zobayer » Sat Jun 18, 2011 11:54 am

@shantanu18, can you please explain your dp relations?
You should not always say what you know, but you should always know what you say.

shantanu18
New poster
Posts: 22
Joined: Tue Jul 20, 2010 9:55 pm

Re: help in Problem 116

Post by shantanu18 » 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

Post Reply

Return to “Volume 1 (100-199)”