FastPrep

Description

Solutions

Eric's Sequence

👩‍🎓 NEW GRAD📚RELATED PROBLEMS

Eric has a sequence of non-negative integers p[0], p[1], ..., p[n-1], and he would like to find a sequence a[0], a[1], ..., a[n-1] of n distinct integers such that

No two (not necessarily distinct) elements a[i] and a[j] sum to 0, and
p[i] is equal to the number of indices j such that a[i] + a[j] > 0 for each 0 <= i < n.

If multiple such sequences exist, Eric wants one such that the maximum of the absolute values of the elements a[0], a[1], ..., a[n-1] is as small as possible.

Help Eric, find such a sequence, if possible.

Input:

n: A positive integer, the length of Eric's sequence.
p: A list of n non-negative integers representing Eric's sequence.

Output:

a: A list of n integers satisfying the restrictions given by Eric, including making sure the maximum of the absolute values of a[0], a[1], ..., a[n-1] is as small as possible. If there are still multiple such sequences, return any such sequence. If no such sequence exists, return None.

Example 1:

Input:  n = 3, p = [3, 2, 3]
Output: [2, -1, 3] 
Explanation:
      
      In this example, there are many such sequences a[0], a[1], a[2] that satisfy Eric's first two requirements, but one that minimizes the maximum absolute value of a[0], a[1], and a[2] is [2, -1, 3]. Another option is [3, -1, 2]. Both are acceptable outputs.
      
      
      While [4, -1, 3] also satisfies Eric's first two requirements, it does not minimize the maximum absolute value of a[0], a[1], and a[2].

Example 2:

Input:  n = 4, p = [1, 1, 1, 1]
Output: [] 
Explanation:
      
      It can be checked that there is no such sequence that satisfies Eric's requirements.

Constraints:

1 <= n <= 100,000