getting correct for the test case…
my attempt was http://www.codechef.com/viewsolution/3478153 .
what i did was:
- Stored the diffenece btw the strength and weight and the index in a two
dimensional array. - Sorted the array according to the difference.
- took the first and last element and found their speed=min.
- iterated through the array and found the minimum speed.
plzzz anyone… help…
The solution given by you is incorrect in many ways. You are just finding the difference between the values of weights and strengths and then allotting the pairs. The actual solution is a standard binary search. As you are given the range of weights and strengths. You can find the maximum speed possible and the minimum speed possible, then you need to check if that speed is attainable in the most efficient pairing. The pairing is done not on the basis of difference but on the basis of
D[i] = strength[i] - speed * (weight[i]+10)
weight[i]+10 because a constant weight of 20 is added to each pair, so instead we can add 10 to each member of the pair.
The pairing factor is the one given above because if we add the factors of two elements we get
strength[i] + strength[j] -speed* (weight[i]+weight[j]+20) >=0
which is the required one.
Then the most efficient paring is the one as done by you by mapping the first and the last, second and second last and so on.
3 Likes
thank you…
+1 for nice explanation.
Thankyou for Such great Explanation.You have changed my perception toward looking such questions.