MNMX - Editorial

thank you for the …

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

@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

5 Likes

#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

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

1 Like

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

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

1 Like

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;

}

What if both the numbers are equal?

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);
			
		}
}

}

cant I use only 2 variables

my solution

got WA

What is wrong here except TLE(in subtask 3) ? I am curious … HELP !!

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();

	while(t-- > 0){
	    
	    int n = sc.nextInt();
	    ArrayList al = new ArrayList();
	    
	    for(int i=0;i<n;i++){
	        int x = sc.nextInt();
	        al.add(x);
	    }
	    
	    /*for(int i=0;i<n;i++){
	        System.out.println(al.get(i));
	    }*/
	    int sum = 0;
	    
	    while(al.size() > 1){
	        
	        if((int)al.get(0) > (int)al.get(1)){
	            sum = sum+(int)al.get(1);
	            al.remove(0);
	        }
	        else{
	            sum = sum+(int)al.get(0);
	            al.remove(1);
	        }
	        
	    }
	    
	    System.out.println(sum);
	}
	
}

}

1 Like

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

3 Likes

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

3 Likes

Yes, I think its correct.

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…

11 Likes

Have a look at my code

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

(Solved for You)

Please UPVOTE…

1 Like

In python 3, its just a half line code.
min(a)*(n-1)

#include<stdio.h>
#include<bits/stdc++.h>

using namespace std;

int main()
{

// #ifndef ONLINE_JUDGE
// freopen(“input.txt”, “r”, stdin);
// freopen(“output2.txt”, “w”, stdout);
// #endif

int cases;
scanf("%d", &cases);

while (cases--) {
    int num;
    scanf("%d", &num);
    int arr[num];
    int min = INT_MAX;

    for (int i = 0 ; i < num ; i++) {
        scanf("%d", &arr[i]);
        if (min > arr[i]) {
            min = arr[i];
        }
    }

    printf("%d\n", min * (num - 1));
}
return 0;

}

What’s wrong with this? I am not able to pass third cases. I used long long but it shows runtime overflow. Please help

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#define ll long long
#define PI 3.14
#define pb push_back
#define pop pop_back
#define MOD 1000000007
#define fi first
#define se second

using namespace std;

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
    vector<ll>v1;
    vector<ll>::iterator it;
    vector<ll>::iterator it1;
    ll n,x,cnt=0;
    cin>>n;
    while(n--)
    {
        cin>>x;
        v1.push_back(x);
    }
    while(v1.size()!=1)
    {
         it=v1.begin();
        it1=v1.begin()+1;
    cnt=cnt+min(v1[0],v1[1]);
   
    if(*it>*it1)
    {
        v1.erase(it);
    }
    else
    v1.erase(it1);
  
    
    }
    cout<<cnt<<endl;
}
   
 

 return 0;
}
```what is wrong  in this method?