The problems:
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.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Since the maximum possible number of pairings is $$$10395$$$, I could just check all possible pairings for a cycle. But I'm not sure how I would implement this.
I have no clue. I do not think a brute force would work here.
I can precalculate shortest paths between the pharmacies, fixing the starting and ending. Then for every other vertex, I could take the minimum over all choices of starting and ending pharmacies. Then I could take the overall minimum. It works, but I'm having trouble implementing so much neatly.
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.
Name |
---|
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