MNMX - Editorial

editorial
, , ,
1

PROBLEM LINK

Practice

Contest

Author: Sunny Aggarwal

Tester: Alex Gu and Pushkar Mishra

Editorialist: Prateek Gupta

Russian Translator: Vitalij Kozhukhivskij

Vietnamese Translator: Khanh Xuan Nguyen

Mandarian Translator: Gedi Zheng

Contest Admin: Praveen Dhinwa and Pushkar Mishra

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given an array of size N, you have to reduce the array into a single element by repeatedly applying a single operation.
The operation involves picking up two adjacent elements in the array and remove larger of them by paying a cost equal to smaller of them. Minimize the total cost.

EXPLANATION

Solution for Subtask 1:

This subtask can indeed be solved by Bit Masking DP. Check this link to know more about Bit Masking.
In this case, we maintain a state F(mask) where in, set bits of mask represent which all indexes have been removed uptill now. We want to arrive at a state where only the last element i.e only 1 unset bit remains in the final array. The last index remaining will always be the position of minimum element in the array regardless of the order of applied operations. Lets look at the pseudo code to understand how this recurrence works.

F(mask) {
   if ( __builtin_popcount(mask) == n-1 ) return 0
   long long ans = 0
   for ( int i = 0; i < n; i++ ) {
       if ( !(mask & (1<<i)) ) {
            int j = i+1
            while ( j < n && (mask&(1<<j)) ) j++ 
            if ( j != n ) {
                int remove_idx = (A[i] > A[j]) ? i : j
                ans = min(ans, min(A[i],A[j]) + f(mask | (1<<remove_idx)) )
            }
       }
   }
   return ans
}

Basically, at any particular state, we are checking what all indices are there which have not been removed yet. So for this, we try to apply all kinds of X-1 operations for any X unset bits. We take a bit which is not set, lets call it i, we find the just next unset bit j, which would mean these two are consecutive elements at that particular state and hence, the greater of them can be removed. We do this for all such (i,j) pairs to take the minimum of all answers. Minimum value returned by calling function F(0) will hence be the minimum cost spent to convert the array into a single element. Overall Complexity for this naive approach is \mathcal{O}(2^N*N^2)

Solution for subtask 2 & 3:

In order to minimize the total cost, you should surely choose the pair of consecutive integers consisting of the smallest element in the given array. The minimum element will anyway be the last remaining element after all operations have been applied. So, why not choose a pair of consecutive numbers involving this minimum element till the whole array reduces to this minimum element. Since, we need to perform this operation N - 1 times, total cost incurred will hence be equal to (N - 1)*(MINVAL). As answer can be little large, use a data type which can handle larger numbers.

COMPLEXITY

As minimum value in the array can just be found in a single traversal, overall complexity of the solution is \mathcal{O}(N).

SOLUTIONS

Tester

1 Like
2

in JAVA

System.out.println(new BigInteger(n).subtract(new BigInteger(“1”)).multiply(new BigInteger(MINVAL)));

1 Like
3

i think my solution is a bit easier:

import java.util.*;

import java.lang.*;

import java.io.*;

class Codechef

{

public static void main (String[] args) throws java.lang.Exception {

	BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

	int t = Integer.parseInt(r.readLine());

	while(t-->0) {

	    int n = Integer.parseInt(r.readLine());

	    String[] s = r.readLine().split(" ");

	    long l = s.length;

	    long min = Long.parseLong(s[0]);

	    for(int i=0;i<(int)l;i++) {

	        if(Long.parseLong(s[i])<min) {

	            min = Long.parseLong(s[i]);

	        }

	    }

	    System.out.println((l-1)*min);

	}

}

}

4

My solution is as many have submitted and appears right,still got only 60 points? I got wrong answer for the last subtask,I don’t understand how.Can someone help?
https://www.codechef.com/viewsolution/7955688

5

In your solution n and min are integers. So, min*(n-1) overflowed.Typecast them to long long. I tried and got AC for your code

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

p.s. I encountered the exact problem in some contest a few months ago. Since then I use long long for all cases even if the chances of overflow is low

1 Like
6

