10715 - Cat

[Verdan]

Can you tell me what I'm doing wrong ?
1. Normalizing all weights Wi = Wi / Sum(Wi=1..n).
2. Sorting of weights.
3. Recursively find solution with summary weigh 0.49..0.51.

I've got WA.

Maybe I should print bigger or smaller solution ?
Should I sort numbers of rocks in answer ?

[little joey]

The total weight of ballast in the port hull should not differ from that in the starboard hull by more than 2%.

This is something else then that the difference should be smaller than 2% of the total weight. Looking for an answer between 0.496 and 0.504 would be more accurate.

[Animosity]

ok...where does my logic fail me?

Since there will always be a solution i'm using the following simple algorithm:

-sort weights in decreasing order
-have 2 sums s1=s2=0
-s1 += heaviest rock
-s2 += next heaviest
-recursively...compare s1 to s2 and add the next rock to whichever is smaller
- we end up with 2 sums that are close to each other

Working with the given example in the problem:
rocks in decreasing order: 90.0,50.0,38.0,10.0,7.1
s1 = 90.0; s2 = 50.0;
s2 += 38.0;
s2 += 10.0;
s1 += 7.1;
and we end up with s1 = 97.1 and s2 = 98.0

[Per]

If I understand your logic correctly, it fails when the weights are for instance:

3 3 2 2 2

[Animosity]

so true..too bad i didnt thought of it in time

[sohel]

I am also using the technique Verdan used and also made ammendments to my code with the modification that little joey added,
but I am getting TLE.

I will post my code here, cos it's relatively small..
btw I am with those who are against 'posting of codes' but finding no other alternative, I resorted to it.

[c]
// Name : Cat
// Number : 10715
// Author : Sohel Hafiz
// Date : 2004-11-08
// Algorithm : Backtracking

#include<stdio.h>
#include<algorithm>

using namespace std;
struct node{
double d;
double r;
int index;
};

node N[105];
int t;
int A[105];
int yes;

void dfs(int u, int d, double sum) {
if(yes) return;
if( sum > 0.504 ) return;
int i;
if( sum >= 0.496 && sum <= 0.504) {
for(i=0;i<d;i++) {
if( i ) printf(" ");
printf("%d", A[i] + 1);
}
printf("\n");
yes = 1;
return;
}
if( u == t) return;
A[d] = N[u].index ;

dfs(u+1, d+1, sum + N[u].r);
dfs(u+1, d, sum);

}

bool comp(const node &a, const node &b) {
return a.r > b.r;
}

int main() {
int i;
double total;
while(1) {
scanf("%d",&t);
total = 0;
if( t == 0 ) break;
for(i=0;i<t;i++) {
scanf("%lf", &N[i].d);
total += N[i].d;
N[i].index = i;
}
for(i=0;i<t;i++) {
N[i].r = N[i].d / total;
}
sort( N, N + t, comp);
yes = 0;
dfs(0, 0, 0);

}
return 0;
}
[/c]

Some help will be appreciated.

[Abednego]

Sohel, doesn't your algorithm make 2^100 calls to dfs()? Even with the branch-and-bound that doesn't allow the sum to go over 0.504.

What I did was round every weight to 2 decimal places, multiply them by 100 and do the simple coin change dispenser on it (with dynamic programming). But it gives me WA. My logic is:
1. The total sum of the weights is at most 10000.
2. Half of that is 5000.
3. 2% of that is 100.
4. Divided by the number of stones, it is 1 - the maximum allowed error per stone.
5. So if I have an error of 0.1 per stone, that should be well within the 2% bound.
6. Multiplying each weight by 100 and rounding gives an error of at most 0.005 per stone.

Hmmm. Did I mess up the coding, or is there something wrong with the logic?

[Abednego]

Ok. Normalizing first, like Verdan suggested, then scaling by a large number and rounding helped. But I'm still confused why the first method didn't work.

[IgorOstrovsky]

1. The total sum of the weights is at most 10000.
2. Half of that is 5000.
3. 2% of that is 100.
4. Divided by the number of stones, it is 1 - the maximum allowed error per stone.
5. So if I have an error of 0.1 per stone, that should be well within the 2% bound.
6. Multiplying each weight by 100 and rounding gives an error of at most 0.005 per stone.

Abednego, the problem with your error bound calculation is in your step 1: you assume the maximum sum of weights. If the sum of weights is smaller, all the numbers in your calculation, including the error per stone, will be smaller proportionally.

Igor (the other one )

[Abednego]

Ah! Of course. That makes sense.

[yohney]

ok, can somebody help me a bit? Let's say i somehow got weights for example 178 and 180. what it means 2% off?

does it mean if -> 1.02 * 178 >= 180 <- then it is OK, or what?

[LithiumDex]

After a little bit of a headache, and a few *cough* submissions, I solved it in 0.031 -- With a GA (that's Genetic Algorithm)

I used to obsessed with GA's... when all else failed, I would write a GA... let's hope this doesn't cause a relapse, lol