# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* S. Manuj Nanthan

*Takuki Kurokawa*

**Tester:***Nishank Suresh*

**Editorialist:**# 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';
}
}
```