i think its failing at " ans=min*(n-1); "

as min and n-1 both are int so their product will also be an int and it will be assigned to ans.
and in the product overflow will happen as its int only

do this

ans=(long long)min*(n-1);

7

thank you for the …

8

Can I find the reason why this program is giving wrong…
https://www.codechef.com/viewsolution/9195456

9

@karthik_bhata7 The question says to minimize the cost which can be done if u pick the smallest number and compare it with its consecutive number and adding the cost.
But in your solution, you haven’t selected the smallest so it will always give cost greater than the minimum cost.
e.g suppose 5, 4, 3 are the numbers so your solution will give ( 5 > 4) = 4, ( 4 > 3 ) = 3
so cost = 4 + 3 = 7
but if we pick the smallest and then start comparing ( 3 < 4 ) = 3, ( 3 < 5) = 3
so cost = 3 + 3 = 6

10

#include <stdio.h>

int main(void) {

int a[20],t,i,j,k,n;
scanf("%d",&t);
while(t--)
{
     scanf("%d\n",&n);
     for(i=0;i<n;i++)
     scanf("%d\n",&a[i]);
     for(j=0;j<n;j++)
     {
         if(a[j]>a[j+1])
         {
             k=k+a[j+1];
             n=n-1;
         }
         else
         {
             k=k+a[j];
             n=n-1;
         }
     }
     printf("%d\n",k);
     n=0;k=0;
   }


return 0;

}
what is wrong with this sol

11

Please Help Me…I have written code for this problem it also giving the desired output.But When i submitted it,It giving me wrong answer.Please Help Me.I am a beginner.Here is my solution
https://www.codechef.com/viewsolution/10613974

12

if the previous array elements where

5,8,9,2,5,4,6

the after deletion it will became say

5,8,2,5,4,6

so

now 8 and 2 will be considered adjacent

is it correct or not

1 Like
13

Yes, I think its correct.

14

Theoretical question: why is it that

cost=min*(n-1)

with

int min,n;
long long cost;

doesn’t work, but if all variables are long long it does?

Thanks

15

What is the problem with this code?

#include<stdio.h>
int main(){
long i, j, T, n, a, b;
long cost = 0;
scanf("%li", &T);

for(i = 1; i<=T; i++){
	scanf("%li", &n);
	scanf("%li", &a);
	cost = 0;
	
	for(j = 2; j<=n; j++){
		scanf("%li", &b);
		
		if(a>b){
			a = a + b;
			b = a - b;
			a = a - b;
		}
		
		cost+=a;
	}
			
	printf("%d\n", cost);
}

return 0;

}

16

You just need one observation, to select the pairs…

The answer of this problem is always be = (N-1)*Minimum element in array,

Consider array 5 7 3 1 15 16 7 9

optimal choice is always to select pair containing minimum element…

select 1 and 15, 15 removed incurring cost 1

resultant array 5 7 3 1 16 7 9, cost = 1

select 1 and 16, 15 removes for cost = 1

resultant array 5 7 3 1 7 9, cost = 2

Repeat this process, you’ll get array containing single element 1

Total number of elements removed = N-1, cost per removal = 1

So, Answer = (N-1)*minimum element

Please UPVOTE…

17

Have a look at my code

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

(Solved for You)

Please UPVOTE…

18

What if both the numbers are equal?

19

Can someone tell what wrong in this code, it is accepted but subtask 3 gets failed why?

package continueFromDefault;
import java.util.*;
public class MinimumAndMaximum {

public static void minAndmax(int arr[],int len)
{
	Arrays.sort(arr);
	
	int k = 0;
	
	for(int i=1;i<arr.length;i++)
	{
		k+=arr[0];
	}
	System.out.println(k);
}

public static void main(String[] args) {
	// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		
		int times = sc.nextInt();
		
		while(times-->0)
		{
			int len = sc.nextInt();
			
			int arr[] = new int[len];
			
			for(int i=0;i<len;i++)
			{
				arr[i] = sc.nextInt();
			}
			
			minAndmax(arr, len);
			
		}
}

}

20

cant I use only 2 variables

my solution

got WA