CandyCupRunningCompetition | Topcoder Archive

Problem Statement

Alice is going to host a competition in running, called the Candy Cup. Candy Cup will take place in a city that consists of N intersections. The intersections are numbered 0 through N-1.

There are M roads in the city. The roads are numbered 0 through M-1. Each road is bidirectional and connects two intersections. There are no self-loops. Each pair of intersections is directly connected by at most one road. Note that the road network is not guaranteed to be connected. (That is, it may be impossible to travel between some pairs of intersections.)

You are given the description of the city: the int N and two int[]s A and B, each with M elements. For each valid i, the road number i connects the intersections A[i] and B[i].

As a preparation for the Candy Cup, Alice has placed some candies into the middle of each road. For each i, she placed exactly 3^i (three to the power of i) candies into the middle of road i.

The rules of Candy Cup are really simple. Each participant starts at the intersection 0 and must reach intersection N-1 by following some roads. Additionally, each time a participant takes a road, they must pick up a candy from that road. (Once there are no candies left on a road, participants in the race are not allowed to take that road.) Note that different participants may use a different number of roads to reach the finish.

Let F be the largest possible number of participants that can finish Candy Cup by reaching the finish in a valid way. Return the value (F modulo 1,000,000,007).

Definition

Class:: CandyCupRunningCompetition
Method:: findMaximum
Parameters:: int, int[], int[]
Returns:: int
Method signature:: int findMaximum(int N, int[] A, int[] B)
(be sure your method is public)

Constraints

N will be between 2 and 2000, inclusive.
A and B will contain between 0 and 2,000 elements, inclusive.
A and B will each contain the same number of elements.
Each element of A and B will be between 0 and N-1, inclusive.
No two roads will connect the same pair of intersections.
For each valid i, A[i] will be different from B[i].

Examples

```
3
```
```
{0,1}
```
```
{1,2}
```
```
Returns: 1
```
The only finisher will take the route 0-1-2. Afterwards, there are no candies left on road 0.
```
4
```
```
{0,1,0,2}
```
```
{1,3,2,3}
```
```
Returns: 10
```
One participant will take the route 0-1-3 and nine more will take the route 0-2-3.
```
3
```
```
{0}
```
```
{1}
```
```
Returns: 0
```
```
5
```
```
{}
```
```
{}
```
```
Returns: 0
```

{1,1,2,0,4,3,0,1,4}

{3,2,3,1,5,5,2,4,3}

Returns: 39

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.