FastPrep
Problem · Graph

Energy Crisis

Learn this problem
● HardRubrik logoRubrikOA

Problem statement

You are given a connected undirected graph with energy e[i] assigned to each vertex. Every edge must connect vertices whose energies differ by exactly 1.

Each row [u, v, flag] has one of two meanings:

  • If flag = 1, the direction is fixed and must satisfy e[v] = e[u] + 1.
  • If flag = 0, either e[v] = e[u] + 1 or e[u] = e[v] + 1 is allowed.

If no assignment satisfies every edge, return -1. Otherwise return the maximum possible disparity max(e) - min(e).

Function

maximizeStellarGradient(n: int, edges: int[][]) → int

Examples

Example 1

n = 6edges = [[5, 6, 1], [3, 4, 0], [1, 4, 0], [4, 6, 0], [5, 1, 0], [4, 2, 1]]return = 3

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

Example 2

n = 5edges = [[4, 3, 1], [3, 5, 1], [2, 4, 0], [1, 2, 1], [5, 1, 1]]return = -1

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

Constraints

  • The number of planets, 1 ≤ n ≤ 200
  • The number of cosmic pathways, 1 ≤ m ≤ 2000

More Rubrik problems

drafts saved locally
public int maximizeStellarGradient(int n, int[][] edges) {
  // write your code here
}
n6
edges[[5, 6, 1], [3, 4, 0], [1, 4, 0], [4, 6, 0], [5, 1, 0], [4, 2, 1]]
expected3
checking account