You are not logged in. Please login at www.codechef.com to post your questions!

×

# ANUARM - Editorial

Author: Anudeep Nekkanti
Tester: Constantine Sokol
Editorialist: Florin Chirica

Simple

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.

# 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[i] = 0 if i = pos
• numbering[i] = numbering[i – 1] + 1 if i > pos
• numbering[i] = numbering[i + 1] + 1 if i < pos

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

# Take general case

For general case, suppose pos, pos, ..., 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|, |i – pos|, ...., |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, pos, ..., 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, pos, ..., 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.

# AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

asked 20 Oct '14, 00:34 3★elfus ♦♦
0112527
accept rate: 0% 2.5k53137170

Getting access denied errors in XML when I open the Author's and Tester's solutions.

(20 Oct '14, 01:00)

What has the tester done in so much code?

(20 Oct '14, 10:26)

 1 where is the practice link? Btw nice question. :) answered 20 Oct '14, 05:34 407●2●7●19 accept rate: 7% The Practice Link (25 Oct '14, 15:45) vidudaya3★
 0 What is wrong with the below approach? For every M in the input calculate the maximum value of the left most guy(index 0)[leftMax] and right most guy(index n-1)[rightMax] At the end the maximum value assigned to guy at position i is maximum(|leftMax-i|,|rightMax-(n-1-i)|)? http://ideone.com/F5KyD8 answered 31 Dec '14, 06:31 1 accept rate: 0% You are not printing a space after each number (31 Dec '14, 23:34)
 0 Please help me find the reason for WA link: http://www.codechef.com/viewsolution/6397057 answered 05 Mar '15, 17:28 2★joel1794 1 accept rate: 0%
 0 Please help me find the reason for wrong answer. https://www.codechef.com/viewsolution/14065014 answered 04 Jun '17, 23:41 1 accept rate: 0%
 0 Good question,btw i am unable to comment! how do i gain upvotes when i can neither write a comment or pose a question? answered 27 Jan '18, 16:12 14●4 accept rate: 0%
 0 Please can you provide what is output to this input 1 6 3 2 3 0 answered 15 Feb, 22:59 2★gaut9a8m 1 accept rate: 0% 3 2 2 3 4 5 (16 Feb, 19:15)
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,191
×151

question asked: 20 Oct '14, 00:34

question was seen: 4,857 times

last updated: 16 Feb, 19:15