Restrictions | Topcoder Archive

Problem Statement

You are given the task to construct an array of positive integers. The array A must have exactly n elements. You are given m additional constraints the array has to satisfy. Each constraint is of one of two kinds:

If type[i] = 1: for each j such that l[i] <= j <= r[i], A[j] must be greater than or equal to val[i].
If type[i] = 2: for each j such that l[i] <= j <= r[i], A[j] must be less than or equal to val[i].

Construct and return the array A. If no array matches all the given constraints, return the array {-1}. If multiple arrays match all the given constraints, return the lexicographically smallest of them.

Definition

Class:: Restrictions
Method:: exist
Parameters:: int, int, int[], int[], int[], int[]
Returns:: int[]
Method signature:: int[] exist(int n, int m, int[] type, int[] l, int[] r, int[] val)
(be sure your method is public)

Notes

Given two distinct arrays with the same number of elements, the lexicographically smaller one is the one that has a smaller value at the first index at which they differ.

Constraints

n will be between 1 and 500 inclusive.
m will be between 0 and 150 inclusive.
Each of the arrays type, l, r, and val will have exactly m elements.
Each element of type will be either 1 or 2.
For each valid i the inequalities 0 <= l[i] <= r[i] <= n-1 will hold.
Each element of val will be between 1 and 10^6 inclusive.

Examples

```
6
```
```
5
```
```
{1,1,2,2,2}
```
```
{0,1,2,1,2}
```
```
{5,3,3,4,2}
```
```
{10,18,25,26,16}
```
```
Returns: {-1 }
```
From condition 1 (0-based index) we can deduce that A[2] must be 18 or more. From condition 4 we can deduce that A[2] must be at most 16. This is a contradiction, there is no array that would have both properties at the same time.
```
2
```
```
3
```
```
{1,2,2}
```
```
{0,1,0}
```
```
{1,1,0}
```
```
{3,4,4}
```
```
Returns: {3, 3 }
```
The arrays {3,3}, {3,4}, {4,3}, and {4,4} are the only four arrays that satisfy all the constraints. Among them, {3,3} is lexicographically smallest.

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.