# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

**Setter:** Hardik

**Tester:** Abhinav Sharma

**Editorialist:** Kanhaiya Mohan

# DIFFICULTY:

Easy-medium

# PREREQUISITES:

# PROBLEM:

Initially, Alice and Bob both have a bag of N stones each with every stone having a **lowercase alphabet** written on it. Both players know the stones of the other player.

Alice and Bob want to create a string S of length 2 \cdot N using the stones they have. They play a game to create the string. The rules of the game are as follows:

- Initially, all the indices of S are empty.
- Alice starts the game. The players take alternating turns. In each turn, the player can choose one of the stones from their bag and place it at any empty index i (1 \le i \le 2 \cdot N) of S.
- The game ends when both the players have used all their stones.
- Alice wants S to be as lexicographically small as possible while Bob wants S to be as lexicographically large as possible.

Find the final string S formed by characters written on stones if both Alice and Bob play optimally!

# EXPLANATION:

## Observation 1

Alice wants the string to be as lexicographically small as possible.

For each turn, Alice would want the smallest empty index to be filled with the lexicographically **smallest** letter available. Similarly, she would want the largest empty index to be filled with the lexicographically **largest** letter available.

On the other hand, Bob would want the smallest empty index to be filled with the lexicographically **largest** letter available and the largest empty index to be filled with the lexicographically **smallest** letter available.

## Observation 2

Consider the case when all the letters Alice has, are lexicographically larger than the letters of Bob.

The smallest letter Alice chooses would be larger than any letter chosen by Bob.

Thus, it is not optimal for Alice to fill the smallest empty index with the smallest letter available to her. However, since all her letters are larger than Bob’s, she can fill the largest empty index with the largest letter available to her.

Similarly, if all the letters of Bob are lexicographically smaller than the letters of Alice, it is not optimal for Bob to fill the smallest empty index with the largest letter available to him. Instead, he can fill the largest empty index with the smallest letter available to him.

## Solution

## Optimal moves for Alice

- Place lexicographically
**smaller**letters at smaller empty indices. - Place lexicographically
**larger**letters at larger empty indices.

## Optimal moves for Bob

- Place lexicographically
**larger**letters at smaller empty indices. - Place lexicographically
**smaller**letters at larger empty indices.

Suppose it is Alice’s turn to place a stone.

From all the stones available to her, she chooses the stone with lexicographically **smallest** letter.

Suppose this letter is lexicographically greater than the largest letter available to Bob.

This means that all letters of Alice are larger than Bob’s . Thus, Alice has the overall lexicographically **largest** character available amongst **both** of them. She can place the lexicographically **largest** character at the largest empty index.

On the other hand, if this not the case, she can place the lexicographically **smallest** character **available to her** at the smallest empty index.

Similarly, if it is Bob’s turn:

From all the stones available to him, he chooses the stone with lexicographically **largest** letter.

Suppose this letter is lexicographically smaller than the smallest letter available to Alice. This means that all of Bob’s letters are smaller than Alice’s . Thus, Bob has the overall lexicographically **smallest** character available amongst **both** of them. He can place the lexicographically **smallest** character at the largest empty index.

On the other hand, if this not the case, he can place the lexicographically **largest** character **available to him** at the smallest empty index.

Note that when the largest letter of Bob is **equal** to the smallest letter of Alice, the optimal move for any player would be to place the letter at the **largest** empty index.

# TIME COMPLEXITY:

Based on the implementation, the time complexity can be O(Nlog(N)) or O(N) per test case. Refer Editorialist’s Solution for O(N) implementation.

