Statistics

Problem Statement for "Removal"

Problem Statement

When items are removed from the middle of a sequence, the positions of all the items further down the sequence change. We are given a sequence and a list of removals that will occur. We want to be able to determine which item ends up in a specified position.

We refer to the positions in our sequence starting with 1. Let the items in our sequence initially be 1, 2, ..., n. Let k be the specified final position, and let remove be a list of Strings that gives the removals in order. Each removal is in the form "lo-hi" where lo and hi are positive integers (with no leading zeros) giving the range of positions whose items are to be removed. Each removal refers to the items by current position (not original position) in the sequence and includes both lo and hi. So if n is 8 and removal is {"3-4","4-5"} the sequence after the first removal is 1, 2, 5, 6, 7, 8 and the final sequence is 1, 2, 5, 8.

Create a class Removal that contains a method finalPos that takes as input n, the original sequence length, k the final position of interest, and remove, a String[] of removals formatted as described above. The method returns the item that ends up in position k, or returns -1 if no item ends up in position k (i.e. if there are fewer than k items left after all the removals).

Definition

Class:
Removal
Method:
finalPos
Parameters:
int, int, String[]
Returns:
int
Method signature:
int finalPos(int n, int k, String[] remove)
(be sure your method is public)

Constraints

  • n will be between 1 and 2,000,000,000 inclusive.
  • k will be between 1 and n inclusive.
  • remove will contain between 1 and 50 elements inclusive.
  • Each element of remove will be formatted as "lo-hi".
  • In each element of remove, neither lo nor hi will have leading zeros.
  • In each element of remove, 0 < lo <= hi <= n.
  • In each element of remove, hi will be less than or equal to the number of items remaining after the preceding removals.

