ANUARM - Editorial

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[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[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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

9 Likes

where is the practice link? Btw nice question. :slight_smile:

2 Likes

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)|)?

Please help me find the reason for WA
link:
http://www.codechef.com/viewsolution/6397057

Please help me find the reason for wrong answer.
https://www.codechef.com/viewsolution/14065014

Good question,btw i am unable to comment! how do i gain upvotes when i can neither write a comment or pose a question?

Please can you provide what is output to this input
1
6 3
2 3 0

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?

The Practice Link

You are not printing a space after each number

3 2 2 3 4 5

Thanks good.

CAN SOMEONE TELL ME
what’s wrong in this solution?

#include <stdio.h>

int left_array(int question_array[] , int position)
{
int i;
for(i = position -1 ; i>=0 ; i–)
{
question_array[i] = question_array[i+1] +1;
}
}

int right_array(int question_array[] , int position, int size )
{
int i;
for(i = position+1 ; i<size ; i++)
{
question_array[i] = question_array[i-1]+1;
}
}

int question(int question_array[] , int position , int size)
{
question_array[position] = 0;
left_array(question_array , position);
right_array(question_array , position , size);
}

int checking(int question_array[] , int answer_array[] , int size)
{
int i;
for(i = 0 ; i<size ; i++)
{
if(question_array[i]>= answer_array[i])
{
answer_array[i] = question_array[i];
}
}
resetting_array(question_array , size);
}

int resetting_array(int question_array[] , int size)
{
int i;
for(i = 0 ; i<size ; i++)
{
question_array[i] = 0;
}
}

int main(void) {
int cases;
scanf("%d",&cases);
while(cases–)
{
int size , rounds;
scanf("%d %d" ,&size,&rounds);
int a[rounds] , i;
int question_array[size] , answer_array[size];

   for(i = 0 ; i<size ; i++)
   {
       question_array[i] = answer_array[i] = 0;
   }
   for(i = 0 ; i<rounds ; i++)
   {
       scanf("%d" , &a[i]);
   }
   
   for(i = 0 ; i<rounds; i++)
   {
       question(question_array , a[i] , size);
       checking(question_array , answer_array , size);
   }
   
   for(i = 0 ; i<size ; i++)
   {
       printf("%d " , answer_array[i]);
   }

}

return 0;

}

Can anyone please help me why am I getting wrong answer for this solution?
Thanks in advance.

https://www.codechef.com/viewsolution/34996362