SRMDiv0Easy | Topcoder Archive

Problem Statement

The year is 2147. Taro is preparing a problem set for the upcoming SRM, and he still needs an easy problem for division 0. For inspiration, he has been looking at problems from some very old SRMs. Here is a problem he just found:

You have a sequence A of length N. Initially, all elements of A are zeros. You are given a sequence of Q instructions to process. Instruction i has the following form: "Add V[i] to each of the elements with indices between L[i] and R[i], inclusive." Apply all the instructions in the given order, and return the resulting sequence.

"Too easy." concluded Taro. "Now even babies can solve such problems. I need to make it harder." And indeed, he came up with a way to modify the above problem. The new problem is described below. Solve it!

In the new problem, you are given the int N and you are given the int[]s L and R (each with Q elements). You are not given the values V[i]. Instead, you are given the following additional information:

You are given two new int[]s X and Y, each with Q elements. For each i, the value V[i] must be between X[i] and Y[i], inclusive.
After all the instructions have been applied, all elements of A must have the same value. (Let's denote that value Z.)

Return the largest possible value Z that can be achieved by an appropriate choice of the values V[i]. If there is no value Z that can be achieved, return -1 instead. (In other words, the return value -1 means that for each valid choice of values V[i] there will be at least two different values in the final sequence A.)

Definition

Class:: SRMDiv0Easy
Method:: get
Parameters:: int, int[], int[], int[], int[]
Returns:: int
Method signature:: int get(int N, int[] L, int[] R, int[] X, int[] Y)
(be sure your method is public)

Constraints

N will be between 2 and 200, inclusive.
Q will be between 0 and 200, inclusive.
L,R,X,Y will each have exactly Q elements.
Each element of L,R will each be between 0 and N-1, inclusive.
For each i between 0 and Q-1, L[i] is equal to or less than R[i].
Each element of X,Y will each be between 0 and 1000, inclusive.
For each i between 0 and Q-1, X[i] is equal to or less than Y[i].

Examples

```
2
```
```
{0,1}
```
```
{0,1}
```
```
{1,2}
```
```
{2,3}
```
```
Returns: 2
```
If V[0] = 2, V[1] = 2, resulting sequence will be {2,2} and it meets the condition. So, the answer is 2.
```
2
```
```
{0,1}
```
```
{0,1}
```
```
{1,3}
```
```
{2,4}
```
```
Returns: -1
```
In this case, we can't achive the state that all the numbers of A are equal.

{0,1,0,0,2}

{2,2,1,0,2}

{1,3,1,4,2}

{11,13,19,15,17}

Returns: 41

{0,0,1,4,9,7,0}

{6,11,11,4,10,11,0}

{1,73,334,1,1,5,362}

{546,342,645,249,999,535,458}

Returns: -1

{0,49,0,97,0,65,0,55,0,24,0,86,0,139,0,34,0,11,0,62,0,172,0,59,0,97,0,47,0,156,0,24,0,103,0,184,0,130,0,154,0,26,0,121,0,72,0,183,0,5}

{48,199,96,199,64,199,54,199,23,199,85,199,138,199,33,199,10,199,61,199,171,199,58,199,96,199,46,199,155,199,23,199,102,199,183,199,129,199,153,199,25,199,120,199,71,199,182,199,4,199}

{1,1,1,1,2,1,2,2,2,2,1,1,1,1,2,1,1,1,1,1,2,2,2,1,2,1,1,2,2,1,1,1,2,2,1,1,2,1,1,1,1,1,2,2,2,2,2,2,2,1}

{964,962,952,993,983,973,971,954,978,980,958,999,991,978,977,991,971,976,977,998,968,992,951,955,987,981,986,958,968,966,992,957,975,995,958,995,983,985,956,974,966,986,985,999,959,989,980,998,971,973}

Returns: 24202

```
5
```
```
{}
```
```
{}
```
```
{}
```
```
{}
```
```
Returns: 0
```

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.