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

Post by Adrian Kuegel » Sat Aug 17, 2002 3:46 pm

Rivaldo, you should load as many cars as possible.

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

10261

Post by Rivaldo » Sun Oct 20, 2002 9:07 am

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[0] := 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

Post by Subeen » Fri Oct 17, 2003 12:44 pm

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] = 0;
for(j=0; j<=maxL; j++) C[0][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] = 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:

Post by jpfarias » Tue Oct 28, 2003 6:35 pm

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:

Post by yiuyuho » Mon Jan 19, 2004 11:13 am

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...

Post by inverse.midas » Sun Sep 19, 2004 3:10 pm

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...

Post by mido » Mon Jan 10, 2005 1:31 am

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

Post by tat tvam asi » Tue Jan 11, 2005 1:24 am

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

Post by mido » Tue Jan 11, 2005 1:33 am

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

Post by mido » Tue Jan 18, 2005 7:38 pm

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

Post by ranjit » Sun Jan 30, 2005 8:44 am

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

Post by technobug » Thu May 19, 2005 2:09 pm

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[1000];
int le() {
       int v;
       cin >> v;
       return v;
}

int fer[30000],pre[30000],ult[30000];

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[0] = 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;

}

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Nov 17, 2005 1:42 am

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...

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Nov 17, 2005 10:10 am

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.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Nov 17, 2005 6:15 pm

Ah! Thanks. Now I understand.
If only I had as much free time as I did in college...

Post Reply

Return to “Volume 102 (10200-10299)”