0
$\begingroup$

So, I have been solving problems in Google Foobar for the past two weeks or so ans has reached Level 4. The first problem is as stated below and I have come up with a solution which is able to pass all test cases except one. I have been stuck on it for the past 3 days and hasn't been able to made any progress so far. Can someone help me by pointing me in the right direction.

Here's the problem statement:

Running with Bunnies

You and your rescued bunny prisoners need to get out of this collapsing death trap of a space station - and fast! Unfortunately, some of the bunnies have been weakened by their long imprisonment and can't run very fast. Their friends are trying to help them, but this escape would go a lot faster if you also pitched in. The defensive bulkhead doors have begun to close, and if you don't make it through in time, you'll be trapped! You need to grab as many bunnies as you can and get through the bulkheads before they close.

The time it takes to move from your starting point to all of the bunnies and to the bulkhead will be given to you in a square matrix of integers. Each row will tell you the time it takes to get to the start, first bunny, second bunny, ..., last bunny, and the bulkhead in that order. The order of the rows follows the same pattern (start, each bunny, bulkhead). The bunnies can jump into your arms, so picking them up is instantaneous, and arriving at the bulkhead at the same time as it seals still allows for a successful, if dramatic, escape. (Don't worry, any bunnies you don't pick up will be able to escape with you since they no longer have to carry the ones you did pick up.) You can revisit different spots if you wish, and moving to the bulkhead doesn't mean you have to immediately leave - you can move to and from the bulkhead to pick up additional bunnies if time permits.

In addition to spending time traveling between bunnies, some paths interact with the space station's security checkpoints and add time back to the clock. Adding time to the clock will delay the closing of the bulkhead doors, and if the time goes back up to 0 or a positive number after the doors have already closed, it triggers the bulkhead to reopen. Therefore, it might be possible to walk in a circle and keep gaining time: that is, each time a path is traversed, the same amount of time is used or added.

Write a function of the form solution(times, time_limit) to calculate the most bunnies you can pick up and which bunnies they are, while still escaping through the bulkhead before the doors close for good. If there are multiple sets of bunnies of the same size, return the set of bunnies with the lowest prisoner IDs (as indexes) in sorted order. The bunnies are represented as a sorted list by prisoner ID, with the first bunny being 0. There are at most 5 bunnies, and time_limit is a non-negative integer that is at most 999.

For instance, in the case of
[
[0, 2, 2, 2, -1], # 0 = Start
[9, 0, 2, 2, -1], # 1 = Bunny 0
[9, 3, 0, 2, -1], # 2 = Bunny 1
[9, 3, 2, 0, -1], # 3 = Bunny 2
[9, 3, 2, 2, 0], # 4 = Bulkhead
]
and a time limit of 1, the five inner array rows designate the starting point, bunny 0, bunny 1, bunny 2, and the bulkhead door exit respectively. You could take the path:
Start End Delta Time Status
- 0 - 1 Bulkhead initially open
0 4 -1 2
4 2 2 0
2 4 -1 1
4 3 2 -1 Bulkhead closes
3 4 -1 0 Bulkhead reopens; you and the bunnies exit

With this solution, you would pick up bunnies 1 and 2. This is the best combination for this space station hallway, so the answer is [1, 2].

Solution

There are two parts of the solution that I have come up with:

  1. Negative Cycle - if there is any negative cycle in the graph then we can just loop it as many times as required and pick all the bunnies. I am doing this by Floyd Warshall algorithm as well as getting all the shortest pair paths which can be used in case there is no negative cycle

  2. DFS - In case there is no negative cycle, I simply start from the start point and try to get all the permutations of the order in which we can travel the graph and then check if the solution is correct at the end point.

        static int size;
        static List < Integer > ans;
        public static int[] solution(int[][] times, int times_limit) {
            // Your code here
            int n = times.length;
            if (n <= 2 || (n != times[0].length)) {
                return new int[] {};
            }
            boolean negCycle = check(times, n);
            if (negCycle) {
                int[] ans = new int[n - 2];
                for (int i = 0; i < n - 2; i++) {
                    ans[i] = i + 1;
                }
                return ans;
            } else {
                size = 0;
                ans = new ArrayList < >();
                boolean[] visited = new boolean[n];
                visited[0] = true;
                for (int i = 1; i < n - 1; i++) {
                    dfs(i, times_limit - times[0][i], times, new ArrayList < >(), visited);
                }
                if (ans.size() == 0) {
                    return new int[] {};
                }
                int[] ret = new int[ans.size()];
                for (int i = 0; i < ret.length; i++) {
                    ret[i] = ans.get(i);
                }
                Arrays.sort(ret);
                return ret;
            }
        }
    
        public static void dfs(int u, int time, int[][] times, List < Integer > list, boolean[] visited) {
    
            int n = times.length;
            if (time <= -999 || (u == n - 1 && time < 0) || (size == n - 2)) {
                return;
            }
            if (time >= 0 && u == n - 1) {
                if (list.size() > size) {
                    ans = new ArrayList < >(list);
                    size = list.size();
                }
                return;
            }
            if (visited[u]) {
                return;
            }
            visited[u] = true;
            list.add(u - 1);
            for (int v = 1; v < n; ++v) {
                if (v == u) {
                    continue;
                }
                dfs(v, time - times[u][v], times, list, visited);
            }
            list.remove(list.size() - 1);
            visited[u] = false;
        }
    
        public static boolean check(int[][] times, int n) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        if (times[i][k] + times[k][j] < times[i][j]) {
                            times[i][j] = times[i][k] + times[k][j];
                        }
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                if (times[i][i] < 0) {
                    return true;
                }
            }
            return false;
        }
    } ```
    
    

Please let me know if there's something wrong in my methodology.

$\endgroup$
1
  • $\begingroup$ I don't have the patience to look at your code, but could help you by showing you a solution that passed all the tests. Maybe by comparing them you can see what yours might be missing. $\endgroup$ – plop Aug 26 '20 at 19:49
0
$\begingroup$

I found the issue in my code. It was a very stupid mistake from my end. It was not passing the test case where there was a negative cycle in the graph because I was passing the result based on 1 as index starting instead of 0.

The original return value was being made by this:

for (int i = 0; i < n - 2; i++) {
      ans[i] = i + 1; // Extra one here
}

While it should be:
for (int i = 0; i < n - 2; i++) {
      ans[i] = i;
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.