## 10261 - Ferry Loading

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Rivaldo, you should load as many cars as possible.

Rivaldo
New poster
Posts: 19
Joined: Sun Jul 07, 2002 3:59 pm

### 10261

I got WA many time. I checked my program using the data I found in http://plg.uwaterloo.ca/~acm00/, and it was right.

Who can tell my program's bug? Thanks.
[pascal]
const
maxn = 10010;
var
f,g : array[0 .. maxn] of boolean;
pre : array[0 .. maxn] of integer;
w : array[1 .. 210] of integer;
sol : array[1 .. 210] of boolean;
m,k,n : integer;

procedure init;
var j,s : integer;
begin
readln(k);
n := 0; s := 0;
readln(j); k := k * 100;
while j <> 0 do begin
inc(s, j);
if s <= k + k then begin
inc(n);
w[n] := j;
end;
readln(j);
end;
end;

procedure main;
var i,j,s,r : integer;
more : boolean;
begin
if n = 0 then begin
writeln(0);
exit;
end;
fillchar(g, sizeof(g), false);
fillchar(pre, sizeof(pre), 0);
g := true; s := 0;
for i := 1 to n do begin
s := s + w; more := false;
fillchar(f, sizeof(f), 0);
for j := k downto 0 do
if g[j] then begin
if s - j <= k then begin
f[j] := true; more := true;
end;
if j + w <= k then begin
f[j + w] := true;
pre[j + w] := i;
more := true;
end;
end;
if not more then break;
g := f;
end;

if not more then i := i - 1;
writeln(i);
r := 0;
for j := 0 to maxn do
if g[j] and (abs(s - j - j) < abs(s - r - r)) then r := j;
fillchar(sol, sizeof(sol), false);
while r <> 0 do begin
sol[pre[r]] := true;
r := r - w[pre[r]];
end;
for j := 1 to i do
if sol[j] then writeln('port')
else writeln('starboard');
end;

begin
readln(m);
while m > 0 do begin
dec(m);
init;
main;
writeln;
end;
end.
[/pascal]

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

### got RTE

I got Runtime Error (SIGSEGV) with my program. Please help me to find the bug.
[c]#include <stdio.h>

#define MAXN 201
#define MAXL 10001

int length[MAXN];

int knapsack(int itemsTaken[][MAXL], int n, int maxL)
{
int i, j;
int C[MAXN][MAXL];

for(i=0; i<=n; i++)
for(j=0; j<=maxL; j++)
itemsTaken[j] = 0;

for(i=0; i<=n; i++) C = 0;
for(j=0; j<=maxL; j++) C[j] = 0;

for(i=1; i<=n; i++)
for(j=1; j<=maxL; j++)
{
if(length > j) C[j] = C[i-1][j];
else
{
if(C[i-1][j] >= C[i-1][j-length]+length)
{
C[j] = C[i-1][j];
itemsTaken[j] = itemsTaken[i-1][j];
}
else
{
C[j] = C[i-1][j-length]+length[i];
itemsTaken[i][j] = i;
}
}
}
return (C[n][maxL]);
}

void main()
{
int kase, I;
int maxLenOfFerry, total, limit, count;
int newleft, newright;
int used[MAXN];
int i, temp, flag;
int itemsTaken[MAXN][MAXL];
scanf("%d", &kase);

for(I=0; I<kase; I++)
{
if(I) printf("\n");

scanf("%d", &maxLenOfFerry);
maxLenOfFerry *= 200;
limit = maxLenOfFerry / 2;
newleft = newright = 0;
flag = 1;
length = 0;
for(i=1, total=0, count=0; ; )
{
scanf("%d", &length[i]);
if(length[i]==0) break;
if(flag) total += length[i];
if(total <= maxLenOfFerry && newright <= limit && (newright+newleft+length[i])<=maxLenOfFerry)
{
newleft = knapsack(itemsTaken, i, limit);
newright = total - newleft;

if(newright <= limit)
count++;
i++;
}
else flag = 0;
}
for(i=0; i<=count; i++) used[i] = 0;
temp = count;

while(itemsTaken[count][limit])
{
used[itemsTaken[count][limit]] = 1;
limit = limit-length[itemsTaken[count][limit]];
count--;
}
count = temp;

printf("%d\n", count);

for(i=1; i<=count; i++)
{
if(used[i]) printf("starbord\n");
else printf("port\n");
}
}
}[/c]

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
Ok, I agree it is a knapsack problem, but I could not think in the right way to solve it... Can someone help me here?

JP.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
I am some confusion about this problem:

it says that the length of car is between 100 and 3000, is that true? I think I am getting some Run time error because of some values of cars are > 3000 in the judge input.

Thanks

inverse.midas
New poster
Posts: 1
Joined: Sun Sep 19, 2004 2:31 pm

