AVGSHORT - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Harshil Shah
Editorialist: Pawel Kacprzak

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Graphs, shortest paths, binary search, Bellman-Ford algorithm

PROBLEM:

For a given nodes A and B, find the average length of a walk between A and B that has the smallest average length among all such walks or decide that there is no walk between these nodes.

QUICK EXPLANATION:

First, check if B is reachable from A. If not, we are done. Otherwise, perform a binary search over all possible resulting average lengths. For a fixed average length L, use Bellman-Ford algorithm to find out if the graph has a walk from A to B with average length less or equal to L.

EXPLANATION:

Subtask 1

In the first subtask the constraints are very small, we have at most 10 vertices and at most 20 edges. One may try various approach within these constrains. One of them may be to first find out average lengths of all simple paths from A to B by examining all of them, and after that, try to form an infinite walk between A and B by adding a cycle with some minimum length L, which when the walk is infinite, will dominate other length is such a path. Alternatively, some approximate solutions may be also possible, because the required precision of the answer in this subtask is not very restrictive.

Subtask 2

Let’s assume that B is reachable from A, because in the other case the answer is obvious, and this can be easily check by a simple DFS. After that, let’s try to solve a different problem:

For a given value L, decide if there exists a walk from A to B with average length not greater than L.

How is this problem simpler than the original one? Well, let’s assume that there exists a walk W from A to B with average length less or equal to L. Now, let’s subtract L from all weights of edges in the graph. How does this operation affect W? Since its average length was not greater than L before, and we subtracted L from all weights, now its absolute length is not greater than 0. Moreover, this operation of lowering weights of edges affects all paths in the same way, i.e. the relative order of their average lengths is not affected by the operation (be careful here, this is not true when operating on absolute lengths instead of average lengths).

So far so good, but how to find out if there is a walk from A to B of length not greater than 0? It is very important that we are looking for a walk, not only for a simple path here. Moreover, after subtraction, weights on edges can be negative, which is also important for certain algorithms to work. Fortunately, Bellman-Ford algorithm can be used here. It works perfectly with negative edges and can be used to detect if a graph has a negative length cycle, which is crucial in the solution.

In order to find out if there is a walk from A to B with length not greater than 0, we run Bellman-Ford algorithm to compute the shortest simple path from A to B. If its length is not greater than 0, we are done. Otherwise, we use Bellman-Ford to check if there is a negative length cycle C in the graph, with the property that C is reachable from A and B is reachable from C. If there is any such cycle C, then by traversing it enough number of times, we can always lower the cost of the path (which is in fact a walk right now) to be not greater than 0. If there is no such cycle, then there is no walk from A to B with length not greater than 0, because there is no such simple path between them with that property and there is no negative cycle which can lower a cost of any path from A to B. This solution works in O(N * M) time, because this is the running time of Bellman-Ford algorithm. Thus in this time we can solve the problem of deciding for a fixed value L if the graph has a walk from A to B with average length not greater than L. How to use this fact to solve the original problem? Well, we can use binary search over all possible values of L, and for a fixed value of L we can solve the problem described above. Notice that since all weights of edges in the graph are within a range [1, 100], all possible values of L are also within this range. Moreover, since the required precision of the answer is to return it with absolute or relative error not greater than 10-6, we can stop binary search as soon as the range of valid values of L is reduced enough to fulfill this requirement. For more details please refer to author’s and tester’s solutions.

AUTHOR’S AND TESTER’S SOLUTIONS:

Tester’s solution can be found here.
Editorialist’s solution can be found here.

2 Likes
2

How did this solution pass the 2nd subtask but not the first subtask? By the way, is testcase 0 the sample subcase?

1 Like
3

Sample Tasks were not properly illustrated , wrong answers were given for sample tasks , language was incorrect "loops instead of self - loops " . On asking doubts about answer of second sample no one replied, this problem could have had much more submissions if the admin would have taken the pain of answering doubts and reviewing questions instead of just copy pasting the question…

1 Like
4

There is solution without binary search, main idea is to find cycle with smallest average: CodeChef: Practical coding for everyone.

ref: http://www.columbia.edu/~cs2035/courses/ieor6614.S16/mmc.pdf

3 Likes
5

Since weights are positive number then can we also use Dijkstra’s algorithm?

1 Like
6

Could someone please help in explaining the solution in the below link?:
While I am aware of the Bellman - Ford algorithm, the calculation of the shortest average path in the below solution is unknown to me.

https://www.codechef.com/viewsolution/11275296

7

@swamicoder, no you cannot use Dijkstra’s as the edge weights can be negative AFTER subtraction, as mentioned in the editorial.

8

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Scanner;
/**

  • Created by user on 29-05-2017.
    */

class Avg {

public static ArrayList<Float> pa = new ArrayList<Float>();

public static int n,edge,pathLength;

public static ArrayList<Integer> nodesTravelled = new ArrayList<Integer>();

public static boolean flag = false;

public static void main(String args[]) {

    int a,b;

    float minimum_val;

    Scanner input = new Scanner(System.in);

    ArrayList<Float> output = new ArrayList<Float>();

    int tc = input.nextInt();

    for(int j =0 ; j<tc ;++j) {  // iterate through to read inputs

        HashMap<Integer,HashMap <Integer,Integer>> paths = new HashMap<Integer,HashMap<Integer,Integer>>();

        minimum_val = 1000;

        pa = new ArrayList<Float>();

        flag = false;

        edge  = 0;

        pathLength =0;

        HashMap<Integer, Integer> pathsFound = new HashMap<Integer, Integer>();

        int m = input.nextInt();

        n = input.nextInt();

        //paths -> Map with key as node and value as another hashmap connecting node and value weight

        for (int i = 0; i < n; ++i) {

            int node = input.nextInt();

            HashMap<Integer, Integer> tmpMap = new HashMap<Integer, Integer>();

            if(paths.get(node)!= null) {

                tmpMap = paths.get(node);

            }

            tmpMap.put(input.nextInt(), input.nextInt());

            paths.put(node, tmpMap);

        }

        a = input.nextInt();

        b = input.nextInt();

        if (!findMinAvgPath(a, b, paths) || paths.get(a) == null) {

            output.add(-1F);

        } else {

            for (Float t : pa) {

                if (t < minimum_val) {

                    minimum_val = t;

                }

            }

            output.add(minimum_val);
        }

    }
    for(float out : output) {

        if(out == -1F)

            System.out.println("-1");

        else

            System.out.println(out);

    }
}
public static boolean findMinAvgPath(int a, int b, HashMap<Integer,HashMap <Integer,Integer>> paths) {
    for(int node : paths.get(a).keySet()) {
        pathLength = pathLength + paths.get(a).get(node);
        edge++;
        if(node == b){
            flag = true;
            pa.add((float)pathLength/edge);
        }
        else {
            findMinAvgPath(node,b,paths);
        }
        pathLength = pathLength - paths.get(a).get(node);
        edge--;

    }
    return flag;
    }

}

I recently started programming. This code is failing at runtime. Could anyone check if 1) the logic i have used is correct . 2)Why is it failing during runtime.