FastPrepFastPrep
Problem Brief

Eric's Sequence

NEW GRADOA

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

  1. No two (not necessarily distinct) elements a[i] and a[j] sum to 0, and
  2. 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.

1Example 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].

2Example 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

Limits and guarantees your solution can rely on.

  • 1 <= n <= 100,000
public int[] findSequence(int n, int[] p) {
  // write your code here
}
Input

n

3

p

[3, 2, 3]

Output

[2, -1, 3]

Sign in to submit your solution.