BearPermutations2
SRM 673 · 2015-10-30 · by Errichto
Problem Statement
Bear Limak loves algorithms and tolerates data structures. Today he learned about the Cartesian tree. You can find a detailed description of this tree at https://en.wikipedia.org/wiki/Cartesian_tree. Below we give a shorter description that is sufficient to solve this problem.
Let A be a sequence of distinct numbers. Each such sequence defines a unique Cartesian tree. The Cartesian tree is determined by the following rules:
- The Cartesian tree is a rooted binary tree.
- The nodes of the tree correspond to the elements of A.
- An in-order traversal of the tree prints the sequence A.
- The tree is a heap.
A more detailed explanation of the third rule: Consider any node in the tree, and let x be the number in this node. All numbers in the left subtree must appear in A before x, and all numbers in the right subtree must appear in A after x.
A more detailed explanation of the fourth rule: For each node, the number in the node must be strictly smaller than each of the numbers in the children of this node.
Below is a figure that shows the Cartesian tree determined by the sequence A = {9,3,7,1,8,12,10,20,15,18,5}.
We will now define the score of a Cartesian tree. Let T be the Cartesian tree determined by the sequence A. In the tree T there are some nodes that have two children. For each such node, look at the numbers in those two children, find the indices of those two numbers in A, and compute their (positive) difference. The score of the tree T is the sum of all these differences.
For example, in the above tree we have four nodes that have two children each: the nodes with numbers 1, 3, 10, and 15. The children of node 1 are the nodes 3 and 5. In the original sequence A, the values 3 and 5 have (0-based) indices 1 and 10. The difference between these indices is 10 - 1 = 9. For the other three nodes with two children, the differences between their indices are 2, 3, and 2. Hence, the score of this tree is 9 + 2 + 3 + 2 = 16.
You are given the
Constraints
- N will be between 1 and 100, inclusive.
- MOD will be between 3 and 10^9, inclusive.
- MOD will be prime.
3 502739849 Returns: 4
For N=3 there are 3! = 6 distinct permutations. Four of these produce Cartesian trees with score 0. The remaining two are the permutations (2,1,3) and (3,1,2). Each of these produces a Cartesian tree with score 2. Hence, the sum of all six scores is 0+0+0+0+2+2 = 4.
1 1000003 Returns: 0
4 973412327 Returns: 38
100 89 Returns: 49
2 209349097 Returns: 0
Submissions are judged against all 24 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BearPermutations2 with a public method int getSum(int N, int MOD) · 24 test cases · 2 s / 256 MB per case