### PROBLEM LINK:

**Author:** Anudeep Nekkanti

**Tester:** Constantine Sokol

**Editorialist:** Florin Chirica

### DIFFICULTY:

Simple

### PREREQUISITES:

none

### PROBLEM:

You have M vectors of length N. Each vector is defined by a position pos. Array on position i is pos – i if i <= pos and i – pos if i > pos. For each position, find maximum of values of all M vectors.

### QUICK EXPLANATION

It turns out it’s enough to calculate minimal and maximal value of all M positions. For an index i, the answer is max(|i – minimal_position|, |i – maximal_position|), where |x| is absolute value of x.

### EXPLANATION

# Special case of M = 1

A good start is to see what happens if M = 1. Suppose selected position by the captain is pos. Then,

- numbering* = 0 if i = pos
- numbering* = numbering[i – 1] + 1 if i > pos
- numbering* = numbering[i + 1] + 1 if i < pos

where numbering is the resulting array. We can see that if i > pos, numbering* = i – pos and if i < pos, numbering* = pos – i. But this is the definition of absolute value. So numbering* = |i – pos| (where by |x| I denote absolute value of x).

# Take general case

For general case, suppose pos[1], pos[2], …, pos[M] are positions asked by the captain during the M rounds. For each i (0 <= i < N) you need to output max(|i – pos[1]|, |i – pos[2]|, …, |i – pos[M]|).

So now let’s calculate for a particular i (let’s forget for a moment we need to iterate each i, we’re interested only in a single value of i). Let’s maximize |i – a|, where a can be pos[1], pos[2], …, pos[M]. A property of absolute value says that |i – a| = max(a – i, i – a). So if we maximize the expressions (a – i) and (i – a), then take their maximum value, we’re done for the given i.

In both expressions i is a constant (since we’ve decided to calculate only for a particular value of i). Since i is constant, it can’t influence maximization. So we need to maximize (a) and (–a). Now it’s obvious we need to take maximum and minimum between pos[1], pos[2], …, pos[M]. Let max_value be the maximum and min_value be the minimum. The answer for a fixed i is max(max_value – i, i – min_value).

The only remained thing is to iterate over all possible i. We calculate at the beginning max_value and min_value, then we iterate i and print max(max_value – i, i – min_value).

# Time Complexity

The algorithm solves each test in O(N + M) time complexity.