Connection Status:
Competition Arena > ParadePlanner

ParadePlanner

SRM 779 · 2020-02-20 · by misof

SRM 779 · 2020-02-20 · by misof · Dynamic Programming, Graph Theory, Math
Class Name: ParadePlanner
Return Type: long
Method Name: count
Arg Types: (int, int, int, vector<int>)
Problem Statement

Problem Statement

You are given the map of a city: an undirected graph on N vertices, numbered from 0 to N-1. Your task is to plan a parade somewhere in the city. The people in the parade want to walk along five consecutive streets, and obviously, the five streets should be distinct. The parade may cross the same intersection multiple times. Formally, the parade is a tour of length 5. Return the number of different parades that can be organized in the given city

Use the following pseudocode to generate the graph: 

state = seed

for x = 0 .. N-1:
    for y = x+1 .. N-1:
        state = (state * 1103515245 + 12345) modulo 2^31
        if state < threshold:
            add edge x-y

L = length(toggle) / 2
for i in 0 .. L-1:
    x = toggle[2*i]
    y = toggle[2*i+1]
    if we have the edge x-y:
        remove edge x-y
    else:
        add edge x-y

Notes

  • The order in which the parade traverses the streets matters. Thus, there can be multiple parades that use the same set of streets.
  • You should return the actual number of possible parades and NOT its value modulo something.

Constraints

  • N will be between 1 and 500, inclusive.
  • seed will be between 0 and 2^31 - 1, inclusive.
  • threshold will be between 0 and 2^31 - 1, inclusive.
  • toggle will have between 0 and 200 elements, inclusive.
  • toggle will have an even number of elements.
  • Each element of toggle will be between 0 and N-1, inclusive.
  • For each valid i, toggle[2*i] will be smaller than toggle[2*i+1].
Examples
0)
10
47
0
{0,1,1,7,2,7,3,4,2,3}
Returns: 2

The generated city has no streets. Then we use toggle[] to add five streets. This creates two possible parades: 0-1-7-2-3-4 and 4-3-2-7-1-0.

1)
4
47
2147483647
{}
Returns: 72

The generated city has four locations, each two of them connected by a street. There's quite a number of possible parades. One of them is 0-1-2-3-0-2.

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

Six locations on a circle. We can choose where we start the parade (6 options) and we can choose the direction in which we walk (2 options). Once we make those choices, the route of the parade is fixed.

3)
7
47
1000000000
{0,1,0,1,0,2,0,3}
Returns: 46

We generate a random city with 8 streets: 0-1, 0-2, 0-4, 0-6, 1-4, 1-5, 2-3, and 2-4. Then we toggle street 0-1 twice (so that it remains in the city), street 0-2 (to make it disappear) and street 0-3 (to make it appear).

4)
500
4247
0
{}
Returns: 0

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

Coding Area

Language: C++17 · define a public class ParadePlanner with a public method long long count(int N, int seed, int threshold, vector<int> toggle) · 51 test cases · 2 s / 256 MB per case

Submitting as anonymous