Connection Status:
Competition Arena > MarioJumper

MarioJumper

TCO20 Europe Qualification · 2020-10-02 · by misof

TCO20 Europe Qualification · 2020-10-02 · by misof · Graph Theory, Simple Search, Iteration
Class Name: MarioJumper
Return Type: long
Method Name: minTime
Arg Types: (vector<string>, vector<int>, int, long long, long long)
Problem Statement

Problem Statement

You are playing a simple Mario-style computer game. The game takes place in a vertically placed two-dimensional plane divided into a grid of unit square cells. The rows and columns of this grid have integer coordinates (row, column), with column numbers growing left to right and row numbers growing bottom to top.

The game world itself consists of cells (r, c) such that 0 <= r and 0 <= c < N. In column i, the bottommost H[i] cells are solid ground. The bottom of the level is solid, as if all the cells (-1, c) also contained solid ground. All other cells contain air.

For example, several bottom rows of the level corresponding to H = {1, 4, 0, 2, 0, 2} are shown below. ('#' is solid ground, '.' is air, '=' shows the additional solid ground below the level.) 


column: 012345

        ......
        ......
        .#....
        .#....
        .#.#.#
        ##.#.#
        ======
     H: 140202

You are given a compressed description of the game world: a String[] pieces containing strings of digits and an int[] counts. You can build a string that describes the game world by concatenating counts[0] copies of pieces[0], followed by counts[1] copies of pieces[1], and so on. N (the width of the game world) is equal to the length of the resulting string, and for each i the digit at index i in the resulting string gives the height H[i].


You are controlling a character. The character can move in steps and jumps. Each movement (regardless of whether it's a step or a jump) takes 1 second. Both steps and jumps can be made in either direction. Jumps have maximum height J and a maximum span of two columns. All possible movements look as follows:

  • A step from column c1 to an adjacent column c2 is possible if and only if H[c2] does not exceed H[c1].
  • A jump from column c1 to an adjacent column c2 is possible if and only if H[c2] does not exceed H[c1] + J.
  • A jump from column c1 over an adjacent column c2 to the following column c3 is possible if and only if neither of H[c2] and H[c3] exceeds H[c1] + J.

As the last part of each movement, after reaching the destination column the character falls straight down until it hits the ground in that column.

Your character starts on the ground in column S. You want to reach column F as quickly as possible. Return the minimum time in seconds in which it can be done, or -1 if it's impossible.

Constraints

  • pieces will contain between 1 and 50 elements, inclusive.
  • Each element of pieces will have between 2 and 50 characters, inclusive.
  • Each character in pieces will be a digit ('0'-'9').
  • counts will contain the same number of elements as pieces
  • Each element of counts will be between 1 and 10^9, inclusive.
  • J will be between 1 and 9, inclusive.
  • S and F will be valid column numbers.
Examples
0)
{"140202"}
{1}
3
0
4
Returns: 2

The world from the example in the problem statement. If our jump height is 3, we can get from column 0 to column 4 in two jumps.

1)
{"14", "02"}
{1, 2}
2
0
5
Returns: -1

The same world as in the previous example, only this time given as a concatenation of smaller pieces. In this example the jump length is too small, so we actually cannot move from column 0 at all.

2)
{"140202"}
{1}
2
5
0
Returns: 3

Direction of travel matters. This is the same situation as in Example 1, but with start and finish swapped. In this case we can jump from column 5 to column 3, from there we can jump to column 1, and from column 1 we can either step or jump to column 0.

3)
{"000"}
{1000000000}
9
0
2999999999
Returns: 1500000000

Even though the level is straight and we could walk from start to finish, jumping is twice as fast.

4)
{"0123456789"}
{10}
1
3
95
Returns: 83

Jumping up the stairs. As J = 1, most of the jumps we'll make will be just to the adjacent column. Only from the columns of height 9 we can make a jump of length 2.

5)
{"12", "34", "56", "789"}
{12, 34, 56, 789}
3
470
470
Returns: 0

The obligatory example that shows the situation in which we start and end in the same column.

8)
{"90009"}
{1}
8
4
0
Returns: -1

There is no way to preserve height in this scenario. As soon as we leave the starting column (regardless of whether by a step or a jump), we will fall down to height 0, and from there we won't be able to reach the desired column.

9)
{"12", "34", "56", "789"}
{12, 34, 56, 789}
9
123
2345
Returns: 1111

If your jump height is 9, you don't really care about the terrain.

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

Coding Area

Language: C++17 · define a public class MarioJumper with a public method long long minTime(vector<string> pieces, vector<int> counts, int J, long long S, long long F) · 134 test cases · 2 s / 256 MB per case

Submitting as anonymous