Help needed in solving MINIMUM SUM PROBLEM from hackerearth.
Imagine you are given two sets of numbers A and B, and your goal is to minimize the sum of A by swapping values at most K times between A and B. There is a simple greedy approach for this.
Now, consider a contiguous range on array X from i to j as [i, j]. Then consider everything within [i,j] as A, and everything outside it as B. Applying the algorithm from earlier on this A and B gives the minimum possible subarray sum in range [i, j] using at most K swaps. Now the overall minimum must be exist for some [i, j]. So just try this for all ranges, and choose the minimum from them all to get the answer 
2 Likes
Okay, give me some time.
Take your time
Here is my code with comments. Get back to me if you have any doubts-
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
//This is a brute-force solution by spirit. It runs in O(N^3 logN time).
bool comp(int a, int b)
{
return a>b;
}
int main() {
// your code goes here
#ifdef JUDGE
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n,k,j,l;
cin>>n>>k;//An attempt to take input is made here....
int i,arr[n];
vector<int> negative;//This will store all negative elements in array-For cases when k>>n
for(i=0;i<n;i++)
{
cin>>arr[i];
if(arr[i]<0)
negative.push_back(arr[i]);
}
sort(negative.begin(),negative.end(),comp);
int minsum=0;//This var will later store "current subarray's sum". Please dont go by its name.
if(negative.size()==0)
{
sort(arr,arr+n);//If all elements >0, return the smallest element.
cout<<arr[0]<<endl;
continue;
}
int swap=k;//Swap stores number of allowed swaps. Changed variable as I have habit of using k as a loop variable
int TotalMin=1000000000;//Stores minimum sum encountered till now, among all sub arrays seen
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)//First and 2nd loop generate all sub arrays
{
vector<int> in, out;//In=element in sub array, out=element out of sub array
//DO NOT DECLARE THESE 2 VECTORS OUT OF LOOP!! IMMEDIATE WA!!
minsum=0;
int allowed=swap;//allowed= number of swaps allowed
for(k=0;k<n;k++)
{
if(k>=i && k<=j)
{
in.push_back(arr[k]);
minsum+=arr[k];//Storing elements in respective vectors
}
else
out.push_back(arr[k]);
}
sort(in.begin(),in.end());
sort(out.begin(),out.end());
int index=0;
int l;
for(l=in.size()-1;l>=0 && index<out.size() && allowed>0;l--)
{
/*
Note that, after sorting, the largest value in vector "in" is stored at end
and smalles value of vector "out" is at start.
*/
if(in[l]>out[index])
{
/*
If swapping values lowers the sum of this sub array, swap.
*/
minsum-=in[l];
minsum+=out[index];
index++;
allowed--;//Reduce allowed swaps by 1
}
else
break;
/*
See how we are traversing both the vectors.
If this value of in[l] is less than out[index], then so will
future values we are traversing in[l] from highest to lowest and out[index]
from lowst to highest. So break out to optimize code.
(BTW, this can be skipped, but its good to optimize code as much as you can.)
*/
}
TotalMin=min(TotalMin,minsum);
}
}
cout<<TotalMin<<endl;//An attempt to print ans is done here :D
}
return 0;
}Is it entire code or just some portion of code? The logic is same as @meooow told, thats why i didnt mention anything except comments.
In a gist, if the array has only positive values, then we print the smallest element, as thats the sub array with least sum.
If array has negative elements as well, then we generate all sub arrays and check. LEt a sub array start from index i and end at index j. I made 2 vectors, in and out, which stored the elements which are inside the sub-array and which are outside the sub-array respectively.
Now, I sort both the vectors.
Now, we make another loop. Notice that after sorting, vectors are in ascending order. Also, we should realize that greedy approach works here (Swap the largest element in sub array with minimum element outside the sub array to minimize sum).
So we do the follow-
For every element in the sub-array (or inside vector âinâ), we start from greatest one. If this element is greater than the âleast-valued element outside the subarrayâ then we swap and update the sum, else we simply break out of loop.
(Both arrays are in ascending order. If largest element in subarray (or inside vector âinâ) is less than smallest element outisde sub-array (or inside vector âoutâ), then its obvious that other elements in vector âoutâ will be greater as well and swapping will only increase the sum).
Its like, generate all sub-arrays, then for every sub-array generated, check if replacing largest element in sub-array with smallest element outside sub-array minimizes the sum or not. If yes, then swap, update, and check same for second largest element in sub-array. If no, then sub-arrayâs sum is already minimum.
We store the smallest sum encountered and print it as an answer.
I understood your logic. But before this loop
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)//First and 2nd loop generate all sub arrays
explain me the purpose of the code before this code.
Actually, the code above it can be ignored as those nested for loops in latter part of code are capable of giving right ans by itself.
I first thought of a different algo, but realized mid way that it wont work. But for some reason didnt delete that part out, instead used the negative vector for something else.
The only thing you need to get is that, if array has no negtive element, then sub array of length 1 with minimum element is the ans. That part of code checks for this, every other thing like sorting that negative vector can be ignored. Sorry for confusion.
vector<int> in, out;//In=element in sub array, out=element out of sub array
It will cause again and again allocation of memory every time, wouldnât it be slower. Why canât we declare them outside the loop and empty them at start of the loop.
You can do that. But if you simply declare them and dont clear it before every iteration, it will give WA.
Answering here since comment has limit 
I actually thought a lot on it, that if it can be solved in a more optimal way. Heres what I was able to come up with, but it can fail at some edge cases-
-
Check sub-arrays starting with negative integers. Lets say, at index i, arr[i] is negative. We mark it as starting point. Now, we start expanding. If the next element is positive, it needs to be swapped to minimize the sum, so if swap allows we swap it with the most negative integer. IF negative, we happily carry on taking it in sub-array.
-
Once we are out of swaps, we still check further if including future elements can lower the sum. Eg- take case of {1,-2,1,1,1,-5,-10}. Swap allowed=1. We can start from -2, swap a 1 with -10 {array becomes {1,-2,-10,1,1,-5,1}, and then go on till -5 for minimum possible sum.
-
But there are issues again. Like, lets say we take array {1,-2,1,-10,-5}. On encountering the â1â, it will swap it with -10, but in next step it will anyway include {1,-5} as its lowering the sum. We essentially wasted a swap by swapping an element in sub-array with an element which nevertheless ended up inside final sub-array.
In the end, there were quite lots of issues in optimizing the approach. So i decided to brute force it because of smaller constraints. Its the above mentioned approach why vector ânegativeâ was created and sorted, but on taking up certain cases i realized there are many loop holes here, and decided its best to go with brute force for accuracy and quick solution to your doubt.
We do not need to take care of the case where all the no. are positive it will be covered with nested loop, I think.
As i said earlier, its all optional. The nested loop is main part, and self sufficient.