PROBLEM LINK:Author: Anudeep Nekkanti 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 EXPLANATIONIt 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. EXPLANATIONSpecial case of M = 1A good start is to see what happens if M = 1. Suppose selected position by the captain is pos. Then,
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 caseFor 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 ComplexityThe 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

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 n1)[rightMax] At the end the maximum value assigned to guy at position i is maximum(leftMaxi,rightMax(n1i))? http://ideone.com/F5KyD8 answered 31 Dec '14, 06:31

Please help me find the reason for WA link: http://www.codechef.com/viewsolution/6397057 answered 05 Mar '15, 17:28

Getting access denied errors in XML when I open the Author's and Tester's solutions.
What has the tester done in so much code?