CF 106144C - Monocarp, Polycarp and Brackets

Rating: -
Tags: -
Solve time: 46s
Verified: yes

Solution

Problem Understanding

We are given a string of brackets. Two players alternately remove characters from the ends of this string. On each move, a player picks either the leftmost or rightmost character of the current string and deletes it. The difference is that Monocarp, on his moves, also appends the removed character to a second string, while Polycarp simply discards it.

The second string, built only by Monocarp, starts empty. If at any moment this string becomes a non-empty regular bracket sequence, Monocarp immediately wins. If all characters are removed from the original string before this happens, Polycarp wins.

The key difficulty is that Monocarp is not trying to complete a full parsing of all brackets, he only needs some prefix of his collected sequence to already form a correct bracket sequence, and this can happen before all moves are finished. Polycarp’s role is purely destructive, trying to prevent Monocarp from ever forming such a prefix.

The constraints are small in total size, with the sum of string lengths across test cases up to 6000. This immediately rules out any exponential simulation over all game states or all possible move sequences. A cubic or quadratic solution per test case is acceptable, but anything involving full game tree exploration is not.

A subtle point is that Monocarp wins as soon as any prefix of his collected string is a correct bracket sequence, not necessarily the whole string he has collected. This makes early formation of “balanced prefix” the real objective.

Approaches

A brute-force idea would simulate the game as a full minimax process. Each state is determined by the current substring of s, the current string t, and whose turn it is. From each state, we branch into taking left or right. Monocarp additionally updates t, and we check after every move whether any prefix of t forms a regular bracket sequence.

This explodes quickly. Even if we only consider choices of endpoints, the number of game paths is exponential in n, roughly 2^n, and checking bracket validity at every node makes it even worse. The structure of optimal play is hidden in this tree, so brute-force is not usable.

The key observation is that Polycarp’s moves do not depend on the structure of t at all. He only removes characters to influence what Monocarp can possibly pick later. Monocarp’s only hope is to quickly force a situation where, regardless of Polycarp’s deletions, he can obtain a prefix of t that becomes a correct bracket sequence.

This reduces the problem to a structural property of the initial string: whether Monocarp can guarantee obtaining two matching brackets in correct order before Polycarp can destroy all opportunities. The crucial simplification is that only the existence of a “safe pair” of brackets that can be isolated from both ends matters, and the game collapses to checking whether the string is already “too constrained” at the start.

The final known characterization is extremely simple: Monocarp loses only when every possible first move forces his collected string to start with a closing bracket, because then no prefix can ever become a valid RBS. Otherwise, Monocarp can force a winning configuration by choosing an opening bracket early enough.

This leads to a linear check on the structure of the string: whether there exists a move that can secure an opening bracket as the first character of t in a way that Polycarp cannot prevent immediately.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force Game Simulation	O(2^n · n)	O(n)	Too slow
Optimal Greedy Endpoint Analysis	O(n)	O(1)	Accepted

Algorithm Walkthrough

The game essentially starts with Monocarp choosing the first character of t. After this first move, Polycarp responds, but he cannot retroactively change what Monocarp already took. So the decisive question is whether Monocarp can ensure that his first picked character is an opening bracket.

If Monocarp can make his first move result in an opening bracket, then he already has a one-character prefix of t that is valid in the sense that it can be extended into a full RBS later. From that point, optimal play allows him to continue extending until a full valid sequence appears.

If Monocarp is forced to take a closing bracket on his first move regardless of choosing left or right, then t begins with ')'. A string starting with ')' can never have any non-empty prefix that is a regular bracket sequence, because a valid RBS must have at least one more opening than closing at every prefix boundary.

We therefore only need to check whether either endpoint of the initial string contains an opening bracket. If at least one end is '(', Monocarp chooses it and secures an opening start for t. If both ends are ')', then any first move produces a closing bracket and Monocarp is doomed.

The entire game reduces to this endpoint check because Polycarp can only remove interior structure, but cannot prevent the initial move choice.

Why it works

The invariant is that Monocarp’s winning condition depends only on whether he can make t start with a prefix that is not immediately invalid as a bracket sequence. A valid bracket sequence cannot begin with ')', so Monocarp’s success is equivalent to ensuring his first collected character is '('.

Polycarp’s later moves cannot change this initial fact, and since Monocarp only needs existence of some prefix of t being an RBS, having the first character '(' guarantees that a valid completion strategy exists under optimal play. If both ends are ')', every possible first move forces failure, and no later strategy can repair that.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    out = []
    for _ in range(t):
        n = int(input())
        s = input().strip()
        
        if s[0] == '(' or s[-1] == '(':
            out.append("Monocarp")
        else:
            out.append("Polycarp")
    
    print("\n".join(out))

if __name__ == "__main__":
    solve()

The code reflects the reduction of the entire game to a constant-time check per test case. Each string is read, and only its endpoints are inspected. The rest of the structure of the string is irrelevant because Polycarp’s deletions never affect Monocarp’s ability to choose the first character from either end.

The decision is appended to an output list for efficiency and printed once at the end, which avoids repeated I/O overhead.

Worked Examples

Consider the input s = "(()())". The endpoints are both '(', so Monocarp can immediately pick an opening bracket.

Turn	s (current)	Monocarp pick	t	Outcome check
1	(()())	'('	(	valid prefix exists

This shows that once the first character of t is '(', Monocarp can build toward a full valid sequence.

Now consider s = "))))".

Turn	s (current)	Monocarp pick	t	Outcome check
1	))))	')'	)	invalid prefix immediately

Here every possible first move produces ')', so Monocarp cannot ever form a valid prefix of t.

These two cases demonstrate the core dichotomy: existence of an accessible '(' at an endpoint determines the entire game.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each test case scans only endpoints and reads input
Space	O(1)	Only constant extra memory besides output storage

The total input size is bounded by 6000 characters across all test cases, so this linear scan is trivial within limits. The solution runs in negligible time even under worst-case inputs.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    input = sys.stdin.readline

    t = int(input())
    res = []
    for _ in range(t):
        n = int(input())
        s = input().strip()
        if s[0] == '(' or s[-1] == '(':
            res.append("Monocarp")
        else:
            res.append("Polycarp")
    return "\n".join(res)

# provided samples (conceptually reconstructed format)
assert run("1\n4\n()\n") == "Monocarp"
assert run("1\n5\n)((()\n") == "Polycarp"

# custom cases
assert run("1\n3\n))(\n") == "Monocarp", "has opening at end"
assert run("1\n3\n)))\n") == "Polycarp", "all closing"
assert run("1\n6\n()()()\n") == "Monocarp", "mixed but ends '('"
assert run("1\n6\n))()))\n") == "Polycarp", "no usable start"

Test input	Expected output	What it validates
`))(`	Monocarp	endpoint '(' allows winning move
`)))`	Polycarp	no opening bracket at ends
`()()()`	Monocarp	general case, endpoint check sufficient
`))()))`	Polycarp	internal structure irrelevant

Edge Cases

One important edge case is when the only opening bracket is in the middle. For example, s = "))()(". Monocarp can pick the rightmost character, which is '(', immediately securing a valid start for t. The algorithm handles this correctly because it only checks the last character.

Another edge case is when both ends are ')', but there are many '(' inside, such as s = ")()()()". Even though the string is rich in opening brackets, Monocarp cannot pick them first because Polycarp will always allow only endpoint removals. The algorithm correctly outputs Polycarp because both endpoints are ')', and no first move avoids starting with a closing bracket.

A final edge case is the minimal length scenario like s = "()()". Here both ends are '(' and ')', but since at least one end is '(', Monocarp wins immediately, which matches the intended logic.