PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: S. Manuj Nanthan
Tester: Takuki Kurokawa
Editorialist: Nishank Suresh
DIFFICULTY:
TBD
PREREQUISITES:
(Optional) Deques
PROBLEM:
Alice and Bob play a game on a binary string S, creating a new string T. They alternate moves, with Alice going first.
- Alice takes the first remaining character of S and moves it to either the start or end of T
- Bob takes the last remaining character of S and moves it to either the start or end of T
Alice tries to (lexicographically) minimize T, while Bob tries to maximize it. What is the final string?
EXPLANATION:
Alice and Bob end up having extremely well-defined moves.
- Since Alice wants to minimize the string, she will always move a 0 to the front and a 1 to the end of T.
- Conversely, Bob will always move a 0 to the back and 1 to the front of T.
This is already enough to solve the problem in \mathcal{O}(N^2) by directly simulating each move:
- Let T be an empty string.
- On Alice’s turn:
- If the character is 0, insert it to the front of T
- If the character is 1, insert it to the back of T
- On Bob’s turn:
- If the character is 1, insert it to the front of T
- If the character is 0, insert it to the back of T
Finally, print T.
For the limits given in the problem, this is already good enough. However, with the help of data structures, there exists a faster solution.
Knowing the moves, all that needs to be done is to simulate the game quickly. For this, we would like a data structure that allows us to quickly insert elements at both the start and the end. The appropriate structure here is a deque
(std::deque
in C++, collections.deque
in Python).
The final solution is thus:
- Keep a deque T, which is initially empty.
- On Alice’s turn:
- If the character is 0, push it to the front of T
- If the character is 1, push it to the back of T
- On Bob’s turn:
- If the character is 1, push it to the front of T
- If the character is 0, push it to the back of T
Finally, print T from front to back.
Every operation on T is \mathcal{O}(1), and by choosing the first/last character of S by maintaining two pointers (instead of directly deleting the character) these operations also become \mathcal{O}(1). This leads to a final complexity of \mathcal{O}(N).
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int n; cin >> n;
string s; cin >> s;
int L = 0, R = n-1;
deque<char> dq;
while (L <= R) {
if (s[L] == '0') dq.push_front('0');
else dq.push_back('1');
if (L < R) {
if (s[R] == '1') dq.push_front('1');
else dq.push_back('0');
}
++L, --R;
}
for (auto c : dq) cout << c;
cout << '\n';
}
}