GCJ 2019 Round 1A

Pylons

If we properly take some k, (i,j) -> ((i+k)%H,j+1) -> ((i+2k)%H,j+2) -> ... is a path satisfying the given conditions. I don't have any proof, but at least under this constraints, it is correct. In addition, (H,W)=(4,4) doesn't work, so this case is treated as an exception. I couldn't come up with a randomized solution. It is really simple. Good problem.

Golf Gophers

lcm(2,3,5,7,11,13,17) is a little small, so I tried lcm(5,6,7,8,11,13,17). By Chinese remainder theorem, we can figure out the answer uniquely. Even if we don't have the library for solving equations, the answer can be found by trying the all integers from 0 to M.

Alien Rhyme

This is the easiest problem in these. Greediliy pair the strings having the longest common suffix, and do this repeatedly until such a pair doesn't exist. Though N<=1000, we should carefully implement an algorithm. Actually, some quadratic algorithms might be too slow to pass large cases. For avoiding such a trouble, so I wrote O(1000*50*17) time algorithm using std::map. Needless to say, Trie runs more quickly, but it takes a lot of time for implementation.