CF 65D - Harry Potter and the Sorting Hat

CF 65D - Harry Potter and the Sorting Hat

Rating: 2200
Tags: brute force, dfs and similar, hashing
Solve time: 1m 58s
Verified: yes

Solution

Problem Understanding

We process students one by one. Each student either has a fixed house, represented by one of the letters G, H, R, S, or has ambiguous ancestry, represented by ?.

A fixed student always goes into that house. A ? student behaves differently. We look at the current counts of all four houses. The student may choose any house whose count is currently minimal.

Hermione comes after all given students. We must determine every house she could possibly end up in, assuming earlier ? students choose their houses in any valid way.

The key difficulty is that earlier choices affect later balances. Two different decisions at the beginning can completely change what houses are available later.

The number of students before Hermione is at most 10000. That is far too large for any exponential search over all ? assignments. Even 2^40 is impossible, and in the worst case we may have 10000 ambiguous students. We need something closer to linear or polynomial time.

A subtle part of the problem is that we are not asked for one reachable configuration. We need all houses Hermione could possibly enter under some sequence of valid choices.

One easy mistake is assuming that every ? student should always pick all currently minimal houses equally. The process is not probabilistic. We only care about reachability.

Consider:

2
H?

After the first student:

G=0 H=1 R=0 S=0

The second student may choose G, R, or S.

If they choose G, Hermione may choose R or S.

If they choose R, Hermione may choose G or S.

If they choose S, Hermione may choose G or R.

So Hermione can never end in H.

A greedy simulation that arbitrarily picks one house for each ? would miss possibilities.

Another dangerous edge case is when multiple houses stay perfectly balanced for a long time.

Example:

4
????

Every step preserves near-balance. After four students, every house can still have count 1, so Hermione may choose any house.

A careless DFS over counts without memoization explodes because many different sequences produce the same state.

There is also a symmetry observation hidden here. Only relative differences matter. The exact order of previous choices matters only through the current counts.

Approaches

The brute force idea is straightforward. Process students from left to right. Whenever we see a fixed letter, increment that house. Whenever we see ?, branch into every currently minimal house.

At the end, inspect which houses are minimal for Hermione.

This is correct because it explicitly explores every legal sequence of decisions.

The problem is the number of branches. In the worst case, the first many students may all be ?, and each one can branch into up to four choices. Even with pruning, the number of paths grows exponentially.

For example, with only 40 ambiguous students, 4^40 is already astronomically large.

The important observation is that many different choice sequences lead to exactly the same house counts. Once the counts are identical, the future possibilities are identical too.

That immediately suggests dynamic programming or memoized DFS over states.

Now we need to understand how large the state space really is. At first glance, counts can go up to 10000, which sounds huge. But the balancing rule heavily restricts configurations.

A ? student may only enter a currently minimal house. That means house counts can never differ by more than 1 among houses that evolved only through ? assignments. Fixed assignments disturb the balance, but only in controlled ways.

The crucial compression is this:

Instead of storing exact histories, we store only the tuple of current counts.

From one state, transitions are deterministic:

fixed letter -> increment one count,

question mark -> increment every minimal count separately.

The number of reachable count tuples stays surprisingly small because the balancing constraint aggressively merges paths.

We can run DFS with memoization over reachable states. Every unique state is processed once.

That gives an accepted solution comfortably within limits.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(4^q)	O(q)	Too slow
Optimal	O(number of reachable states)	O(number of reachable states)	Accepted

Here q is the number of ? characters.

Algorithm Walkthrough

1. Represent houses as indices:

0 = G, 1 = H, 2 = R, 3 = S. 2. Start from the count tuple (0, 0, 0, 0). 3. Process the students from left to right using DFS with memoization. 4. The DFS state consists of:

the current position i,

and the current tuple of house counts. 5. If i == n, we reached the moment before Hermione.

Find the minimum count among the four houses.

Every house with that minimum is a valid answer. 6. If the current student has a fixed house letter, increment only that house and continue DFS. 7. If the current student is ?, compute the minimum current count.

Every house having that minimum is a legal transition.

For each such house, increment its count and continue DFS. 8. Memoize visited states (i, counts) so the same configuration is never processed twice.

Without memoization, the same count tuple can be reached through many different sequences of choices.

Why it works

The state completely determines the future.

Suppose two different histories produce the same position i and the same count tuple. Every remaining student sees exactly the same house counts, so the set of legal future moves is identical. No information from earlier decisions matters anymore.

The DFS explores every legal transition exactly once per unique state. Every terminal state corresponds to a valid sorting sequence, and every valid sorting sequence appears in the DFS.

So the collected minimal houses at the end are exactly the houses Hermione can enter.

Python Solution

import sys
from functools import lru_cache

input = sys.stdin.readline

houses = ['G', 'H', 'R', 'S']
name_map = {
    'G': 'Gryffindor',
    'H': 'Hufflepuff',
    'R': 'Ravenclaw',
    'S': 'Slytherin'
}

idx = {c: i for i, c in enumerate(houses)}

n = int(input())
s = input().strip()

possible = [False] * 4

@lru_cache(maxsize=None)
def dfs(i, g, h, r, s_cnt):
    counts = [g, h, r, s_cnt]

    if i == n:
        mn = min(counts)
        for j in range(4):
            if counts[j] == mn:
                possible[j] = True
        return

    ch = s[i]

    if ch != '?':
        nxt = counts[:]
        nxt[idx[ch]] += 1
        dfs(i + 1, *nxt)
    else:
        mn = min(counts)

        for j in range(4):
            if counts[j] == mn:
                nxt = counts[:]
                nxt[j] += 1
                dfs(i + 1, *nxt)

dfs(0, 0, 0, 0)

