10261 - Ferry Loading

[Adrian Kuegel]

Rivaldo, you should load as many cars as possible.

[Rivaldo]

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]

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]

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]

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]

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]

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]

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]

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]

Finally got the DP solution...1 less problem to solve in life...!!!

[ranjit]

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

[technobug]

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;

}

[Abednego]

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?

[little joey]

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]

Ah! Thanks. Now I understand.