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