editorial_28350_780x0_proportion

TopCoder SRM 659 Div 2 Easy

This was my first SRM from an actual weekly competition! Checkout the problem statement.

So this problem asks us to take a list of positions, and a number that let’s us know how far we can jump.  We have to figure out how many positions we can reach within the array based of of the number given.  So, for instance, if we are given the positions array [1, 2, 3, 7, 9] and the number 1 for our max jump distance, we would be able to reach 1, 2, and 3 but not 7 and 9 as there are no numbers within 1 of these.  So here was my first attempt which took around 40 minutes (This is the one that I submitted):

public static int countReachableIslands(int[] positions, int L) {
       // first attempt
       int islands = 0;
       boolean[] canReach = new boolean[positions.length];

       canReach[0] = true;
       for (int i = 0; i < positions.length - 1; ++i)
           for (int j = i + 1; j < positions.length; ++j)
               if (Math.abs(positions[i] - positions[j]) <= L) {
                   canReach[i] = true;
                   canReach[j] = true;
               }

       for (boolean reachable : canReach ) {
           if (reachable) ++islands;
       }

       return islands;
}

Here’s my second attempt, which took about 20 minutes:

    // second attempt
    public static int countReachableIslands(int[] positions, int L) {
       int islands = 0;

       boolean[] canReach = new boolean[positions.length];
       canReach[0] = true;
       for (int i = 0; i < positions.length - 1; ++i)
           for (int j = i + 1; j < positions.length; ++j)
               if (Math.abs(positions[i] - positions[j]) <= L) {
                   canReach[i] = true;
                   canReach[j] = true;
               }

       for (boolean reachable : canReach)
           if (reachable)
               ++islands;
       return islands;
   }

And the last attempt, 2 minutes:

    // third attempt
    public static int countReachableIslands(int[] positions, int L) {
        if (positions == null || positions.length == 0) return 0;

        int islands = 0;

        boolean[] canReach = new boolean[positions.length];
        canReach[0] = true;
        for (int i = 0; i < positions.length - 1; ++i)
            for (int j = i + 1; j < positions.length; ++j)
                if (Math.abs(positions[i] - positions[j]) <= L) {
                    canReach[i] = true;
                    canReach[j] = true;
                }

        for (boolean reachable : canReach)
            if (reachable)
                ++islands;
        return islands;
    }

As you can see, all the attempts were just about the same! I really thought I had found the optimal solution to the problem this time on the first go round, and it did indeed pass all the test cases that came with the problem. However this solution was challenged in the challenge phase and I lost all my points. I couldn’t find out how to view the challenge parameters either so I am stuck not knowing what the fail case was. I will update this post once the match editorial is released in the next few days. In any case, it was fun taking a stab at the SRM challenge and I am looking forward to the next one! I can’t wait to dig further into my Algorithms book as well so that I can start getting into the harder problems.

Published by

Duke Deus

Deus Duke is a mobile software developer in the Bay Area. Also interested in game development, the occasional bar, and all around good times.

Leave a Reply