You are not logged in. Please login at www.codechef.com to post your questions!

×

Explanation to problem Minimum Maximum (MNMX)

I was solving this particular problem in August Lunchtime challenge, but when I submitted the solution I got Wrong Answer. (My submission code link.)
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)

asked 30 Aug '15, 22:36

aakash29's gravatar image

2★aakash29
11326
accept rate: 0%

edited 30 Aug '15, 22:38


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.

link

answered 30 Aug '15, 23:31

rishivikram's gravatar image

5★rishivikram
492110
accept rate: 14%

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

link

answered 30 Aug '15, 22:52

ironmandhruv's gravatar image

4★ironmandhruv
333239
accept rate: 20%

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.

link

answered 30 Aug '15, 23:12

hello1bye2's gravatar image

3★hello1bye2
11
accept rate: 0%

edited 31 Aug '15, 00:11

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

link

answered 30 Aug '15, 23:24

jainsuyogj's gravatar image

3★jainsuyogj
11
accept rate: 0%

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

link

answered 16 Oct '15, 00:20

bhargav431997's gravatar image

3★bhargav431997
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×820
×539
×217
×41
×32
×13

question asked: 30 Aug '15, 22:36

question was seen: 3,076 times

last updated: 16 Oct '15, 00:20