Connection Status:
Competition Arena > Frogs

Frogs

SRM 822 · 2022-01-16 · by misof

SRM 822 · 2022-01-16 · by misof · Sorting
Class Name: Frogs
Return Type: int[]
Method Name: move
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

There are N frogs and 2*N+1 lilypads. The lilypads are arranged in a row and numbered from 0 to 2*N.

For each frog you are given its initial lilypad start[i] and the desired destination goal[i].


Frogs can only move by jumping. The jumps must be performed one at a time. In each jump, the jumping frog must leap over exactly one other frog and land on an empty lilypad.


Find any sequence of at most 1000 jumps that brings all frogs to their desired destinations.


Suppose your sequence of jumps is:

  • a frog jumps from lilypad s[0] to lilypad t[0],
  • then a frog jumps from s[1] to t[1],
  • then ...

Return the int[] { s[0], t[0], s[1], t[1], ... }.

Notes

  • A solution within the stated limit always exists.
  • Any valid solution will be accepted.

Constraints

  • N will be between 3 and 30, inclusive.
  • start will contain N elements.
  • goal will contain N elements.
  • The elements of start will be distinct numbers between 0 and 2*N, inclusive.
  • The elements of goal will be distinct numbers between 0 and 2*N, inclusive.
Examples
0)
{2, 3, 5}
{2, 3, 5}
Returns: {3, 0, 0, 3 }

All frogs are already in their desired places, so an empty sequence would have been a valid answer. Just to illustrate that you are not required to minimize the number of jumps, one of our frogs jumps over the other twice (there and back).

1)
{2, 3, 5}
{6, 0, 5}
Returns: {3, 0, 2, 6 }

First frog 1 jumps from lilypad 3 to lilypad 0, then frog 0 jumps from lilypad 2 to lilypad 6. (Note that making the same jumps in the opposite order is not a valid solution, as frog 0 would jump over two frogs in the same jump and then frog 1 would jump over no frogs at all.)

2)
{0, 1, 2, 3}
{6, 7, 5, 3}
Returns: {2, 5, 1, 4, 4, 7, 0, 4, 4, 6 }
3)
{2, 3, 5}
{2, 3, 0}
Returns: {3, 0, 5, 1, 1, 4, 0, 3, 3, 6, 4, 1, 1, 5, 6, 4, 5, 3, 3, 6, 6, 3, 3, 1, 2, 6, 1, 5, 5, 2, 4, 1, 1, 5, 6, 4, 5, 3, 3, 6, 2, 5, 5, 3, 4, 2, 3, 0, 6, 1, 1, 3 }
4)
{3, 2, 5, 0, 4, 7, 8}
{6, 1, 2, 4, 9, 3, 5}
Returns: {3, 1, 5, 3, 8, 5, 4, 6, 6, 8, 7, 9, 9, 6, 5, 7, 7, 4, 8, 5, 5, 8, 4, 7, 7, 14, 8, 5, 6, 4, 4, 7, 3, 6, 6, 12, 7, 4, 5, 3, 3, 6, 2, 5, 5, 10, 6, 3, 4, 2, 2, 5, 1, 4, 4, 8, 5, 2, 3, 1, 1, 4, 0, 3, 3, 6, 12, 9, 9, 7, 7, 5, 5, 3, 3, 0, 8, 12, 4, 8, 2, 7, 7, 4, 10, 7, 7, 5, 5, 1, 6, 10, 4, 9, 9, 6, 10, 7, 7, 2, 6, 10, 10, 3, 8, 13, 13, 10, 14, 11, 11, 9, 10, 14, 9, 13, 13, 10, 10, 13, 13, 11, 12, 6, 11, 4, 14, 5, 5, 9, 4, 7, 7, 5, 6, 4, 4, 6, 2, 4, 0, 2 }

Submissions are judged against all 170 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Frogs with a public method vector<int> move(vector<int> start, vector<int> goal) · 170 test cases · 2 s / 256 MB per case

Submitting as anonymous