 # STNGAME - Editorial

Setter: Hardik
Tester: Abhinav Sharma
Editorialist: Kanhaiya Mohan

Easy-medium

Greedy Algorithm

# 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>=b)
{
turn=1;
}
if(turn)
{
ansr+=b.back();
b.pop_back();
}
else
{
ansl+=b;
b.pop_front();
}
}
else //Alice's turn
{
if(!b.empty() and a>=b)
{
turn=1;
}
if(turn)
{
ansr+=a.back();
a.pop_back();
}
else
{
ansl+=a;
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 = {0};
int f2 = {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;
}

7 Likes

Loved solving this really nice problem  3 Likes

CAN YOU PLEASE TELL ME WHAT IS THE MISTAKE IIN MY PROGRAM

#include<stdio.h>

int main()

{

int t;

scanf("%d",&t);

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

{

int n;

int k=0;

int u=0;

int w=0;

char temp;

scanf("%d",&n);

int l=2*n;

char a[n],b[n],s[l];

scanf("%s %s",&a,&b);

for (int p = 0; p <n; ++p){

for (int j = p + 1; j <n; ++j){

  if (a[p] > a[j]){

temp = a[p];

a[p] = a[j];

a[j] = temp;

}


}

}

for (int q = 0; q < n; ++q){

for (int f = q + 1; f <n; ++f){

  if (b[q] < b[f]){

temp = b[q];

b[q] = b[f];

b[f] = temp;

}


}

}

while(k<l)

{

if (w<=u){

s[k]=a[w];

k++;

w++;

}

else{

s[k]=b[u];

k++;

u++;}


}

printf("%s\n",s);

}

return 0;


}

1 Like

Considering the fact that this is div4 I would loved not to see a greedy as the hardest problem because probably many beginners don’t know how to think them. Anyhow the problem was fun to solve even tho I messed up implementation several times.

Thus, Bob has the overall lexicographically smallest character available amongst both of them. He can place the lexicographically smallest character at the largest (not smallest) empty index.

1 Like

The time complexity will be O(NlogN) since we will need to sort the input strings.
Also, this problem is copied from this problem.

4 Likes

It is not necessary to sort the input strings. You can implement an O(N) solution by storing the character counts as well. I have added the solution for reference.

4 Likes

can anyone check this code please below

def solve(A,B,N):
ans = [’’ for i in range(2N)]
front,back,startA,endA,startB,endB = 0,2
N-1,0,N-1,0,N-1
A = ‘’.join(sorted(A))
b = ‘’.join(sorted(B,reverse = True))

for i in range(2*N):
if((i&1) == 0):
if startB<=endB and A[startA] >= B[startB]:
ans[back] = A[endA]
back,endA = back-1,endA-1
else:
ans[front] = A[startA]
front,startA = front +1,startA+1
else:
if startA <= endA and A[startA]<B[startB]:
ans[front] = B[startB]
front,startB = front+1,startB+1
else:
ans[back] = B[endB]
back,endB = back-1,endB-1
print(''.join(ans))


try:
t = int(input())
for _ in range(t):
N = int(input())
A = input()
B = input()
solve(A,B,N)

except:pass

this code is giving me WA even after seeing and learning from tutorail

can anyone help me in figuring what’s wrong in my code.
it works well in sample cases but showing wrong answer for sub tasks when submitted.

#include <bits/stdc++.h>

#define ll long long

#define mod 1e9+7;

using namespace std;

string solve()

{

int n;

cin>>n;

string a,b,res;

cin>>a;cin>>b;

res.resize(2*n);

//cout<<res;

sort(a.begin(),a.end());sort(b.begin(),b.end(),greater<char>());

int starta=0,startb=0;

int enda=n-1;int endb=n-1;

bool aturn=true;int front=0,back=2*n-1;

//cout<<front<<" "<<back<<" "<<last<<endl;

while(front<=back)

{   if(aturn)

{

if(a[starta]<=b[startb])res[front++]=a[starta++];

else res[back--]=a[enda--];

aturn=false;

}

else

{

if(starta<=enda && b[startb]<a[starta])res[back--]=b[endb--];

else res[front++]=b[startb++];

aturn=true;

}

}

return res;


}

int main()

{

int t;

cin>>t;

while(t--)

{

cout<<solve()<<endl;

//cout<<endl;

}

return 0;


}

Could anyone please help me find where this solution fails?

1
4
aaab
cdef
check for this input

1 Like

Please anyone tell why this code is failing for hidden test cases ? It is passing sample test cases

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long int ll;

int main() {
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
string a,b;
cin>>a;
cin>>b;
string res="";
sort(a.begin(),a.end());
sort(b.begin(),b.end(),greater<char>());
ll l=a.size()+b.size();
ll x=0,y=0;
for(ll i=0;i<l;i++){
if(i%2==0){
res.push_back(a[x]);
x++;
}
else{
res.push_back(b[y]);
y++;
}
}
cout<<res<<endl;
}
return 0;
}



Sample test cases are not exhaustive, they are usually just for the output format reference.

I hope you have given thought to

If not have a look at this.

As for where it fails, whenever max of the stones held by Bob are lesser than min of the stones held by Alice, it is better if Alice leaves the first cell empty. What you do is greedily put smallest stone of Alice at first index. Just fixing this one case will not solve the problem though.

2 Likes

Thank you bro