Gorillas and Poles meeting point algorithm - Not able to figure out the perfect solution and failing test cases

Question

I came across this problem while practicing on a competitive coding website. After giving a lot of thought, I came with the below mentioned logic but somehow, I'm not able to pass most of the test cases. Also, the website does not disclose test cases, so I'm clueless about what could go wrong. The problem is described below:

Problem Statement

A group of gorillas are performing in a circus and are positioned over multiple poles. The poles have their bases submerged into water. You are given the x and y coordinates of all poles in a 2-D plane. As the gorillas cannot swim, the only way for them to move from one pole to other is by jumping. However, when a gorilla jumps from one pole to another, the pole he jumped from gets submerged deeper by 1 unit. Please note that only the pole being jumped from gets submerged. The pole being jumped to is unaffected. For the climax of the circus, all gorillas must meet on one pole. The jumping ability of all gorilla's i.e. "J" is given to you. The jumping ability is nothing but the distance that can be covered by a gorilla in a single jump. A gorilla can jump from pole A to B only if the geometric distance between A and B is less than or equal to "J" i.e. the jumping ability. Every pole has a given height above water, so a fixed number of gorillas can jump from each pole, after which it will get submerged. If the poles are numbered from 0 to N-1, you need to determine the poles on which it is possible for all gorillas to meet during the climax of the circus. Let's say if the gorillas can meet on all poles out of 4 poles, then print 0 1 2 3. If they can meet only on poles 0 and 4, print 0 4. If they cannot meet on any pole, print -1. Gorillas can make any number of jumps, given it is possible as per above conditions.

Input

The first line is an Integer N denoting the number of poles.
The second line is a decimal J denoting the jumping ability of all gorillas.

The successive N lines consist of:
xi = x coordinate of the pole, yi = y coordinate of the pole, gi = the initial number of gorillas on the pole to start with, hi = height of the pole above water initially.

Output

Print the serial numbers of the poles where the gorillas can possibly meet. Print -1 if it is not possible for them to meet anywhere.

Constraints

1 <= N <= 100

0 <= J <= 100000

-10000 <= xi, yi <= 10000

0 <= gi <= 25

1 <= hi <= 200

Sample Test Cases

Input

3 30.0
1 10 5 20
5 10 5 20
8 10 5 20

Output

0 1 2

Explanation

Distance between all poles < 30.0, thus all gorillas can jump for any pole to any other pole when it comes to distance. Also, height of all poles i.e. 20 > no. of gorillas on each pole so the gorillas can easily meet on either pole 0, 1 or 2 by directly jumping on them.

Approach

Let's store all the information given in a 2-D Integer array.

// 4 columns to store xi, yi, gi and hi for each given pole.
int [][] polesInfo = new int[N][4];

First of all we need a loop to iterate over all poles, one by one and see if gorillas from all the poles can jump on the one pole we are looking at.

boolean [][] result = new boolean[N];
for(int i = 0; i < N; i++) {
    result[i] = canAllGorillasJumpToI(polesInfo,i)
}

Inside the method canAllGorillasJumpToI(), I have implemented it based on 3 cases,

1. All gorillas can directly jump to Pole i i.e. All poles have sufficient height and all poles are situated at a distance less than J. So direct jumps are possible from all poles just like the given test case and we return true.

2. One of the poles has more gorillas than it's height, and it will not be possible for all gorillas to jump anywhere from it, hence some gorillas will be eventually left over and in this case, all gorillas can never meet at ith pole, hence return false.

3. This is the most complicated case I'm stuck at and suspect that am missing something. If some of the gorillas are not able to jump directly due to the distance of their pole being far away, check for other possible poles to jump on that have sufficient capacity and then make successive jumps to the destination pole if possible.

1 and 2 are straightforward. But here is my logic for 3.

Store all the poles from where all gorillas cannot make direct jumps in an ArrayList. Sum up the number of gorillas that need to do an indirect jump.

for (Integer p : poles) {
    gorillaPositions += polesInfo [p][2];
}

Find all the poles that are in vicinity of the target pole i.e. within a distance less than J. Store the sum of their excess capacity available.

//pseudocode
if (poles in vicinity) {
    capacity += polesInfo [i][3] - polesInfo [i][2];
}

Finally, I'm checking if gorilla posiitons >= capacity and returning true.

if (gorillaPositions >= capacity ) {
    return true;
}

This logic seems to be working in some cases, but fails most test cases. I know something is not right in case 3 and I'm not able to think of such scenarios.

What would be a better algorithm to do this? Should I use graphs? Any help or test cases would be greatly appreciated. I can share more details or test cases if necessary.

Answer 1

This problem can be modeled as a maximum flow problem with vertex capacities.

First build the graph where the vertices are poles and the edges are pairs of poles that gorillas can jump between. All of these edges have unlimited (or very large) capacity in both directions. Each vertex has capacity equal to the number of gorillas that can jump from that pole.

To this network, add a source vertex with an arc to each pole vertex having capacity equal to the number of gorillas starting on that vertex. For each possible meeting point in turn, add a sink vertex with an arc from each pole vertex of unlimited capacity. If there is a source-to-sink flow of value equal to the number of gorillas, then the gorillas can congregate at that pole.

To transform the vertex capacities into arc capacities, split each capacitated vertex into two vertices. All of the incoming arcs go to one of the two; all of the outgoing arcs leave from the other. From the first vertex to the second, add an arc with capacity equal to the vertex capacity.