Uber OA 2023 - Minimum Score

Problem Description

You are given a 1-indexed array of size N and need to construct a directed graph from this array such that it satisfies the following conditions:

1. Any directed edge between two nodes will have a value that defines the distance between those two nodes. These values can also be negative.
2. There should be connectivity between every pair of nodes, meaning there should be a path of edges that connects every pair of nodes in the graph.
3. The minimum distance from node 1 to node i should be equal to arr[i]. It is given that arr[1] will always be 0.

The score of a graph is defined as the sum of the values of the directed edges in the graph. Your task is to output the minimum score you can achieve by generating any graph that satisfies the above conditions.

Input Format

• An integer n: The number of nodes in the graph.
• An array of integers arr of size n: Where the ith node represents the distance of node i from node 1. The value will always be 0 for the root node.

Output Format

• An integer64: The minimum score of the graph.

Constraints

• 1 ≤ n≤ 100,000
• 0 ≤ arr[i] ≤ 10^9, where arr[1]=0
• The execution time limit is 0.5 seconds (C++).
• The memory limit is 1 GB.

Sample Test Case

Input

n = 2
arr = [0, 2]

Output

0

Explanation

Two edges can be formed where the value of the edge from 1 to 2 is 2, and the value from 2 to 1 is -2. This graph satisfies all the conditions mentioned, and the sum of the edge values will be 0.