We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Unique Divide And Conquer

Unique Divide And Conquer

Problem
Submissions
Leaderboard
Discussions
Editorial

Divide-and-Conquer on a tree is a powerful approach to solving tree problems.

Imagine a tree, , with vertices. Let's remove some vertex from tree , splitting into zero or more connected components, , with vertices . We can prove that there is a vertex, , such that the size of each formed components is at most .

The Divide-and-Conquer approach can be described as follows:

  • Initially, there is a tree, , with vertices.
  • Find vertex such that, if is removed from the tree, the size of each formed component after removing is at most .
  • Remove from tree .
  • Perform this approach recursively for each of the connected components.

We can prove that if we find such a vertex in linear time (e.g., using DFS), the entire approach works in . Of course, sometimes there are several such vertices that we can choose on some step, we can take and remove any of them. However, right now we are interested in trees such that at each step there is a unique vertex that we can choose.

Given , count the number of tree 's such that the Divide-and-Conquer approach works determinately on them. As this number can be quite large, your answer must be modulo .

Input Format

A single line of two space-separated positive integers describing the respective values of (the number of vertices in tree ) and (the modulo value).

Constraints

  • is a prime number.

Subtasks

  • for of the maximum score.
  • for of the maximum score.

Output Format

Print a single integer denoting the number of tree 's such that vertex is unique at each step when applying the Divide-and-Conquer approach, modulo .

Sample Input 0

1 103

Sample Output 0

1

Explanation 0

For , there is only one way to build a tree so we print the value of as our answer.

Sample Input 1

2 103

Sample Output 1

0

Explanation 1

For , there is only one way to build a tree:

image

This tree is not valid because we can choose to remove either node or node in the first step. Thus, we print as no valid tree exists.

Sample Input 2

3 103

Sample Output 2

3 

Explanation 2

For , there are valid trees depicted in the diagram below (the unique vertex removed in the first step is shown in red):

image

Thus, we print the value of as our answer.

Sample Input 3

4 103

Sample Output 3

4

Explanation 3

For , there are valid trees depicted in the diagram below (the unique vertex removed in the first step is shown in red):

image

The figure below shows an invalid tree with :

image

This tree is not valid because we can choose to remove node or node in the first step. Because we had four valid trees, we print the value of as our answer.

Author

gorbunovdv

Difficulty

Advanced

Max Score

90

Submitted By

980

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy