I haven't tried to prove a bound, but my in-contest solution is able to pass system tests with a self-enforced limit of 1200 jumps. With some improvements (sorting things in the right order and refining the greedy algorithm), I have a deterministic solution in the practice room right now that passes system tests with a limit of 950.

The main idea is that regardless of how many jumps we've used so far, if we make $$$2k$$$ consecutive jumps where $$$k$$$ of the jumps are positive and $$$k$$$ are negative, we can get an overall jump of any number in $$$-k^2, -k^2 + 2, \dots, k^2 - 2, k^2$$$; in other words, any number between $$$-k^2$$$ and $$$k^2$$$ with the same parity as $$$k$$$. This lets us generate any desired delta $$$d$$$ in about $$$2 \sqrt d$$$ jumps.

By choosing an end result in the middle of the range of coordinates, this gives us a worst case of about $$$50 \cdot 2 \cdot \sqrt{1250}$$$, which is slightly over 3500.

The main improvement we can make on top of this is that before we use this technique, we should greedily use our small jumps to move each frog directly to its target, until jumping directly toward the target is no longer helpful. Doing this with every frog in the right order gets the 950 result above.

Wow, Thanks for this problem! It's such a a cool idea to uniquely determine state by combining position of both robots and then applying bfs using it.

I really liked the problem. Although I didn't have a single clue during the contest. This was my first SRM, thanks for such a beautiful problem(at least for me). I will definitely look forward for coming SRMs.

This problem will be hard to solve in Python with the given TL. There are 40^4 states and 16 times more operations. That's too much for Python in 2 seconds. See for example the following simple code which just tries to add 40**4 integers in a list (very crude simulation of the BFS):

q = list()
q.append(1)

idx = 0
while idx < len(q):
    num = q[idx]
    for i in range(16):
        if len(q) + 1 < 40**4:
            q.append(idx + i)
    idx += 1

This runs in almost 4 seconds on a more powerful machine than TC uses.

Uhm...? It shows it as complete in the Arena (even while I was writing the editorial, which was on the day of the competition)? If you are looking at the Web arena — don't :D