PROBLEM LINK:
Setter: arpit121
Testers: tabr
Editorialist: aryanag_adm
DIFFICULTY:
1494
PREREQUISITES:
Sorting
PROBLEM:
You are given a string consisting of digits from 0-9, along with + and - characters. You are guaranteed that this string forms a valid mathematical expression.
You can arbitrarily permute the string. Do this in a way such that the final string represents a valid mathematical expression, and its value is maximised.
EXPLANATION:
We want the positive terms to be as large as possible, and the negative terms to be as small as possible.
Assume we have A + characters, and B - characters. Sort the remaining digits in non increasing order. Let’s say we have C = N - A - B digits.
Note that the first number in our expression is always positive, so we want to maximise it. We need to leave at least A+B digits for the rest of the expression, we we can use D = C - A - B digits on the first number itself. Now, in order to maximise the number, we should use the largest D digits, so that the largest digits is in the most significant spot. Eg. if we have digits \{5, 4, 3, 2\} and D = 3, then we should set the first number to be 543.
Now, each of the remaining numbers will have 1 digit each. A of these digits will be added positively, and B will be added negatively. Therefore, we should create the expression by first alternating +'s with the largest A remaining digits, and then alternating -'s with the remaining digits.
It’s easy to prove that this algorithm is correct, let’s see how it works on a sample input.
N = 7, S = 4-89+20
A = 1, B = 1, D = 3. the digits are \{9, 8, 4, 2, 0\}.
Now, the first number should be 984.
Now, we should alternate A +'s with the largest A remaining digits. This gives us +2.
Finally, we should alternate B -'s with the B remaining digits. This gives us -0.
Therefore, our expression is 987 + 2 - 0
TIME COMPLEXITY:
O(N\log N)
SOLUTION:
Editorialist's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>
#define double long double
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
vector<int> num;
int pl = 0, mi = 0;
for(int i = 0;i<n;i++){
if(s[i] == '-') mi++;
else if(s[i] == '+') pl++;
else num.push_back(s[i] - '0');
}
sort(num.begin(), num.end());
for(int i = num.size()-1;i>(pl + mi - 1);i--) cout<<num[i];
for(int i = pl+mi-1;i>=0;i--){
if(pl-->0) cout<<'+';
else cout<<'-';
cout<<num[i];
}
cout<<endl;
}
}
