Kayaks logic

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.

problem statement

Regarding the algorithm itself :

I’d combine the higher with the lower
one and would get the answer…

I think the mistake is here.

Let’s have the following input :

4
50 51
50 52
50 52
50 54

Here, you combine the first person P1 (ratio=51/50) with the last one P4 (ratio=54/50).

The speed of the first boat (P1 and P4) is (51+54)/(20+50+50) = 0.875

The speed of the second boat (P2 and P3) is (52+52)/(20+50+50) = 0,867

Then, the total speed of the group is 0.867. You printed 0.875.


Regarding the implementation :

  • w, s, and ratio arrays cannot be dynamically sized that way (use a constant size instead) ;
  • minind and maxind are not initialized : if no ratio is < 1, minind will have an unknown value (possibly a huge one) ;
  • your program does not return 0, althought it should return an int. (not mandatory in C++, but it is in C).

good luck !

Thank you very much for you detailed comment, cyberax :slight_smile:

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

Bruno

is there an efficient way of solving
this?

sure ! :slight_smile: ask yourself some questions :

  • 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)

good luck :slight_smile:

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 :wink:

Bruno

yeah ! :slight_smile: you seem to be very close to a correct approach. it’s just a coding problem now. ^^

to understand how these questions are related to this problem, i suggest you to read the
solution of Neeraj Kumar.

look at the main function :

  • try to detect what variables are related to the lower and higher bounds we talked about ;
  • how are they used to find the final answer ? what kind of step-by-step operation is it ? ;
  • in your opinion, how the coder chose the number of steps needed ? is this related to floating-point precision ? ;
  • what operations are done before starting to read the problem data ? why ?

and in the “works” function :

  • how does he check if a possible answer satisfies all the constraints or not ?

If you can answer these last questions, you’re almost done. really. :slight_smile:

Glad to help you.

2 Likes

Sadly your concept is wrong .You can implement this by using binary search .
See this tutorial http://www.codechef.com/wiki/tutorial-kayaks

Could you please mention the problem link…

1 Like

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 :wink: