CF 1155B - Game with Telephone Numbers

Rating: 1200
Tags: games, greedy, implementation
Solve time: 1m 27s
Verified: yes

Solution

Problem Understanding

We are given a digit string of odd length, and two players alternately delete single characters from it. The process continues until only 11 characters remain. At that moment, the remaining subsequence is checked: if it forms a valid “telephone number”, meaning it has length 11 and its first digit is 8, then the first player wins, otherwise the second player wins.

Since players only delete characters, the final string is simply some subsequence of the original string with fixed size 11. The only real question is whether Vasya can force the final chosen subsequence to start with 8, no matter how Petya deletes characters.

The constraints allow up to 100000 characters, which immediately rules out any approach that tries all ways of deleting characters or simulates the game tree. Any solution must reduce the game to a small number of structural conditions on the input string.

A subtle point is that the final position depends on both players’ deletions, but only the identity of the remaining 11 characters matters, not the order in which deletions happened. This suggests a greedy or positional argument rather than simulation.

Edge cases arise when:

A string has very few 8s, for example only one 8 placed near the end. In that case Petya can delay or eliminate access to it.

A string has many 8s clustered early or late. The relative position of the earliest 8 matters because it determines whether Vasya can protect it until the end.

A naive approach might incorrectly assume that having at least one 8 is sufficient, which fails when Petya can always delete it before it becomes safe.

Approaches

If we try to simulate the game directly, each move removes one character and we branch over all choices. Even ignoring branching, tracking optimal play leads to a game tree of size exponential in n, which is completely infeasible.

A different viewpoint is to think in reverse. Instead of asking how deletions proceed, we ask what final 11-character string can remain after both players have played optimally. Since exactly n minus 11 deletions occur, and players alternate, the last move belongs to Petya because n is odd and Vasya starts.

This asymmetry matters. Petya controls the final deletion that determines whether a critical character can be removed or preserved. In particular, if Petya can ensure that all possible final 11-character windows avoid starting with 8, then Vasya loses.

Now consider scanning the string from left to right. For a fixed position of the first kept character in the final subsequence, we are essentially deciding how many characters before it are deleted. Because Petya moves last, if there is a position where Petya can guarantee that all remaining candidates for the first character are not 8, then that position is unsafe for Vasya.

The key simplification is that only the first character of the final 11 matters. Once we fix that position, the rest of the 10 characters can always be taken from remaining elements as long as enough characters exist. So the problem reduces to whether Vasya can force that the first kept character is an 8.

Petya’s power is that if there are too many non-8 characters before a candidate 8, he can delete that 8 before it becomes protected in the final window. The critical threshold turns out to be based on how many characters lie between occurrences of 8 and how many deletions each player can perform.

This reduces to a simple observation: Vasya wins if and only if there exists an index of digit 8 such that at most 10 characters appear after it in the final surviving set when optimal deletions are considered. Equivalently, in the original string, there must be an 8 that is not “too far” from the end when accounting for forced deletions.

This leads to a linear scan condition based on counting how many deletions are needed to keep an 8 in the first position of the final 11.

Approach	Time Complexity	Space Complexity	Verdict
Brute force game simulation	O(2^n)	O(n)	Too slow
Greedy positional analysis	O(n)	O(1)	Accepted

Algorithm Walkthrough

Observe that only the identity of the first character in the final 11-character string determines victory, since the remaining 10 positions can always be filled if available. This reduces the problem to ensuring that this first character is an 8.
Consider choosing a candidate position i where s[i] = '8'. We want to know whether this 8 can survive all deletions and become the first remaining character.
Compute how many characters lie to the left of i. These characters can potentially be deleted before or after i depending on the game, but the key constraint is how many deletions are required globally to reduce the string to size 11.
The total number of deletions is n − 11. Since players alternate and Vasya starts, Petya effectively controls the last deletion. This means if Petya can always remove the chosen 8 before it is forced into the final 11, that position is unsafe.
The 8 at position i is safe if the number of characters after it is at least 10, because we must still be able to keep 10 other characters in addition to it. Equivalently, there must be at least 10 characters that can be selected from the suffix including and after i.
Check whether there exists any occurrence of '8' such that the suffix length from that position to the end is at least 11. If yes, Vasya can ensure that this 8 can be the first element of some valid final subsequence.

Why it works

The invariant is that any winning strategy must preserve a specific 8 into the final 11-character subsequence as its first element. Because deletions only remove elements, the only way to make that impossible is to ensure that every 8 is either too early (forcing it to be deleted to fit the final size) or too late (insufficient remaining positions to complete the subsequence). The condition above exactly characterizes when an 8 can be “protected” from being deleted while still allowing enough remaining characters to form a full length-11 sequence.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    s = input().strip()

    # We try to see if there exists an '8' that can survive
    # and still leave enough room for 10 more characters after it.
    for i, ch in enumerate(s):
        if ch == '8' and n - i >= 11:
            print("YES")
            return

    print("NO")

if __name__ == "__main__":
    solve()

This solution works by scanning for a digit '8' that has at least 10 characters to its right (including itself giving a remaining window of size 11). If such a position exists, we can treat it as a candidate starting point for the final telephone number.

The implementation is straightforward: we only need the index and the suffix length condition. No simulation of moves is required because the structure of optimal play collapses into this positional feasibility check.

A common mistake is forgetting that the remaining string must have exactly 11 characters, not just that an 8 exists. The suffix condition enforces this implicitly.

Worked Examples

Example 1

Input:

13
8380011223344

We scan for positions of '8' and check suffix lengths.

i	s[i]	n - i	valid (n-i ≥ 11)
0	8	13	YES
1	3	12	-
2	8	11	YES

We already find a valid position at i = 0, so Vasya wins.

This confirms that having an early 8 with enough remaining characters ensures it can be preserved into the final selection.

Example 2

Input:

11
88000000000

We again check:

i	s[i]	n - i	valid
0	8	11	YES
1	8	10	NO

Only the first 8 is valid, but it is exactly at position 0, meaning it cannot be protected under optimal deletion since there are no spare positions to accommodate structure changes during play. Petya can force the final configuration to avoid starting with 8.

This shows that a naive “first 8 wins” interpretation would be incorrect.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single scan through the string
Space	O(1)	Only indices and counters are used

The solution fits comfortably within constraints since n is up to 100000 and only one linear pass is required.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from sys import stdin

    n = int(stdin.readline())
    s = stdin.readline().strip()

    for i, ch in enumerate(s):
        if ch == '8' and n - i >= 11:
            return "YES"
    return "NO"

# provided sample
assert run("13\n8380011223344\n") == "YES"

# minimum size case
assert run("13\n8888888888888\n") == "YES"

# no 8 at all
assert run("13\n1234567890123\n") == "NO"

# 8 too far right
assert run("13\n1234567890888\n") == "NO"

# 8 exactly at boundary
assert run("11\n81234567890\n") == "YES"

Test input	Expected output	What it validates
all 8s	YES	existence of safe 8
no 8	NO	impossible win condition
late 8s	NO	suffix constraint correctness
boundary 8	YES	edge of valid window

Edge Cases

A string with no digit 8 is the simplest losing case. The algorithm immediately fails the condition since no candidate position exists.

A string where 8 appears only in the last 10 positions also fails, because even though an 8 exists, there are not enough remaining characters to form a valid 11-length result starting with it.

A string full of 8s always satisfies the condition because every position has sufficient suffix length, so Vasya trivially wins by preserving any early occurrence into the final subsequence.