[CF794C Naming Company] Solution

Problem link: CF794C Naming Company

Problem Statement:

Here is the modified text, formatted in Markdown with inline formulas:

A and B each have a string of length \(n\), consisting of lowercase letters, denoted by \(s\) and \(t\) respectively. There is also a target string \(f\) of length \(n\), initially composed of ? symbols.

Now, A and B take turns performing the following operation:

1. They select a character \(x\) from their own string.
2. They replace one ? in \(f\) with \(x\).
3. They remove \(x\) from their own string.

The game ends when there are no more ? symbols in \(f\).

A's goal is to make the lexicographical order of \(f\) as small as possible, while B's goal is to make it as large as possible.

A is the first player. Your task is to determine the final string \(f\) after the game ends.

Note: The strings \(s\) and \(t\) may contain multiple duplicate characters, and only one character can be removed at a time.

Data range:

\(1 \le n \le 3\times 10^5\)

One obvious greedy algorithm is for both players to fill the beginning of \(f\) with characters that benefit them the most.

However, this greedy strategy is incorrect because it results in a larger answer when the smallest character chosen by A is greater than the largest character chosen by B.

So, what can we do instead? We can use a "reverse greedy strategy" in such cases, which ensures that the problematic position in \(f\) is filled with a character that is not greater than the largest character chosen by B.

Time complexity: \(\mathcal{O}(n)\)

Code:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(3e5 + 15))

char s[N];
int n,a[N],b[N],f[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s + 1); n = strlen(s + 1);
    for(int i = 1; i <= n; i++) a[i] = s[i] - 'a';
    cin >> (s + 1); n = strlen(s + 1);
    for(int i = 1; i <= n; i++) b[i] = s[i] - 'a';
    sort(a + 1, a + 1 + n, less<int>());
    sort(b + 1, b + 1 + n, greater<int>());
    int x = 0, y = 0, pos = n;
    for(int i = 1; i <= n; i++)
    {
        if(a[x + 1] >= b[y + 1]) { pos = i - 1; break; }
        (i & 1) ? (f[i] = a[++x]) : (f[i] = b[++y]);
    }
    x = y = (n >> 1) + 1; if(n & 1) ++x;
    for(int i = n; i > pos; i--) {
        ((pos + n - i + 1) & 1) ? (f[i] = a[--x]) : (f[i] = b[--y]);
    }
    for(int i = 1; i <= n; i++) { cout << char(f[i] + 'a'); } cout << '\n';
    return 0;
}