Explanation to problem Minimum Maximum (MNMX)

general
, , , , ,
1

I was solving this particular problem in August Lunchtime challenge, but when I submitted the solution I got Wrong Answer. [(My submission code link.)][1]
[1]: https://www.codechef.com/viewsolution/7966283

My strategy to solve the problem is:

  1. Loop through the array.
  2. Select two adjacent integers.
  3. Find minimum of them and discard the other one.
  4. cost += min; (Cost of this operation will be equal to the smaller of them.)
  5. Display the cost.

I get testcases (mentioned on the problem page) as correct on my local IDE. But when I submit the solution I get WA.

As the contest ended, I went through the solution of other members, and I was confused with the following points:

  1. Challengers found out the minimum number in the array(so did I), but they did not increment the cost variable(as the constrain says Cost of this operation will be equal to the smaller of them.)
  2. At the end they have multiplied the smallest number in the array with (n-1) and displayed it as the final output.

Clearly I have misunderstood the problem statement(even after spending ample amount of time on it!). I request you geeks in sorting my problem, as why we are not supposed to increment cost variable with min number throughout the loop, what is the significance of min*(n-1)

2

Given that the cost of removing a pair is the value that is lesser than the two, we will greedily choose to remove the array by always forming a pair with the element that has the smallest value. Given that the smallest value will never be removed(by definition), for each possible pair only the minimum value will be added to the answer.

Given that there are N-1 possible candidates to pair with the minimum value, final answer is (N-1)*Minimum value.

Consider the array :

5 2 1 3 4

It changes to :

5 2 1 4 -> 5 2 1 -> 5 1 ->1

3

One awesome way to do it I found:
first convert all the enteries into the array and then to a sorted array .
Select first number or smallest number wand multiply it by the length of the array - 1. You get the answer simply

Want to check the code for it :
https://www.codechef.com/viewsolution/7951644

Now , coming to the fun part why this was done :

Obviously, the smallest number in the array would never be deleted ,so it was selected. Moreover , each operation on each two pairs considered it will cost less . We have to access all pairs ,so this could be done by the smallest one in the most efficient way so we did it…
Some examples to clarify:
consider array:
2 3 4 5

Now if we do select the second smallest integer 3 now we have to transverse through all integers greater than it:

2 3 5 (4 deleted so cost +3)

2 3(5 deleted so cost +3)

2 (3 deleted so cost (+2))

so all in all: total cost=8

Now if we go by the right way then:

2 3 4 5 (initially)

2 4 5(3 removed)

2 5(4 removed)

2(5 removed)

So total cost = 2*3=6 (i.e. lesser than 8)

So total cost == min(i.e 2)*n times transversal(i.e. len(array)-1)

so this is how I got it. Hope you understood.

4

The significance of min is that for each operation we use min as one of two and so as per problem statement larger will get discarded…and therefore the last element will be min which has been paired with n-1 elements…therefore min*(n-1).

5

An operation is defined as taking two numbers, adding the minimum number to the result and discarding the larger.

After all the operations, the minimum number remains no matter what. In the end, there will be one number left, so we do (n-1) operations.

As we have to minimize the cost, for every operation, we choose a pair, in which one number is the minimum number and other is the number adjacent to it.

If you think about it carefully, the best possible choice for minimizing cost is to choose a pair, such that the minimum number is always a part of it.

So, the total cost will be (n-1)*MIN_VAL.

1 Like
6

just apply QUICKSORT and then apply (len(array)-1)*array[0] thats it.