for i in range(4):
    if possible[i]:
        print(name_map[houses[i]])

The DFS directly mirrors the sorting process.

The memoization key contains both the current position and the four house counts. Two states with the same values are interchangeable because future transitions depend only on these values.

The terminal condition deserves attention. We do not assign Hermione anywhere. We only inspect which houses are currently minimal, because those are the houses she may choose from.

Another subtle point is updating answers globally instead of returning sets from DFS. Returning large sets repeatedly would add unnecessary overhead. A simple boolean array is enough.

The tuple unpacking in:

dfs(i + 1, *nxt)

keeps the cache key immutable and hashable. Using lists directly would fail because lists are not hashable.

Worked Examples

Example 1

Input:

11
G????SS???H

Trace of one branch leading to Gryffindor:

Step	Student	Counts Before	Choice	Counts After
1	G	(0,0,0,0)	forced G	(1,0,0,0)
2	?	(1,0,0,0)	H	(1,1,0,0)
3	?	(1,1,0,0)	R	(1,1,1,0)
4	?	(1,1,1,0)	S	(1,1,1,1)
5	?	(1,1,1,1)	G	(2,1,1,1)
6	S	(2,1,1,1)	forced S	(2,1,1,2)
7	S	(2,1,1,2)	forced S	(2,1,1,3)
8	?	(2,1,1,3)	H	(2,2,1,3)
9	?	(2,2,1,3)	R	(2,2,2,3)
10	?	(2,2,2,3)	G	(3,2,2,3)
11	H	(3,2,2,3)	forced H	(3,3,2,3)

Hermione sees:

G=3 H=3 R=2 S=3

So she may enter Ravenclaw.

Different earlier choices can instead make Gryffindor minimal.

This trace demonstrates why we must explore multiple branches. The final answer depends on coordinated balancing decisions across many earlier students.

Example 2

Input:

2
H?

Step	Student	Counts Before	Choice	Counts After
1	H	(0,0,0,0)	forced H	(0,1,0,0)
2	?	(0,1,0,0)	G	(1,1,0,0)

Hermione then sees:

G=1 H=1 R=0 S=0

So she may choose R or S.

Other second-step choices produce analogous states.

Union of all possibilities:

Gryffindor
Ravenclaw
Slytherin

This example shows that a house need not appear in every final configuration. We only need existence of some valid sequence.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(number of reachable states)	Each memoized state is processed once
Space	O(number of reachable states)	Cache stores all visited states

The balancing rule keeps the reachable state space manageable. Even with n = 10000, the number of distinct reachable count configurations stays small enough for Python within the limits.

Test Cases

# helper: run solution on input string, return output string
import sys
import io
from functools import lru_cache

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

    input = sys.stdin.readline

    houses = ['G', 'H', 'R', 'S']
    name_map = {
        'G': 'Gryffindor',
        'H': 'Hufflepuff',
        'R': 'Ravenclaw',
        'S': 'Slytherin'
    }

    idx = {c: i for i, c in enumerate(houses)}

    n = int(input())
    s = input().strip()

    possible = [False] * 4

    @lru_cache(maxsize=None)
    def dfs(i, g, h, r, s_cnt):
        counts = [g, h, r, s_cnt]

        if i == n:
            mn = min(counts)

            for j in range(4):
                if counts[j] == mn:
                    possible[j] = True
            return

        ch = s[i]

        if ch != '?':
            nxt = counts[:]
            nxt[idx[ch]] += 1
            dfs(i + 1, *nxt)
        else:
            mn = min(counts)

            for j in range(4):
                if counts[j] == mn:
                    nxt = counts[:]
                    nxt[j] += 1
                    dfs(i + 1, *nxt)

    dfs(0, 0, 0, 0)

    ans = []

    for i in range(4):
        if possible[i]:
            ans.append(name_map[houses[i]])

    return "\n".join(ans) + "\n"

# provided sample
assert run("11\nG????SS???H\n") == "Gryffindor\nRavenclaw\n", "sample 1"

# minimum input
assert run("1\nG\n") == "Hufflepuff\nRavenclaw\nSlytherin\n", "single fixed"

# all ambiguous
assert run("4\n????\n") == (
    "Gryffindor\n"
    "Hufflepuff\n"
    "Ravenclaw\n"
    "Slytherin\n"
), "all houses possible"

# imbalance case
assert run("2\nH?\n") == (
    "Gryffindor\n"
    "Ravenclaw\n"
    "Slytherin\n"
), "H cannot be minimal"

# all same fixed house
assert run("3\nSSS\n") == (
    "Gryffindor\n"
    "Hufflepuff\n"
    "Ravenclaw\n"
), "S too large"

Test input	Expected output	What it validates
1 / G	all except Gryffindor	Single forced assignment
4 / ????	all four houses	Symmetric balancing
2 / H?	G,R,S	Ambiguous branching
3 / SSS	G,H,R	One house permanently ahead

Edge Cases

Consider:

2
H?

After the first student:

(0,1,0,0)

The second student may only choose among minimal houses:

G, R, S

The DFS branches into exactly these three states. None produce H as minimal afterward. The algorithm correctly excludes Hufflepuff.

Now consider:

4
????

The DFS repeatedly distributes students among currently minimal houses. Because all houses begin equal, every branch preserves near-balance.

One reachable terminal state is:

(1,1,1,1)

All four houses are minimal, so Hermione may choose any house. The memoized DFS explores this without exponential duplication because many different assignment orders collapse into the same count tuple.

Finally, consider a strongly skewed input:

3
SSS

The counts become:

(0,0,0,3)

Hermione may choose only among the minimal houses:

G, H, R

The algorithm handles this naturally because terminal processing simply checks which counts equal the minimum.