 Setter: arpit121
Testers: tabr

1494

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

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;
}
}
``````

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

Can any1 tell the test case which is causing a runtime error…i tried my best to see where its possible that i am accesiing array Element out of bounds but i cant figure out…its just one case that is causing RE…

//why this code is givivng TLE

import java.util.*;

import java.lang.*;

import java.io.*;

class help {

``````public static void main(String[] args) throws java.lang.Exception {

Scanner sc = new Scanner(System.in);

int t = sc.nextInt();

while (sc.hasNext()) {

int n = sc.nextInt();

sc.nextLine();

String s = sc.nextLine();

ArrayList<Character> arr=new ArrayList<>();

int p=0,m=0;

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

{

char ch=s.charAt(i);

if((int)ch>=48 && (int)ch<=57){

}else{

if(ch=='+')

p++;

else

m++;

}

}

String st="";

Collections.sort(arr);

for(int i=0;i<arr.size();i++)

{

st=arr.get(i)+st;

if(m>0)

{

st='-'+st;

m--;

}else if(p>0)

{

st='+'+st;

p--;

}

}

System.out.println(st);

}

}
``````

}

I was this close to the solution.

Can someone tell me which test case was failing.

Here is my solution: CodeChef

Same bro…the same thing…for me it was that on 2nd case i got RE…and rest AC…i wonder whats the 2nd test case dats just ruining this:(

this is the case when there will be zero operator. Just sort the numbers in decreasing order .

2 Likes

thank you!

Thank You Implemented the change suggested by rapter_mine?

Can you give us a test case here, because I think I already took care of the zero operators

yes, it worked for me!

can you send your solution link, the link you have given is for the question and not your solution

Here - CodeChef