Connection Status:
Competition Arena > InverseRMQ

InverseRMQ

TCO14 Round 2C · 2014-03-26 · by cgy4ever

TCO14 Round 2C · 2014-03-26 · by cgy4ever · Math
Class Name: InverseRMQ
Return Type: String
Method Name: possible
Arg Types: (int, vector<int>, vector<int>, vector<int>)
Problem Statement

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.

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
0)
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.

1)
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.

2)
600
{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).

3)
1000000000
{1234,1234}
{5678,5678}
{10000,20000}
Returns: "Impossible"

There is no permutation such that two identical queries have different answers.

4)
8
{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).

5)
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.

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

Coding Area

Language: C++17 · define a public class InverseRMQ with a public method string possible(int n, vector<int> A, vector<int> B, vector<int> ans) · 143 test cases · 2 s / 256 MB per case

Submitting as anonymous