TigerMaster | Topcoder Archive

Problem Statement

To celebrate the Lunar New Year that starts the Year of the Tiger, the problems in this set feature tigers.

The jungle around us contains N interesting locations, numbered from 0 to N-1.

Some pairs of locations are connected by paths. There are M such paths, numbered from 0 to M-1. Note the constraints on M.

All paths are bidirectional. There can be multiple paths connecting the same two locations. There are no self-loops: for each path its two endpoints are distinct.

No two paths intersect. More precisely, whenever two paths need to cross each other, one of them goes over the other - that's easily done in a jungle!

Each path has a difficulty level that is proportional to the number of tigers who live around that path.

In order to become a tiger master, one has to make a trip into the jungle. The trip must consist of at least 20 mutually distinct paths. The paths must obviously be consecutive (each starting in the location where the previous one ended) and they must be chosen so that the difficulty level of the trip never decreases.

Take the first step to becoming a tiger master: find one such trip or determine that no such trip is possible.

You are given the ints N and M. You are also given the int[]s X, Y and D that describe the paths: for each i, path number i connects locations X[i] and Y[i] and its difficulty level is D[i].

If there is a tiger master trip, return a int[] of length at least 21: the number of the location where your trip starts followed by the numbers of paths in the order in which they should be traversed. Any valid solution will be accepted.

If there is no valid tiger master trip, return an empty int[].

Definition

Class:: TigerMaster
Method:: train
Parameters:: int, int, int[], int[], int[]
Returns:: int[]
Method signature:: int[] train(int N, int M, int[] X, int[] Y, int[] D)
(be sure your method is public)

Constraints

N will be between 2 and 100, inclusive.
M will be between 10*N and 1000, inclusive.
X, Y and D will have exactly M elements each.
Each element of X will be between 0 and N-1, inclusive.
Each element of Y will be between 0 and N-1, inclusive.
For each i, X[i] will differ from Y[i].
Each element of D will be between 0 and 1000, inclusive.

Examples

```
2
```
```
23
```
```
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0}
```
```
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1}
```
```
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
```
```
Returns: {1, 21, 6, 1, 19, 22, 3, 10, 14, 13, 12, 2, 8, 15, 0, 9, 7, 17, 4, 20, 5 }
```
Two locations connected by 23 distinct paths, each with the same difficulty. You may take any 20 of those (or more if you wish to), just make sure you don't take the same path twice. Note that element #0 of the example return value (i.e., the number 1) is the number of the starting location. Only the following numbers are path numbers.

{1, 2, 2, 2, 2, 0, 0, 1, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 0, 1, 0, 2, 0, 2, 0, 0, 1, 2}

{0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 2, 0, 0, 1, 1, 0, 0, 0, 2, 1, 2, 2, 1, 1, 2, 0, 1, 2, 2, 1}

{55, 73, 50, 53, 13, 61, 72, 30, 91, 76, 73, 16, 46, 65, 12, 89, 60, 98, 45, 98, 33, 72, 39, 33, 14, 48, 1, 80, 79, 55}

Returns: {0, 26, 14, 4, 24, 11, 7, 23, 18, 12, 25, 2, 0, 16, 5, 6, 21, 1, 10, 9, 28 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.