- Edited
I put the code neck to neck on my machine, compiled both in Release mode, both taking in arrays ranging from 1 to 10,000.
My program solves it with the following output:
It also got rid of those annoying "2" differences from the output.
Both programs have been changed to use 64-bit integers.
I am sorry MSD, but your program has yet to return :P
To change MSD's code, just replace int with long to handle those pesky large 100,000 values.
64-bit, arithma's code.
My program solves it with the following output:
shuffled
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
1000 steps done
2499975000 - 2499975000 = 0
It does so in less than a minute.It also got rid of those annoying "2" differences from the output.
Both programs have been changed to use 64-bit integers.
I am sorry MSD, but your program has yet to return :P
To change MSD's code, just replace int with long to handle those pesky large 100,000 values.
64-bit, arithma's code.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Solver{
vector<_int64> left;
vector<_int64> right;
_int64 lsum;
_int64 rsum;
Solver(vector<_int64> & v){
left.insert(left.begin(), v.begin(), v.begin() + v.size()/2);
right.insert(right.begin(), v.begin() + v.size()/2, v.end());
sort(left.begin(), left.end());
sort(right.begin(), right.end());
lsum = 0;
rsum = 0;
for(_int64 i = 0; i < left.size(); i++)
lsum += left[i];
for(_int64 i = 0; i < right.size(); i++)
rsum += right[i];
if(lsum > rsum){
swap(left, right);
swap(lsum, rsum);
}
int steps = 0;
while(step()){
steps++;
if(steps%1000==0)
cout << "1000 steps done" << endl;
}
cout << rsum << " - " << lsum << " = " << rsum - lsum << endl;
}
bool step(){
_int64 diff = rsum - lsum;
for(auto curr = right.rbegin(); curr != right.rend(); curr++){
auto found = lower_bound(left.begin(), left.end(), *curr - diff/2);
//if(found != left.end() && (diff + 2 * *found - 2 * *curr < diff) && (*found - *curr < 0)){
if(found != left.end() && (abs(diff + 2 * *found - 2 * *curr) < diff)){
lsum += + *curr - *found;
rsum += - *curr + *found;
diff = rsum - lsum;
swap(*found, *curr);
sort(left.begin(), left.end());
sort(right.begin(), right.end());
if(lsum > rsum){
swap(left, right);
swap(lsum, rsum);
}
return true;
}
}
return false;
}
void randomswaps(_int64 n){
for(_int64 i = 0; i < n; i++){
_int64 l = rand()%left.size();
_int64 r = rand()%right.size();
lsum += right[r] - left[l];
rsum += left[l] - right[r];
swap(left[l], right[r]);
}
if(lsum > rsum){
swap(left, right);
swap(lsum, rsum);
}
}
};
int main(){
vector<_int64> v;
_int64 const K = 100000;
for(_int64 i = 0; i < K; i++){
v.push_back(i);//rand());
}
vector<_int64> shuffled(K);
for(_int64 i = 0; i < K; i++){
_int64 index = rand()%v.size();
shuffled[i] = v[index];
v.erase(v.begin()+index);
}
cout << "shuffled" << endl;
Solver s(shuffled);
return 0;
cout << "diff = " << s.rsum - s.lsum << endl;
cout << "on the left\n";
for_each(s.left.begin(), s.left.end(), [](_int64 x){ cout << x << " ";});
cout << endl;
cout << "-----------\n";
cout << "on the right\n";
for_each(s.right.begin(), s.right.end(), [](_int64 x){ cout << x << " ";});
cout << endl;
return 0;
}