# Subway
TODO

# Stolen String
The solutions for $k \in \{2,3\}$ are completely different from the the rest of the subtasks (which you should probably be able to guess from how big the difference in $n$ is).
## K=2
Due to the [Ham-sandwich-theorem](https://en.wikipedia.org/wiki/Ham_sandwich_theorem), the answer is always at most $K$. See [here](https://www.youtube.com/watch?v=yuVqxCSsE7c) for an explanation.
We will first check if the answer is 1 by trying every possible cut. If it is not 1, it is then 2.
As there are $O(n)$ possible cuts, we need to be able to check each one in $O(1)$. Suppose we are trying the following cut: person 1 gets $[0, k]$ and person 2 $[k+1, n-1]$. We then need to check if the number of a's in $[0,k]$ is equal to the number of a's in $[k+1,n-1]$. Let $S$ be the input string. To do this, we can create an array $A$, where $A[i]=$ 1 if $S$[i]=A, otherwise 0. We can then create a prefix sum over this to efficiently count the number of a's. We need to do the same for the number of b's. Of course, we could also try $k=0$, then $k=1$, $k=2$ etc and update the information along the way.
## K=3
We will first check if the answer is 1. If not, check if the answer is 2. If is not 2, it is 3.
How can we check if we can solve the problem using two cuts for $N=10^5$? WLOG, we will iterate over each possible point for making the first cut, and give everything to the left of it to some person. We now need to quickly check if there is a second cut point that gives a balanced division. WLOG, we can also assume that the first and last part of the string will be given to person 1, and the middle part to person 2. Further, we can realize that we only need to worry about person 1; we simply need to find a division where they get exactly half of all characters. From fixing the left endpoint, we know that person 1 already has some amount of a,b,c's. Then, we are looking for a suffix to add so we reach exactly half. This can be found using a suffix sum over occurences of each character, and a binary search. $O(N\log(N))$.

## Subtask 3
As $N$ is very small, it suffices to check all $2^N$ possible divisions of items between the people.
## Subtask 4
Because $K$ cuts always suffice, it might be possible to try all of them. How many are there? It can be thought of as: we have $N-1$ possible cutting point, and we want to select $K$ unique. It turns out that this is equal "N choose K", or ${N \choose K}$. ${40 \choose 6} \approx 4 \cdot 10^6$. Implementing this using for example reqursion should suffice well.
## Subtask 5
One way to solve this is using meet-in-the-middle. However, there is a faster and nice DP solution.

The key to solving the problem using DP is to think about the problem in terms of person 1: we want to select cuts so that they get exactly half of each character. Suppose we do a recursive bruteforce, only keeping track of person 1. Then, if we ever have more than half of some character, we can instantly prune this part of the recursion. Intuitively, there aren't many possible different possible valid partial partitions, which motivates a DP. We do
$$\text{DP[position][current person 1 partition][person 1 or 2]=min cuts}$$
Notice that we don't need to keep track of person 2- it follows from the rest of the state. Then, the transitions are that we either add $S$[position] to the current person we are considering, or pay 1 and switch person (making a cut).
But how do we actually check visited states where the state is a "current partition"? More exactly, we will keep track of how many of each character has been given to player 1. One solution is to store the character counts in a vector of size $K$. Then, our dp data structure could be

$$\text{map<vector<int>, int> dp[2][40]}$$
Because of the generous time limit, this will most likely get accepted. However, there is a better way. As we run our DP, we will keep track of the current partition as an integer. Lets $P[c]$=1+the number of occurences of the character $c$ in the current partition. Let $C[c]$=the number of occurences of $c$ in the input string. Then, our partition will be described by the following expression:

$$(P[a])+(P[b]*C[a])+(P[c]*C[a]*C[b])+\dots$$

This might remind of you of remapping 2D coordinates into a unique 1D integer. In fact, our current partition can be viewed as a point in high-dimensional space that we map into 1D.

How many states can there be? Intuitively, we want the number of occurences of each number to be close to $e$. Therefore, we guess that the worst-case is that there are 3 occurences for 8 characters, and 4 for the 4 remaining. This gives ~$2 \cdot 10^6$. If you are not convinced by this, you can do another DP to calculate the worst case, which is not far off (they might even be equal to this construction, I don't remember). Note that under this analysis, $K \approx \frac{N}{3}$ are the hardest, so this solution can handle $N, K \leq 40$.

The official testdata is weak, so $10^5$ suffices. Python is memory-inefficient, so we can't use more than $81 \cdot 10^6$ ints. It may be more memory-efficient if we squeeze it into a 1D-array.

dp = [[-1] * int(1e6) for i in range(81)]
hashfactor = [] # Prefix product of C array
neck = [] # Input remapped to ints
balanced = [] # C array, where each item is divided by 2

def best(i, state, h, playerA):
    if i == len(neck):
        return 0 if state == balanced else 10001

    if dp[i + playerA * 40][h] != -1:
        return dp[i + playerA * 40][h]

    ret = 10000

    if playerA:
        ret = min(ret, best(i + 1, state, h, 1))
        ret = min(ret, 1 + best(i, state, h, 0))
    else:
        ret = min(ret, 1 + best(i + 1, state, h, 1))
        state[neck[i]] += 1
        if state[neck[i]] <= balanced[neck[i]]:
            ret = min(ret, best(i + 1, state, h+hashfactor[neck[i]], 0))
        state[neck[i]] -= 1

    dp[i + playerA * 40][h] = ret
    return ret


s = input()

# Remap characters to ints
mapping = {}
for c in s:
    if c not in mapping:
        mapping[c] = len(mapping)
    neck.append(mapping[c])

cnt = [0] * len(mapping)
for c in neck:
    cnt[c] += 1

for count in cnt:
    if count % 2 == 1:
        print(-1)
        exit(0)

k = len(mapping)

hashfactor = [1] * k 
balanced = [0] * k
for i in range(k):
    balanced[i] = cnt[i] // 2
    for j in range(i + 1, k):
        hashfactor[j] *= (balanced[i] + 1)

state = [0] * k

print(best(0, state, 0, 0))

# The Space Patrol
TODO
One of the most beautiful problems ever