InverseRMQ | Topcoder Archive

Problem Statement

The range maximum query (RMQ) problem looks as follows: You are given a permutation P of the numbers 1 through n, and a sequence of queries. Each query is a pair of integers (L,R) such that 1 <= L <= R <= n. The answer to the query is the maximum of the values that occur in P at (1-based) positions L through R, inclusive.

For example, if P is the permutation (3,1,4,2,5), then:

The answer to the query (1,2) is max(3,1)=3.
The answer to the query (2,4) is max(1,4,2)=4.
The answer to the query (4,5) is max(2,5)=5.

In this problem, we ask you to solve the inverse problem. You are given the int n, and three int[]s A, B, and ans, each containing the same number of elements. We are looking for a permutation P of numbers 1 through n with the following property: For each valid i, the answer to the query (A[i], B[i]) must be ans[i]. Return "Possible" (quotes for clarity) if at least one such permutation P exists, and "Impossible" otherwise.

Definition

Class:: InverseRMQ
Method:: possible
Parameters:: int, int[], int[], int[]
Returns:: String
Method signature:: String possible(int n, int[] A, int[] B, int[] ans)
(be sure your method is public)

Constraints

n will be between 1 and 1,000,000,000, inclusive.
A will contain between 1 and 50 elements, inclusive.
A, B, and ans will each contain the same number of elements.
Each element in A will be between 1 and n, inclusive.
Each element in B will be between 1 and n, inclusive.
For all i, A[i] will be less than or equal to B[i].
Each element in ans will be between 1 and n, inclusive.

Examples

```
5
```
```
{1,2,4}
```
```
{2,4,5}
```
```
{3,4,5}
```
```
Returns: "Possible"
```
This is the example from the problem statement. One valid permutation is (3,1,4,2,5). There are also some other valid permutations.
```
3
```
```
{1,2,3}
```
```
{1,2,3}
```
```
{3,3,3}
```
```
Returns: "Impossible"
```
The only sequence that corresponds to these queries is (3,3,3), but that is not a permutation.

{1,101,201,301,401,501}

{100,200,300,400,500,600}

{100,200,300,400,500,600}

Returns: "Possible"

One valid permutation is the permutation (1,2,3,...,600).

```
1000000000
```
```
{1234,1234}
```
```
{5678,5678}
```
```
{10000,20000}
```
```
Returns: "Impossible"
```
There is no permutation such that two identical queries have different answers.

{1,2,3,4,5,6,7,8}

{1,2,3,4,5,6,7,8}

{4,8,2,5,6,3,7,1}

Returns: "Possible"

The only valid permutation is clearly (4,8,2,5,6,3,7,1).

```
1000000000
```
```
{1}
```
```
{1000000000}
```
```
{19911120}
```
```
Returns: "Impossible"
```
Obviously, for n=1,000,000,000 the maximum of the entire permutation must be 1,000,000,000.

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.