FastPrepFastPrep
Problem Brief

Energy Crisis

OA

In an interstellar civilisation, symbolised by a connected, undirected graph of n celestial bodies and m cosmic pathways. Each celestial body represents an alien entity, and each cosmic pathway (i, j) signifies an alliance between alien entities i and j.

In this cosmic civilisation, entity i harnesses an energy level e_i. Alien entity j feels eclipsed by entity i if e_j equals e_i + 1, implying entity j possesses exactly one more unit of energy than entity i.

The civilisation is termed as having a stellar gradient if in every allied pair, one entity feels eclipsed by the other. For some alliances, it's known which entity feels eclipsed by its ally. However, the direction of the eclipse remains unknown for the rest.

The energy disparity in this civilisation is defined as min e_i - max e_j 1 ≤ i ≤ n 1 ≤ j ≤ n

It's impossible for this civilisation to exhibit this stellar gradient with the known data, such a situation should be reported. Otherwise, a distribution of energy that fulfils the conditions for a stellar gradient should be determined and within this structure, energy disparity should be maximised.

Answer the maximum stellar gradient possible for the planet system. If no such configuration possible return -1.

1Example 1

Input
n = 6, edges = [[5, 6, 1], [3, 4, 0], [1, 4, 0], [4, 6, 0], [5, 1, 0], [4, 2, 1]]
Output
3
Explanation

The maximum stellar gradient possible for the planet system is 3.

2Example 2

Input
n = 5, edges = [[4, 3, 1], [3, 5, 1], [2, 4, 0], [1, 2, 1], [5, 1, 1]]
Output
-1
Explanation

No such configuration is possible, hence the output is -1.

Constraints

Limits and guarantees your solution can rely on.

  • The number of planets, 1 ≤ n ≤ 200
  • The number of cosmic pathways, 1 ≤ m ≤ 2000
public int maximizeStellarGradient(int n, int[][] edges) {
  // write your code here
}
Input

n

6

edges

[[5, 6, 1], [3, 4, 0], [1, 4, 0], [4, 6, 0], [5, 1, 0], [4, 2, 1]]

Output

3

Sign in to submit your solution.