PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name
DIFFICULTY : BEGINNER
PREREQUISITES:
Nill
PROBLEM:
Emma’s family made a sudden plan to go for a picnic. But Emma has to submit her tutorial question’s solution in Google Classroom within 3 hours. The sooner she completes her tutorial, the sooner they can go out. Her family wants to help her finish it faster, but they are over their heads. Can you help Emma’s family to understand the question so that they could make it faster? Consider a list of n distinct integers, L =[L[0], L[1],…., L[n-1]] . They can swap any two elements of the list any number of times. A list is perfect if the sum of |L[i]-L[i-1]| among 0 < i < n is minimal. Given the list L , determine and return the minimum number of swaps that should be performed in order to make the list perfect. For example, L=[24,16, 59, 5]. One minimal array is [5, 16, 24, 59]. To get there, they performed the following swaps: Swap Result [24, 16, 59, 5]
5 24 [5, 16, 59, 24]
24 59 [5, 16, 24, 59]
It took 2 swaps to make the list perfect. This is minimal among the choice of perfect lists possible. Function Description Complete the emmastutorial function in the editor below. It should return an integer that represents the minimum number of swaps required. emmastutorial has the following parameter(s): L : a list of n integers
Input:
The first line contains a single integer, n , the number of elements in L. The second line contains n space-separated integers L[i].
Output:
Return the minimum number of swaps needed to make the list perfect.
Constraints
1 ≤ n ≤ 105
1 ≤ L[i] ≤ 2 X 109
Sample Input:
4
2 5 3 1
Sample Output:
2
QUICK EXPLANATION:
We can find the solution by finding the no. of swaps required to sort the list both in ascending & descending order and answer is the minimum of both.
EXPLANATION:
First of all, we should get the required input from the user and store the numbers in an array. Let’s name it A. Now store the current positions of each element in some data structure. For example if you are using Python language, you can store the index of each element before swapping in a dictionary. Now sort the list in ascending order and then compare the unsorted & sorted lists. Wherever elements aren’t the same, increment the no. of swaps and swap the indices in the dictionary. Repeat the same after sorting the list in descending order. The least no. of swaps required is the final output.
SOLUTIONS:
Setter's Solution
def solution(a):
m = {}
for i in range(len(a)):
m[a[i]] = i
sorted_a = sorted(a)
ret = 0
for i in range(len(a)):
if a[i] != sorted_a[i]:
ret +=1
ind_to_swap = m[ sorted_a[i] ]
m[ a[i] ] = m[ sorted_a[i]]
a[i],a[ind_to_swap] = sorted_a[i],a[i]
return ret
raw_input()
a = [int(i) for i in raw_input().split(’ ')]
asc=solution(list(a))
desc=solution(list(reversed(a)))
print min(asc,desc)
Tester's Solution
Same Person
Editorialist's Solution
Same Person