Swapping values between two vectors so that sum of max_elements of two vectors is minimum

Question

This is a question from Codechef but please bear with me. https://www.codechef.com/ZCOPRAC/problems/ZCO16001

The contest is for the preparation of the Zonal Computing Olympiad held in India, so its not a competitive contest from which I'd earn something as such. Just need a little help to see what is wrong with my code, because I have a feeling I've overlooked something big and stupid. :P

So basically the question is summed up as this.

Lets say that there are two vectors or arrays. You need to swap elements between them such that the sum of their maximum elements is minimum. However you can swap at most K times. Then output the value of this sum.

My approach was simple. Take the highest number from Vector1 (V1) and swap it with the lowest from V2. Add the highest values of each. Do the same, but this time swap the highest number from V2 with the lowest from V1. Add the highest values of each. The better swapping will be the one with the lowest sum and continue from there K times.

So for example:

V1 = 5 6 7 9

V2 = 9 10 5 4

In this case, if K = 1 I would first swap V1's 9 with V2's 4. This gives:

V1 = 5 6 7 4

V2 = 9 10 5 9

Sum of highest number as 17, as compared to earlier's 19. The second swap I could do is 10 from V2 with 5 from V1 giving:

V1 = 10 6 7 4

V2 = 9 5 5 9

This gives sum as 19, so better was the first swap and the output should be 17.

Here is my solution:

#include <iostream>
#include <vector>
#include <algorithm>
#define print(vec) for (int i  = 0; i < vec.size(); i++) { cout << vec[i] << " "; } cout << endl;
using namespace std;

vector <long long int> s1, s2;

inline long long int calc(vector <long long int> v1, vector<long long int> v2) {
    return *max_element(v1.begin(), v1.end()) + *max_element(v2.begin(), v2.end());
}
int main(){


    long long int n, k;
    cin >> n >> k;
    long long int x;
    for (unsigned int i = 0; i < n; i++) {
        cin >> x;
        s1.push_back(x);
    }
    for (unsigned int i = 0; i < n; i++) {
        cin >> x;
        s2.push_back(x);
    }
    while (k--) {

        vector <long long int> b1(s1);
        vector <long long int> b2(s2);
        long long int skewb = calc(b1,b2);

        vector <long long int> v1(s1);
        vector <long long int> v2(s2);

        auto mn1 = minmax_element(v1.begin(), v1.end());
        auto mn2 = minmax_element(v2.begin(), v2.end());

        iter_swap(mn1.second, mn2.first);

        b1 = vector <long long int> (v1);
        b2 = vector <long long int> (v2);
        skewb = calc(v1,v2);

        v1 = vector <long long int> (s1);
        v2 = vector <long long int> (s2);
        mn1 = minmax_element(v1.begin(), v1.end());
        mn2 = minmax_element(v2.begin(), v2.end());

        iter_swap(mn2.second, mn1.first);
        if (calc(v1,v2) <= skewb) {
            b1 = vector <long long int> (v1);
            b2 = vector <long long int> (v2);
        }

        if (b1 == s1 && b2 == s2) cout << "LOL" << endl;
        s1 = vector <long long int> (b1);
        s2 = vector <long long int> (b2);
    }



    cout << calc(s1, s2) << endl;
}

Please note that this does all swaps i.e K. So even if the current arrangement was the best, it would still swap some values. Earlier I was breaking when the current arrangement was the best. The reason for doing this is because I was getting all test cases right except TWO! And guess what was even more annoying, one was from each task! :( So I realised it must be necessary to complete all K switches. However even now I am getting 2 testcases wrong, there must be something I have overlooked.

Any idea what it is? Link to solution: https://www.codechef.com/viewsolution/11574501

And btw, Task 1 has K = 1.

Answer 1

The problem with your code is you change the arrays between swaps and therefore there is the possibility of swapping one item back and forth between arrays. I mean in the first swap you place element x from array1 to array2 and in the next swap it is possible that you swap it back again.

Also you do a lot of vector copying which make the code inefficient. Even if the logic of your code was correct your code wouldn't have passed the time limit because your approach is O(n²).

---

First note that optimal answer is when all the elements in one array are bigger than all the elements in the other array.

• Sort both arrays
• for x from 0 to k
  • hypothetically swap x minimum elements of first array with x maximum elements of the second array.
  • result = min(result, max(result, max(first array) + max(second array) )
  • hypothetically swap x maximum elements of first array with x minimum elements of the second array.
  • result = min(result, max(result, max(first array) + max(second array) )
• result will hold the final answer

Since both arrays are sorted you can find maximum elements of the arrays after hypothetical swap with one comparison.

V1 = 5 6 7 9 -> 5 6 7 9
V2 = 9 10 5 4 -> 4 5 9 10

x = 0   no swaps: result = V1[size-1] + V2[size-1]
x = 1 
        result = max(V1[size-1], V2[size-1]) + max(V1[0], V2[size-2])
        result = max(V1[size-2], V2[0]) + max(V1[size-1],V2[size-1])
x = 2 
        result = max(V1[size-1], V2[size-1]) + max(V1[1], V2[size-3])
        result = max(V1[size-3], V2[1]) + max(V1[size-1],V2[size-1])
...

This is the accepted implementation:

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;


int main()
{
    int n,k;
    cin>>n>>k;

    vector<int> v[2];
    for ( int i=0;i < 2;++i ){
        for ( int j=0;j<n;++j ){
            int temp; cin>> temp;
            v[i].push_back(temp);
        }
    }

    sort(v[0].begin(),v[0].end());
    sort(v[1].begin(),v[1].end());

    int result = v[0].back() + v[1].back();

    for ( int i=1; i<=k; ++i ){
        int t = max(v[0][n-1],v[1][n-1]) + max(v[0][i-1],v[1][n-1-i]);
        result = min(result,t);
        t = max(v[0][n-1-i],v[1][i-1]) + max(v[0][n-1],v[1][n-1]);
        result = min(result,t);
    }

    cout << result << endl;
}