For magic portals, you are right in your approach.

To iterate through all pairings, we could just recursively generate all pairings by, at each point, iterating through all pairings with some "first" value. For example, for 1 2 3 4 5 6, we would pair 1 with all [2,6] and recursively generate pairings on the array. The branches never overlap (as they have a different pair), so we generate all pairs.

This is also the usaco problem WORMHOLE, whose solution can be found here

For Surprise Birthday I do think brute force would work actually, if you think about it in the right direction.

Instead of counting the number of ways to go from a string to our encrypted string, count the number of ways to go from our encrypted string to some other string using the reverse operation, where we transition like so

aaaaa aaaaa X -> aaaaa X aaaaa X aaaaa — > aaaaa X or X aaaaa X aaaaa aaaaa — > X aaaaa

we have O(n^2) possibilities for the string and O(n) transitions from each string to a different one (both following from that the new string must either be a prefix or a suffix of the old string) so we can use a bfs approach to get our solution. With naive string comparison, we can find the transitions in O(n^2) so we get an O(n^4) solution. If this is too slow, we can precompute all of the comparisons in O(n^3) time by using an unordered map or such (however with the size of n i feel that the constants matter more).

This sounds pretty cancerous to implement though so i haven't, so im not certain that this works.

no