CF 105733A - GDSC và BKAC

CF 105733A - GDSC v\u00e0 BKAC

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

Solution

Problem Understanding

Two groups, GDSC and BKAC, are scanning a single string from left to right, character by character. Each group has a fixed target set of letters. GDSC is trying to collect the letters G, D, S, and C. BKAC is trying to collect B, K, A, and C. Whenever a character appears in the string, both groups independently check whether it belongs to their target set. If it does, they add it to their collection, and if it does not, they ignore it. The first group that manages to collect all of its required letters at least once wins. If both complete their collection at the same position in the scan, the result is a draw.

The key detail is that the order of characters in the string defines a timeline. We are not reordering or choosing subsequences; we are simulating a sequential process where each step may contribute to one or both teams.

The constraints are small, with the string length up to 100 and at most 100 test cases. This immediately rules out any need for advanced data structures or optimization beyond a single linear scan per test case. An O(n²) approach would still pass comfortably, but anything more complicated than a single pass is unnecessary overhead.

A subtle edge case arises from the shared character C. Both teams need it. This creates scenarios where progress can be synchronized in non-obvious ways. For example, if C appears very early but the remaining required letters are scattered, both teams might complete at different times despite sharing progress on one key character.

Another edge case appears when one team’s required letters appear much earlier but missing a single final letter delays completion. For instance, if BKAC collects B, K, and A in the first few positions but C appears late, while GDSC steadily accumulates its letters earlier, the winner depends entirely on the last missing requirement rather than frequency or majority appearance.

Finally, repeated characters matter. A naive mistake is to count occurrences rather than tracking whether each required letter has been seen at least once. For example, in a string like GGGG, GDSC has not completed anything because it still lacks D, S, and C, even though a frequency-based interpretation might incorrectly suggest progress.

Approaches

The brute-force idea is to simulate the process exactly as described. For each prefix of the string, we maintain two sets representing what each team has collected so far. At every position, we update the sets and check whether they contain all required characters. This is correct because it mirrors the rules directly.

This approach runs in O(n) per test case since each character is processed once and set operations are constant time. Even if we implemented it less carefully using repeated scans over required letters at each step, we would still be within O(n × 8), which is trivial given n ≤ 100.

There is no deeper optimization required because the structure of the problem is inherently sequential. The only meaningful observation is that we never need to revisit past characters or compute anything beyond “have we seen all required letters yet”.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force simulation	O(n)	O(1)	Accepted
Optimal single-pass tracking	O(n)	O(1)	Accepted

Algorithm Walkthrough

We treat the string as a timeline and maintain two boolean trackers for each team.

1. Initialize four boolean arrays or sets: one for GDSC progress and one for BKAC progress. Each starts empty because no characters have been seen yet.
2. Predefine the required sets: GDSC needs G, D, S, C; BKAC needs B, K, A, C.
3. Scan the string from left to right. For each character, update both teams’ progress if the character belongs to their respective required sets. This step ensures both teams progress independently but synchronously on the same input stream.
4. After updating for a character, check whether GDSC has all four required letters. If so, record the current index as its completion point.
5. Do the same check for BKAC and record its completion point.
6. After finishing the scan, compare the recorded completion indices. If one is smaller, that team wins. If they are equal, the result is a draw.

The important design choice is that we only care about the first moment each team becomes complete. Once a team has collected all letters, later occurrences do not matter for deciding the winner.

Why it works

Each team’s state depends only on whether each required letter has appeared at least once before or at the current position. The state is monotonic: once a letter is collected, it is never lost. Because of this, the first position where all required letters are present is uniquely defined and sufficient to determine the outcome. Comparing these first completion positions fully captures the competition described in the process.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input().strip())
        s = input().strip()

        need_gdsc = set("GDSC")
        need_bkac = set("BKAC")

        have_gdsc = set()
        have_bkac = set()

        finish_gdsc = -1
        finish_bkac = -1

        for i, ch in enumerate(s):
            if ch in need_gdsc:
                have_gdsc.add(ch)
            if ch in need_bkac:
                have_bkac.add(ch)

            if finish_gdsc == -1 and have_gdsc == need_gdsc:
                finish_gdsc = i
            if finish_bkac == -1 and have_bkac == need_bkac:
                finish_bkac = i

        if finish_gdsc < finish_bkac:
            print("GDSC")
        elif finish_bkac < finish_gdsc:
            print("BKAC")
        else:
            print("DRAW")

if __name__ == "__main__":
    solve()

The implementation follows the simulation exactly. The sets have_gdsc and have_bkac track which required characters have been encountered so far. Once a team reaches completeness, we lock its completion index so later updates do not overwrite it.

A subtle point is initializing completion indices to -1. This guarantees that once a team finishes, we do not recompute or accidentally shift its result. The comparison at the end is purely based on first completion time.

Worked Examples

Consider a string where both teams complete at different times.

Input:

1
6
GDBSCA

We track progress step by step.

i	char	GDSC have	BKAC have	GDSC done	BKAC done
0	G	G		No	No
1	D	GD		No	No
2	B	GD	B	No	No
3	S	GDS	B	No	No
4	C	GDSC	BC	Yes (4)	No
5	A	GDSC	BCA	Yes (4)	Yes (5)

GDSC finishes at index 4, BKAC at index 5, so GDSC wins. The trace shows how a shared character like C contributes to both progress paths simultaneously but does not guarantee equal completion.

Now consider a simultaneous completion case.

Input:

1
4
BKAC

i	char	GDSC have	BKAC have	GDSC done	BKAC done
0	B		B	No	No
1	K		BK	No	No
2	A		BKA	No	No
3	C	C	BKAC	Yes (3)	Yes (3)

Both teams complete at the same index, producing a draw. This confirms that shared final characters directly synchronize completion when both sets become satisfied at the same moment.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n) per test case	Each character is processed once with constant-time set updates and checks
Space	O(1)	Only fixed-size sets for at most four characters per team

Given n ≤ 100 and t ≤ 100, the solution runs in at most 10⁴ character operations, which is negligible within the limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    out = io.StringIO()
    with redirect_stdout(out):
        solve()
    return out.getvalue().strip()

# provided sample
assert run("""3
4
CKAB
4
GSDC
10
BAKAZPGDSC
""") == """BKAC
GDSC
DRAW"""

# minimum size, immediate C overlap
assert run("""1
4
BKAC
""") == "DRAW"

# GDSC clearly earlier
assert run("""1
5
GDSCA
""") == "GDSC"

# BKAC clearly earlier
assert run("""1
6
BKAACD""") == "BKAC"

# missing early letters forces late completion
assert run("""1
8
AAAAKBCGDS""") == "BKAC"

Test input	Expected output	What it validates
sample block	mixed	correctness on full scenario
BKAC	DRAW	simultaneous completion
GDSCA	GDSC	early completion bias
BKAACD	BKAC	asymmetry in required letters
AAAAKBCGDS	BKAC	delayed completion due to missing key letters

Edge Cases

One important edge case is when both teams rely heavily on the shared character C, but their other required letters appear at very different times. For input like CCCCDGSKBA, both teams collect C almost immediately, but completion is dictated entirely by the last missing non-shared letter. The algorithm handles this correctly because completion is only triggered when the full set is satisfied, not partial progress.

Another case is repeated irrelevant characters. In a string like ZZZZGDSC, GDSC completes only at the final appearance of C even though many irrelevant characters appear earlier. Since the algorithm ignores non-required characters entirely, these do not affect state transitions