Examples

  1. 8

    3

    {"3-4","4-5"}

    Returns: 5

    As described above, the final sequence will be 1, 2, 5, 8, so item 5 ends up in position 3 of the final sequence.

  2. 100

    13

    {"19-50","19-50","19-19"}

    Returns: 13

    None of these removals affects position 13.

  3. 100

    39

    {"19-50","19-50","19-19"}

    Returns: -1

    The final sequence contains less than 39 items.

  4. 2000000000

    2000000000

    {"1-1"}

    Returns: -1

  5. 2000000000

    1999999999

    {"1-1"}

    Returns: 2000000000

  6. 2000000000

    2000000000

    {"1-1999999003"}

    Returns: -1

  7. 1000000000

    9

    {"20-100","100-200","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100"}

    Returns: 9

  8. 1000000000

    30

    {"20-100","100-200","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100","20-100"}

    Returns: 4100

  9. 1000000000

    30

    {"20-100","100-200","20-100"}

    Returns: 293

  10. 2000000000

    30

    {"30-100","100-200","20-100"}

    Returns: 283

  11. 2000000000

    30

    {"30-100","100-200","31-100"}

    Returns: 101

  12. 1995999999

    1000000000

    {"1000000000-1100000000","5-100000","17-895000000","1000000000-1000000000"}

    Returns: 1995099982

  13. 2000000000

    1000000000

    {"1-1000000000","1000000000-1000000000"}

    Returns: -1

  14. 2000000000

    1000000000

    {"12-1000000010","1000000000-1000000000"}

    Returns: 2000000000

  15. 700

    500

    {"3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3","3-3"}

    Returns: 530

  16. 700

    500

    {"498-500","500-503","600-603"}

    Returns: 507

  17. 100

    39

    { "19-50", "19-50", "19-19" }

    Returns: -1

  18. 200000000

    19999

    { "19-50", "99-500", "19-1999", "19-50", "19-50", "19-1999", "19-50", "19-50", "19-1999", "1799999-19999999" }

    Returns: 26504

  19. 8

    3

    { "3-4", "4-5" }

    Returns: 5

  20. 1999999999

    7000

    { "9-9000", "70-700000" }

    Returns: 715923

  21. 2000000000

    39

    { "19-50", "19-50", "19-19" }

    Returns: 104

  22. 2000000000

    1

    { "1-10" }

    Returns: 11

  23. 2000000000

    3

    { "3-4", "4-5" }

    Returns: 5

  24. 2000000000

    2000000000

    { "1-2000000000" }

    Returns: -1

  25. 2000000000

    1999999995

    { "1999999990-1999999993" }

    Returns: 1999999999

  26. 2000000000

    500000

    { "2-1000000000" }

    Returns: 1000499999

  27. 2000000000

    1

    { "5000-500000" }

    Returns: 1

  28. 1999999999

    100

    { "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2", "1-2" }

    Returns: 182

  29. 2000000000

    1000000000

    { "1-1" }

    Returns: 1000000001

  30. 2000000000

    1

    { "1-1" }

    Returns: 2

  31. 2000000000

    20

    { "1-1000000000", "50-100000", "100-10000000", "200-1000000" }

    Returns: 1000000020

  32. 2000000000

    1000000000

    { "10000000-500000000" }

    Returns: 1490000001

  33. 2000000000

    100000000

    { "1-1000000", "1000000000-1500000000" }

    Returns: 101000000

  34. 8

    3

    { "4-5", "3-4" }

    Returns: 7

  35. 2000000000

    45

    { "8-2000", "34-234245" }

    Returns: 236250

  36. 200000000

    199999

    { "19-50", "99-500", "19-1999", "19-50", "19-50", "19-1999", "19-50", "19-50", "19-1999", "1799999-19999999" }

    Returns: 206504

  37. 2000000000

    1999999

    { "19-50", "99-500", "19-1999", "19-50", "19-50", "19-1999", "19-50", "19-50", "19-1999", "1799999-19999999" }

    Returns: 20206505

  38. 2000000000

    13

    { "19-50", "19-50", "19-19" }

    Returns: 13

  39. 8

    2

    { "3-6", "2-3" }

    Returns: 8

  40. 2000000000

    1

    { "5-2000000000" }

    Returns: 1

  41. 2000000000

    1

    { "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999", "1-39999999" }

    Returns: 1959999952

  42. 2000000000

    200000000

    { "1-2" }

    Returns: 200000002

  43. 1999999999

    7000

    { "8-80000", "1000000-1000001", "90-10000000" }

    Returns: 10086906

  44. 10

    5

    { "6-8", "3-4" }

    Returns: 10

  45. 2000000000

    1000000000

    { "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3", "1-3" }

    Returns: 1000000150

  46. 6

    2

    { "3-4", "2-3" }

    Returns: 6

  47. 10000000

    1000

    { "1000-5000", "2000-30000", "1500-2500", "100-200", "100-1500", "50000-100000" }

    Returns: 35505

  48. 100

    50

    { "51-56", "48-49" }

    Returns: 58

  49. 100

    2

    { "1-2", "3-4", "1-2", "3-4", "1-2", "3-4" }

    Returns: 12

  50. 50

    8

    { "4-5", "4-9", "15-18" }

    Returns: 16

  51. 4

    2

    { "3-3", "2-2" }

    Returns: 4

  52. 100

    30

    { "32-40", "32-40", "1-6" }

    Returns: 54

  53. 5

    2

    { "3-3", "1-1" }

    Returns: 4

  54. 3

    2

    { "1-1" }

    Returns: 3

  55. 20

    2

    { "5-10", "1-4" }

    Returns: 12

  56. 10000

    99

    { "100-100", "80-80", "78-78", "56-112", "12-58", "72-111", "1111-1115", "12-13", "101-110", "111-123", "105-106" }

    Returns: 248

  57. 3

    2

    { "2-3" }

    Returns: -1

  58. 20

    5

    { "6-7", "1-4" }

    Returns: 11

  59. 2000000000

    2000000000

    { "1-2" }

    Returns: -1

  60. 100

    2

    { "3-3", "2-4" }

    Returns: 6

  61. 100

    11

    { "14-15", "2-13" }

    Returns: 25

  62. 1999999999

    2

    { "2-3", "3-4", "4-5", "5-6", "2-3", "3-4", "4-5", "5-6", "7-1929", "393-203093", "29382-199299", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1", "1-1" }

    Returns: 1979

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: