CandyCupRunningCompetition
SRM 632 - TCO14 Wildcard Sweep · 2014-08-25 · by dreamoon
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
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).
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].
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
6
{1,1,2,0,4,3,0,1,4}
{3,2,3,1,5,5,2,4,3}
Returns: 39
Submissions are judged against all 50 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CandyCupRunningCompetition with a public method int findMaximum(int N, vector<int> A, vector<int> B) · 50 test cases · 2 s / 256 MB per case