Connection Status:
Competition Arena > SuperUserDo

SuperUserDo

SRM 705 Sponsored By Blizzard · 2016-12-22 · by ltaravilse

SRM 705 Sponsored By Blizzard · 2016-12-22 · by ltaravilse · Simple Search, Iteration
Class Name: SuperUserDo
Return Type: int
Method Name: install
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Fox Ciel just used the command "sudo" (super-user do) to gain administrative privileges in the UNIX-based operating system on her computer. She now wants to install several new programs. Each program has some dependencies: in addition to the program, the package manager has to install some libraries used by the program.
The package repository contains exactly 1000 libraries. For simplicity, we will number them from 1 to 1000, inclusive.
You are given the information about the dependencies of the programs Fox Ciel wants to install. More precisely, you are given the int[]s A and B, both containing the same number of elements. For each valid i, one of the programs needs all libraries that have numbers between A[i] and B[i], inclusive. Note that the programs may have overlapping dependences: multiple programs may require the same library to be installed. Of course, in such cases it is sufficient to install such a library once.
Calculate and return the total number of libraries that need to be installed.

Constraints

  • A will contain between 1 and 100 elements inclusive.
  • B will contain the same number of elements as A.
  • Each element of A will be between 1 and 1000 inclusive.
  • The i-th element of B will be between A[i] and 1000 inclusive.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{1}
{10}
Returns: 10

Only libraries 1 to 10 must be installed, so the answer is 10.

1)
{1,101}
{10,110}
Returns: 20
2)
{1}
{1000}
Returns: 1000
3)
{1,2,3,4,5}
{6,7,8,9,10}
Returns: 10

In this test case the dependencies have non-empty intersections. One program needs libraries from 1 to 6, another program needs libraries from 2 to 7, and so on. In order to satisfy all dependencies, the package manager will install libraries numbered from 1 to 10, inclusive. Hence, the total number of installed libraries is 10.

4)
{1,1}
{1,1}
Returns: 1

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

Coding Area

Language: C++17 · define a public class SuperUserDo with a public method int install(vector<int> A, vector<int> B) · 38 test cases · 2 s / 256 MB per case

Submitting as anonymous