SWEGARR - Editorial

ad-hoc
cobl2016
easy
editorial
sorting
sweg
swegarr
swegwan

#1

PROBLEM LINK:

Contest
Practice

Author: Haresh Khanna
Tester: Vaibhav Daga
Editorialist: Haresh Khanna

Difficulty:

Easy

Prerequisites:

Arrays, Sorting, Sweg

PROBLEM:

Given an array A of size N and each element of the array lies in the range [L,R] (inclusive). You have to choose exactly one integer from the array and replace it with another integer that also lies in the range [L,R] inclusive. You necessarily have to change a number and you can’t change a number with itself. After the replacement sort the array and output the minimum integer that could occur at each position after the replacement and sorting.

EXPLANATION:

It is clear from the problem statement that we have to choose a number then change it to some number in in range of [L,R] and then sort the array and output. Now in the first place there are ‘n’ numbers that can be replaced and (R-L-1) possibilities for each. Now we will get the minimum at each position when we replace the maximum number of the array Amax by the minimum number in [L,R] i.e. L. This can be achieved by first sorting. Let the sorted array be called B. Now print “L” followed by the n-1 numbers from B[0] to B[n-2]. This effectively means replacing B[n-1] (max element of A) by L and printing the sorted array A after the replacement, which is the required answer.

But there are fails in this approach considering the fact that a number needs to be replaced necessarily and it can not be replaced by itself. So the two fails are:

  1. All the numbers of the given array are L and L!=R: In this case after sorting, in array B, B[n-1] will be L and if we apply the previously discussed approach we will end up not replacing anything. So to cover this case and consider we have to replace necessarily we replace B[n-1] with L+1 and output the array B.

  2. L is equal to R: In this case, all the number of the array are equal to L and any number can not be changed as there is no number in [L,R] except L itself. So “-1” needs to be printed.

Time Complexity:

O(n*log(n))

AUTHOR’S SOLUTION:

Author’s solution can be found here