Statistics

Problem Statement for "SuperUserDo"

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.

Definition

Class:
SuperUserDo
Method:
install
Parameters:
int[], int[]
Returns:
int
Method signature:
int install(int[] A, int[] B)
(be sure your method is public)

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.

Examples

  1. {1}

    {10}

    Returns: 10

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

  2. {1,101}

    {10,110}

    Returns: 20

  3. {1}

    {1000}

    Returns: 1000

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

  5. {1,1}

    {1,1}

    Returns: 1

  6. {778,794,336,493,363,28,60,541}

    {887,916,387,650,422,691,764,927}

    Returns: 900

  7. {173,212,430,531,124,68}

    {737,369,568,783,863,136}

    Returns: 796

  8. {23,59,168,12,43,374,785,199,316}

    {803,70,394,457,230,422,920,538,325}

    Returns: 909

  9. {414,92,874,171,282}

    {527,981,957,863,997}

    Returns: 906

  10. {85,328,506,314,125}

    {926,337,847,730,858}

    Returns: 842

  11. {546,368,365,44,88}

    {583,815,435,751,809}

    Returns: 772

  12. {179,404,652,400,61,369}

    {789,585,755,933,677,740}

    Returns: 873

  13. {227,95,571,379,468,98,318}

    {587,540,796,435,602,903,493}

    Returns: 809

  14. {302,281,442,445,441,32,98}

    {757,287,866,690,620,730,118}

    Returns: 835

  15. {482,710,568,354,587,307}

    {676,928,857,498,966,684}

    Returns: 660

  16. {529,733,504,20,369,341,150,619,246}

    {625,872,830,271,709,716,797,724,847}

    Returns: 853

  17. {556,380,229,351,194,35}

    {922,489,765,842,501,765}

    Returns: 888

  18. {915,744,228,366,433,438,229,408,122}

    {988,857,492,860,937,552,276,475,859}

    Returns: 867

  19. {30,236,429,12,530}

    {238,794,819,144,929}

    Returns: 918

  20. {405,614,539,841,129,370}

    {444,764,607,905,819,689}

    Returns: 756

  21. {918,325,184,491,726,591,140}

    {997,744,471,500,773,645,506}

    Returns: 714

  22. {670,83,198,356,349,612,300,344,341}

    {787,543,465,508,805,623,829,747,569}

    Returns: 747

  23. {312,606,662,306,321,445,466}

    {811,802,731,879,737,627,523}

    Returns: 574

  24. {283,259,63,601,37,380,469,72}

    {417,925,638,625,453,900,551,974}

    Returns: 938

  25. {882,895,164,200,900,774}

    {931,934,661,982,997,960}

    Returns: 834

  26. {669,96,467,85,91,377,108,446,180,413,173,10,211,343,207,373,256,600,722,812,668,229,128,659,225,270,82,85,293,673,386,223,43,714,191,525,210,337,156,5,380,274,256,143,580,206,568,505,755,260,203,203,22,843,190,873,499,37,249,304,134,755,568,369,47,789,250,34,364,254,126,153,189,158,437,415,305,28,51,557,698,44,3,404,501,539,152,135,340,128,505,50,286,336,178,239,290,368,293,145}

    {814,191,927,341,685,543,937,757,419,888,349,660,337,588,302,714,322,820,905,940,941,706,151,985,921,423,397,631,973,851,626,300,641,899,299,591,582,820,733,995,770,777,851,861,885,994,622,614,962,327,945,507,785,869,529,909,959,809,754,334,649,891,747,530,501,798,991,304,498,893,687,997,976,730,461,922,461,29,749,903,795,700,40,429,682,648,160,536,693,216,630,965,430,344,901,972,950,989,796,744}

    Returns: 995

  27. {391,341,542,233,43,118,24,82,191,368,235,627,58,169,206,313,101,727,553,530,291,648,52,594,628,313,215,91,413,611,190,356,434,889,339,285,418,261,238,60,218,784,459,638,290,479,315,472,101,439,26,75,158,359,271,418,364,623,174,432,391,293,58,158,492,948,22,538,31,99,82,3,140,405,339,22,863,380,686,537,177,208,745,500,128,237,106,50,245,806,292,615,590,919,806,823,31,94,127,254}

    {830,683,570,827,262,361,762,310,426,997,678,691,525,615,359,387,347,995,917,579,947,971,81,632,858,887,356,513,480,970,275,642,621,988,567,771,857,607,850,206,519,946,874,874,484,608,758,730,460,619,389,234,682,494,700,840,570,795,848,463,683,792,116,522,575,952,232,741,55,326,517,517,232,797,581,219,971,813,978,905,484,760,858,912,951,561,819,564,712,935,376,956,769,994,883,983,718,575,594,487}

    Returns: 995

  28. {75,714,180,763,89,711,18,236,138,154,329,292,19,218,56,91,131,572,634,74,605,251,504,7,196,121,227,678,597,561,37,519,212,197,322,271,173,41,73,399,64,31,574,60,48,83,205,444,487,279,160,263,42,325,123,155,458,366,172,219,702,654,908,729,721,85,335,377,716,53,190,11,17,110,1,54,82,339,68,148,232,123,282,180,255,132,814,182,82,434,182,416,297,405,552,33,135,416,58,596}

    {544,815,378,776,920,733,295,347,692,944,574,926,711,837,964,859,905,662,686,790,852,806,869,486,640,950,968,764,982,866,956,771,343,533,380,985,428,235,284,831,348,951,715,523,925,436,233,955,899,641,263,684,849,724,273,336,822,748,777,270,704,934,960,807,798,309,699,992,899,172,560,507,225,540,379,110,115,990,427,224,788,533,876,851,591,351,858,495,604,721,983,488,826,723,893,298,182,507,709,1000}

    Returns: 1000

  29. {298,484,155,310,383,22,564,212,87,286,584,315,117,526,529,491,137,619,338,583,311,226,571,438,9,351,98,127,72,150,529,399,611,394,891,200,88,100,567,18,642,299,185,777,267,529,309,198,556,446,1,284,128,383,335,335,160,958,355,763,542,851,483,218,155,16,365,264,173,38,829,281,857,342,353,512,70,84,113,301,639,365,33,105,142,413,637,171,761,650,315,327,40,536,153,394,110,632,265,296}

    {963,777,978,588,933,267,861,683,686,931,991,477,821,893,840,526,361,644,929,622,956,889,816,854,723,784,658,828,270,652,911,640,889,578,977,553,932,778,658,953,736,369,196,806,429,955,594,279,673,775,326,998,413,422,694,440,422,986,762,973,717,853,663,400,174,507,852,791,492,538,860,872,988,591,971,666,518,362,352,507,668,490,155,876,680,539,970,957,845,815,466,887,184,970,622,791,290,674,736,549}

    Returns: 998

  30. {1 }

    {10 }

    Returns: 10

  31. {1, 1 }

    {1, 1 }

    Returns: 1

  32. {1, 3, 1 }

    {2, 4, 2 }

    Returns: 4

  33. {1, 1, 1, 1, 1000 }

    {1, 1, 1, 1, 1000 }

    Returns: 2

  34. {50, 60, 1 }

    {60, 70, 100 }

    Returns: 100

  35. {1, 20 }

    {30, 25 }

    Returns: 30

  36. {3, 1 }

    {4, 5 }

    Returns: 5

  37. {100, 1 }

    {101, 2 }

    Returns: 4

  38. {1, 1 }

    {3, 2 }

    Returns: 3

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.
This problem was used for: