Connection Status:
Competition Arena > SRMDiv0Easy

SRMDiv0Easy

SRM 694 · 2016-06-25 · by IH19980412

SRM 694 · 2016-06-25 · by IH19980412 · Graph Theory
Class Name: SRMDiv0Easy
Return Type: int
Method Name: get
Arg Types: (int, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

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

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

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

2)
3
{0,1,0,0,2}
{2,2,1,0,2}
{1,3,1,4,2}
{11,13,19,15,17}
Returns: 41
3)
12
{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
4)
200
{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

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

Coding Area

Language: C++17 · define a public class SRMDiv0Easy with a public method int get(int N, vector<int> L, vector<int> R, vector<int> X, vector<int> Y) · 167 test cases · 2 s / 256 MB per case

Submitting as anonymous