Newtech66's blog

By Newtech66, history, 3 years ago, In English

The problems:

Magic Portals

Surprise Birthday

Roaming

My thoughts:

Magic Portals
Surprise Birthday
Roaming

Please help me in getting a solution to each of these problems.

Note: Contest ended a long time ago so don't worry about possible cheating.

 
 
 
 
  • Vote: I like it
  • +14
  • Vote: I do not like it

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

no