# MNMX - Editorial

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

11 Likes

Have a look at my code

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

(Solved for You)

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?``````

Hello Karthik ,I think your logic is little wrong.
Let say your array is as shown below.
9 1 2 5 3 0 – - the ans should be 0 but your code is gives 4.
I think your code is working fine if the smallest number lies within 0th or 1st index(as in case of the provided Example test case), It fails once the smallest element is placed in 2nd position of array and so on.

your ans is only finding the cost, but in question it is given that we have to find the minimum cost , see…
suppose 5, 4, 3 are the numbers so your solution will give ( 5 > 4) = 4, ( 4 > 3 ) = 3
so cost = 4 + 3 = 7
but the minimum cost must be 6 as (4 > 3) = 3 , and (5 > 3) = 3
cost( min ) = 3+3 =6
so better first you find the smallest element.

#include <stdio.h>

int main(void) {
int testcases;
scanf("%d",&testcases);
while(testcases–){
int elements;
int testnumber;
scanf("%d",&elements);
int no_of_elements = elements;
if(no_of_elements >= 1){
scanf("%d “,&testnumber);
no_of_elements–;
}
while(no_of_elements–){
int number;
scanf(”%d",&number);
if(number<testnumber){
testnumber = number;
}
}
printf("%d\n",testnumber*(elements-1));
}
return 0;
}

/the code above is partially correct can some one suggest why my code is partially correct for this problem …/

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{

``````    long long  int n;
cin>>n;
long long int a[n],i,sum=0;
for(i=0;i<n;i++)
{
cin>>a[i];
}

long long int min = a[0];

for(i=1;i<n;i++)
{
if(min>a[i])
min = a[i];

sum+=min;
}

cout<<sum<<endl;
}
return 0;
``````

}

what is wrong with this code??? can anyone tell??

I think there is one trick to solve this problem very easily, for that we first have to store the elements in vector or array, than we have to find the element with minimum value and the answer will be minimum element value multiplied by the size of vector - 1
#include

#include

#include

using namespace std;

int main(){

``````int t;

vector <int> vec;

cin>>t;

while (t--)

{

int n,e;

cin>>n;

for (int i = 0; i < n; i++)

{

cin>>e;

vec.push_back(e);

}

int min;

cout<<vec[0]*(vec.size()-1)<<endl;

vec.clear();

}

return 0;
``````

}

Java integer supports range from
`-2147483648 to 2147483647`
And given constraints for Elements of Array was
`1 ≤ Ai ≤ 10^5` which can easily be stored in an `Integer type Array`, but no, it was giving wrong answer, but when i switched to `Long type Array`, my answer get Accepted.
Can anyone tell me whats wrong here, the constraints were false or there is any other problem?

You might want to read this.

CodeChef: Practical coding for everyone : why am I getting TLE in 3rd part of the problem?
Can someone correct my code?
Thanks.

Aside from your TLE issue, this code will not yield the required results as you are not able to identify the minimum cost for the operations.

Given in this array [5,7,2,4,1] the minimum cost should be 4 because:
[5,7,2,4,1] = sum += min(4,1) – which is 1
[5,7,2,1] = sum += min(2,1) – which is 1
[5,7,1] = sum += min(7,1) – which is 1
[5,1] = sum += min(5,1) – which is 1

Therefore sum = 4
Try to refactor your code to identify which is the best pair to calculate first

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

using namespace std;

int main(){
int testcase;
cin >> testcase;
while(testcase–){
int n;
cin >> n;
int a[n],cost=0,small;
for(int i=0;i<n;i++){
cin >> a[i];
}
for(int i=1;i<n;i++){
if(i==1){
if(a[i-1]<a[i]){
small=a[i-1];
cost += small;
}
else{
small=a[i];
cost += small; }
}
else{
if(small>a[i]){
small=a[i];
cost += small;
}
else cost += small;
}
}
cout << cost << endl;
}
return 0;
}
What’s wrong with this code?

``````
int main(void) {
int testCase;
scanf("%d", &testCase);
while(testCase--) {
int arraySize, i, minCost;
scanf("%d", &arraySize);
int array[arraySize];
for(i = 0; i < arraySize; i++)
scanf("%d", &array[i]);
minCost = array[0];
for(i = 0; i < arraySize - 1; i++)
if(array[i] > array[i+1])
minCost = array[i+1];
printf("%d",minCost*(arraySize-1));
}
return 0;
}
``````

What is wrong with this solution?

this is my solution

/“We have two choices when we wake up in the morning:
either we go back to sleep and dream,
or we wake up and chase that dream.”
/

#include <bits/stdc++.h>

using namespace std;
#define ll long long int
#define F first
#define S second
#define pb push_back
#define si set
#define vi vector
#define pii pair <int, int>
#define vpi vector
#define vpp vector <pair<int, pii>>
#define mii map <int, int>
#define mpi map <pii, int>
#define spi set
#define E endl
#define sz(x) ((int) x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define C cout

int main(){
int t ;
cin>>t;
while(t–){
ll n;
cin>>n;
vi v(n);
for(auto &x:v){cin>>x;}
sort(all(v));
ll cost=v[0]*(n-1);
C<<cost<<E;
}
return 0;
}