### 10261 (Ferry loading problem) strange WAs...

Hello.
I coded my solution but it gets WA.
Fortunately, I've got an accepted solution from somewhere.
So I wrote a program which solves the problem twice - once by my method and once by the accepted method - and prints the results of the accepted method.
I inserted into this program some code which generates a SIGFPE when the maximum numbers of the cars computed by the two methods are different.
It also generates the signal when my method produces an infeasible solution, where the total length of the cars on one side of the ferry(port or starboard) is greater than the length of the ferry.
I submitted this program.
It's accepted because it prints the results by the accepted method and it never results in a SIGFPE.
That means my method calculates the correct maximum number of the cars.
And the total length of the cars on each side is less than or equal to the length of the ferry.
But strangely, my own program gets WAs. I wonder if the judge program is not flexible enough to check correctly?
Please give me some ideas..

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

### 10261 ferry loading again...

Could someone leak a hint for this problem(and I plead for more than that it's a knap-sack like problem)? I've been trying and leaving this problem for no less than a year now(shame, but true...). Thanks...

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm
Hi,
When i solved the problem with dp, got ac in ~0.2,
then switched to exhaustive search (without sophisticated pruning)
and got better time. So the judge's data is weak enough to try this way...
Csaba Noszaly

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
Exhaustive search.....???!!! The input is definitely weak then, as with the given constraints, I believe one could have 100 cars in the queue, and 2^100 is not something to play with..

I still wish somebody would advise how DP would be used here...Like I mentioned before, I tried for a year now...

Anyways, thanks mr Csaba...

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt
Finally got the DP solution...1 less problem to solve in life...!!!

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

### is there any greedy approach

is there any greedy solution to the problem. I see some zero memory and time solutions

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

### 10261 - DP problem

I have beein trying this one.
I found out that:

read a new car
- if i cant add any previous cars, dont try this one
- i can either add the car to the left or to the right, so try it by doing:
for(i=tam;i>=0;i--) if this position is checked THEN
if i can add it at position i (which means to the left), i try doing so
if i can not add it to the right, uncheck this position
if i unchecked all positions and did not check any one i was not able to add this car.... time to stop trying

The code follows, any tips? (ps: wrong answer)

Code: Select all

``````#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#define FOR(a,b) for(a=0;a<b;a++)
#define REP(a,b) for(int a=0;a<b;a++)

using namespace std;

char d;
int le() {
int v;
cin >> v;
return v;
}

int fer,pre,ult;

void st() {

int tam = le() * 100;
int v;
int i,j,k = 0;

FOR(i,tam+100) fer[i] = ult[i] = 0;
FOR(i,tam+100) pre[i] = -1;

fer = 1;

int total = 0;
bool parei = 0;
//cout << "comec" << endl;

while((v=le())!=0) {

if(parei) continue; // se parou, ignora esse
k++; // estamos no kesimo

bool cabe = 0;
for(i=tam;i>=0;i--) {

// se nao ativado ignora
if(!(fer[i])) continue;

// se cabe na esquerda, tenta la
if(i+v<=tam && !ult[i+v]) {
fer[i+v] = 1;
ult[i+v] = k;
cabe = 1;
pre[i+v] = i;
}

// se nao cabe na direita, tira daqui
if((total-i)+v>tam) {
fer[i] = 0;
} else {
cabe = 1;
}

}
// se coube em algum lugar.... ok
if(cabe) {
total += v;
//cout << "ad o " << k << endl;
} else {
k--;
parei = 1;
}

}

// sai imprimindo
/*FOR(i,tam+1) cout << fer[i] << " ";
cout << endl;
FOR(i,tam+1) cout << pre[i] << " ";
cout << endl;
FOR(i,tam+1) cout << ult[i] << " ";
cout << endl;*/

// procura o k na lista
FOR(i, tam+1) if(ult[i]==k) break;

vector<int> li;
// agora roda o iterativo
while(i!=0) {
li.push_back(ult[i]);
i = pre[i];
}

cout << k << endl;

for(i=1;i<=k;i++) {
if(find(li.begin(),li.end(),i)!=li.end()) cout << "port" << endl;
else cout << "starboard" << endl;
}

}

int main() {

int t = le();
while(t--) {
st();
if(t) cout << endl;
}

return 0;

}
``````

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Is this answer to the sample input correct?

Code: Select all

``````6
port
starboard
port
port
starboard
starboard
``````
I think it is, but how would the special judge test that?
If only I had as much free time as I did in college...

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Subject to this constraint as many cars should be loaded as possible, starting with the first car in the queue and loading cars in order until no more can be loaded.
This means you're not allowed to skip cars when loading. Your answer would give a total length of 52m on starboard.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Ah! Thanks. Now I understand.
If only I had as much free time as I did in college...