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