# SOLUTION:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
int test;
cin >> test;
while (test--)
{
int n;
cin >> n;
string ansl;
string ansr;
string s,t;
cin>>s>>t;
sort(s.begin(),s.end());
sort(t.begin(),t.end());
reverse(t.begin(),t.end());
deque<char> a,b;
for(int i=0;i<n;i++)
{
a.push_back(s[i]);
}
for(int i=0;i<n;i++)
{
b.push_back(t[i]);
}
int turn=0;
for(int i=0;i<2*n;i++)
{
if(i&1) // BOb turn
{
if(!a.empty() and a[0]>=b[0])
{
turn=1;
}
if(turn)
{
ansr+=b.back();
b.pop_back();
}
else
{
ansl+=b[0];
b.pop_front();
}
}
else //Alice's turn
{
if(!b.empty() and a[0]>=b[0])
{
turn=1;
}
if(turn)
{
ansr+=a.back();
a.pop_back();
}
else
{
ansl+=a[0];
a.pop_front();
}
}
}
reverse(ansr.begin(),ansr.end());
string result = ansl+ansr;
cout<<result<<'\n';
}
// assert(getchar() == -1);
cerr<<"SUCCESS\n";
cerr << "\nTime elapsed: " << setprecision(6) << 1000.0 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
```

## Tester's Solution

```
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
cin >> T;
while(T--){
int n;
cin>>n;
string s,t;
cin>>s>>t;
sort(s.begin(), s.end());
sort(t.begin(), t.end());
reverse(t.begin(), t.end());
string s1="", s2="";
int f=0;
rep(i,2*n){
if(i&1){
if(f) s2+=t[i/2];
else{
if(t[i/2]<=s[i/2+1]){
reverse(s.begin()+i/2+1, s.end());
reverse(t.begin()+i/2, t.end());
f=1;
s2+=t[i/2];
}
else s1+=t[i/2];
}
}
else{
if(f) s2+=s[i/2];
else{
if(s[i/2]>=t[i/2]){
reverse(s.begin()+i/2, s.end());
reverse(t.begin()+i/2, t.end());
f=1;
s2+=s[i/2];
}
else s1+=s[i/2];
}
}
}
reverse(s2.begin(), s2.end());
cout<<s1+s2<<'\n';
}
return 0;
}
```

## Video Editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
void solve() {
int N; cin >> N;
string A, B; cin >> A >> B;
vector<char> ans(2 * N);
int front = 0, back = 2 * N - 1;
int startA = 0, endA = N-1, startB = 0, endB = N-1;
sort(A.begin(), A.end());
sort(B.begin(), B.end());
reverse(B.begin(), B.end());
for(int i = 0; i < 2*N; i ++) {
if((i % 2) == 0) { // Current Turn = Alice
if(startB <= endB && A[startA] >= B[startB]) {
ans[back --] = A[endA --];
}
else {
ans[front ++] = A[startA ++];
}
}
else { // Bob Turn
if(startA <= endA && A[startA] < B[startB]) {
ans[front ++] = B[startB ++];
}
else {
ans[back --] = B[endB --];
}
}
}
for(char ch : ans) {
cout << ch;
}
cout << endl;
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T; cin >> T;
while(T --) {
solve();
}
}
```

## Editorialist's Solution

```
#include <bits/stdc++.h>
using namespace std;
int smallest(int a[]){
for(int i = 0; i<26; i++){
if(a[i]>0)
return i;
}
return -1;
}
int largest(int a[]){
for(int i = 25; i>=0; i--){
if(a[i]>0)
return i;
}
return -1;
}
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string p, q;
cin>>p>>q;
int f1[26] = {0};
int f2[26] = {0};
for(int i = 0; i<n; i++){
f1[p[i]-'a']++;
f2[q[i]-'a']++;
}
char ans[2*n];
int st = 0;
int end = 2*n-1;
for(int i = 0; i<2*n; i++){
if((i % 2) == 0) {
int sA = smallest(f1);
int lA = largest(f1);
int lB = largest(f2);
if(lB!=-1 && sA >= lB){
ans[end--] = ('a'+lA);
f1[lA]--;
}
else {
ans[st++] = ('a'+sA);
f1[sA]--;
}
}
else{
int sA = smallest(f1);
int lB = largest(f2);
int sB = smallest(f2);
if(sA!=-1 && sA < lB) {
ans[st++] = ('a'+lB);
f2[lB]--;
}
else {
ans[end--] = ('a'+sB);
f2[sB]--;
}
}
}
for(auto ch: ans){
cout<<ch;
}
cout<<endl;
}
return 0;
}
```