Okay, so here is my code to solve the problem Kayaks:
#include <stdio.h>
using namespace std;
int main()
{
int N;
scanf("%d", &N);
float max = 0;
float min = 1;
int maxind;
int minind;
int w[N];
int s[N];
for(int j = 0; j < N; ++j)
{
float ratio[N];
int weight;
int strength;
scanf("%d %d", &weight, &strength);
w[j] = weight;
s[j] = strength;
ratio[j] = float(strength)/weight;
if(ratio[j] > max)
{
maxind = j;
max = ratio[j];
}
if(ratio[j] < min)
{
minind = j;
min = ratio[j];
}
}
printf("%.6f", (s[maxind]+s[minind])/(20.0+w[maxind]+w[minind]));
}
What I did was maintain track of the highest and lowest ratios between strenght and speed for each person, and out of all those ratios, I’d combine the higher with the lower one and would get the answer… So where I am going wrong? :s It works for the test case.
Thank you very much for you detailed comment, cyberax
Hmm… I initially tried a greedy strategy, where I’d put the two lower ratio persons together in order to follow a “worst case” = “max speed” strategy but I almost immediately realized that such strategy would fail… Then I recalled a problem I had once solved in Google Code Jam which asked me to find a permutation of the coordinates of the two vectors in order to maximize their scalar product and the trick there was combine the higher coordinates with the lower ones…
Provided that this approach also fails and the only thing I can think of now is brute forcing all combinations, is there an efficient way of solving this? Can someone give a clue? Thanks in advance
given a set of persons, and considering the problem constraints (50<=wi<=100, 50<=si<=100), can you find the minimum and maximum theorical speed limits for the group ? is this range wide in your opinion ? or is it tight ?
if i give you a group speed, are you able to tell me fast enough if this group can reach this speed ? it’s the idea of problems which are difficult to compute an answer, but fast to check if an answer is correct or not (P-class, NP-class)
do you know a method (faster than checking them all in order), if given a range of numbers, that returns the first one that verifies a certain property ? (divide and conquer, binarylog research, lower/higher bounds sliding, etc.)
bonus one : given the answers to the three questions above, can you write an efficient algorithm to return the max speed a group can reach, if given a set of person characteristics ? (that’s actually the problem statement itself)
I believe that those are the kind of questions I need to start asking myself if I want to improve my algorithm design skills… So, I managed to work on some of those over my sleep and here are some conclusions I’ve arrived to:
In the “worst-case” group, I think that the range between the maximum and minimum theoretical speeds wouldn’t be that large, since the minimum speed is given by (50+50)/(100+100+20) and the maximum by (100+100)/(50+50+20); I’d say that in a typical input file the range will be smaller than this one.
Once I have found the maximum and minimum speed limits for the group, it’s just a matter of seeing whether the given speed is inside or outside the range of speeds. If it is outside I can definitely conclude that the group will never reach that speed! If it is in, it might reach the speed, but I think I can’t tell it before I analyze all the possibilities since the data are discrete and not continuous…
To do such thing without performing a sequencial search, I could use a built-in sort function of the language I am using and perform a binary search on the sorted range I guess… Although I’ve only implemented a binary search once, it shouldn’t be that hard…
Lastly, some tips on how to use all the answers to the questions above would be of great value to me! Thanks again for you reply and for helping me on my quest of becoming a better programmer
added to statement, in most cases you can find this when you click on user profile (discuss.codechef.com), then main profile (codechef.com) and last submissions here
you seem to be very close to a correct approach. it’s just a coding problem now. ^^