Statistics

Problem Statement for "ThreePartSplit"

Problem Statement

Ternary search is one of many algorithms in which we need to split a range of integers into three equal (or almost equal) parts. That will be your task in this problem.

A half-open interval [x,y) is the set of integers that are greater than or equal to x and strictly less than y. Hence, [x,y) = { x, x+1, x+2, ..., y-2, y-1 }. For example, [3,7) = { 3, 4, 5, 6 }.

You are given two ints a and d. These define the half-open interval [a,d). This interval contains n = d-a numbers. Your task is to split this interval into three parts: [a,b), [b,c), and [c,d). Each of these intervals must contain at least (n div 3) elements.

Return {b, c}. That is, return a int[] with two elements, the first of which is b and the second is c. If there are multiple valid solutions, you may return any one of them.

Definition

Class:
ThreePartSplit
Method:
split
Parameters:
int, int
Returns:
int[]
Method signature:
int[] split(int a, int d)
(be sure your method is public)

Notes

  • The formula "n div 3" means "n divided by 3, rounded down". For example, 14 div 3 = 4.

Constraints

  • a will be between 0 and 10^8, inclusive.
  • d will be between a+3 and 10^8, inclusive.

Examples

  1. 0

    6

    Returns: {2, 4 }

    We are given the range [0,6) = {0,1,2,3,4,5}. We need to split it into three parts, each containing at least (6 div 3) = 2 elements. Clearly, the only valid solution is to split it into {0,1}, {2,3}, and {4,5}, that is, intervals [0,2), [2,4), and [4,6). Thus, we must have b=2 and c=4, and we must return {2,4}.

  2. 10

    14

    Returns: {11, 12 }

    When splitting the interval [10,14) into three roughly equal parts, we have multiple valid options: Split it into [10,11), [11,12), and [12,14). Split it into [10,11), [11,13), and [13,14). Split it into [10,12), [12,13), and [13,14). Hence, there are three valid return values: {11, 12}, {11, 13}, and {12, 13}. Your solution may return any one of these three.

  3. 127

    345

    Returns: {199, 271 }

  4. 0

    100000000

    Returns: {33333333, 66666666 }

  5. 57738620

    74308313

    Returns: {63261851, 68785082 }

  6. 60890672

    76610214

    Returns: {66130519, 71370366 }

  7. 52669103

    82619242

    Returns: {62652482, 72635861 }

  8. 5490675

    56174495

    Returns: {22385281, 39279887 }

  9. 35407527

    64632919

    Returns: {45149324, 54891121 }

  10. 1226180

    42356098

    Returns: {14936152, 28646124 }

  11. 30876379

    31909169

    Returns: {31220642, 31564905 }

  12. 48195185

    59353897

    Returns: {51914755, 55634325 }

  13. 47439601

    80661580

    Returns: {58513594, 69587587 }

  14. 45890888

    74865365

    Returns: {55549047, 65207206 }

  15. 32026925

    97864709

    Returns: {53972853, 75918781 }

  16. 4735057

    16844269

    Returns: {8771461, 12807865 }

  17. 48699376

    77625098

    Returns: {58341283, 67983190 }

  18. 51483060

    68223645

    Returns: {57063255, 62643450 }

  19. 13032361

    87081599

    Returns: {37715440, 62398519 }

  20. 30461759

    93846145

    Returns: {51589887, 72718015 }

  21. 63220606

    99882012

    Returns: {75441074, 87661542 }

  22. 14783505

    55923193

    Returns: {28496734, 42209963 }

  23. 32075749

    74526545

    Returns: {46226014, 60376279 }

  24. 35109973

    47908112

    Returns: {39376019, 43642065 }

  25. 71495688

    75884514

    Returns: {72958630, 74421572 }

  26. 5383446

    64954137

    Returns: {25240343, 45097240 }

  27. 41903666

    75529436

    Returns: {53112256, 64320846 }

  28. 29653664

    81382227

    Returns: {46896518, 64139372 }

  29. 15292186

    84209166

    Returns: {38264512, 61236838 }

  30. 27794650

    50984921

    Returns: {35524740, 43254830 }

  31. 20025590

    59577419

    Returns: {33209533, 46393476 }

  32. 2038795

    22856691

    Returns: {8978093, 15917391 }

  33. 73416107

    84175572

    Returns: {77002595, 80589083 }

  34. 35668351

    68616779

    Returns: {46651160, 57633969 }

  35. 69386059

    90477545

    Returns: {76416554, 83447049 }

  36. 63325269

    95051093

    Returns: {73900543, 84475817 }

  37. 2984114

    77432999

    Returns: {27800409, 52616704 }

  38. 46434549

    57933395

    Returns: {50267497, 54100445 }

  39. 23713243

    63054542

    Returns: {36827009, 49940775 }

  40. 13209403

    18342176

    Returns: {14920327, 16631251 }

  41. 46178284

    70786583

    Returns: {54381050, 62583816 }

  42. 35818037

    59582023

    Returns: {43739365, 51660693 }

  43. 60652

    87593894

    Returns: {29238399, 58416146 }

  44. 16425002

    55575540

    Returns: {29475181, 42525360 }

  45. 9014669

    49559704

    Returns: {22529680, 36044691 }

  46. 2781207

    35466737

    Returns: {13676383, 24571559 }

  47. 5597578

    18849325

    Returns: {10014827, 14432076 }

  48. 24317463

    99206390

    Returns: {49280438, 74243413 }

  49. 26997684

    66396815

    Returns: {40130727, 53263770 }

  50. 75645855

    76146682

    Returns: {75812797, 75979739 }

  51. 1340478

    93286024

    Returns: {31988993, 62637508 }

  52. 100

    105

    Returns: {101, 104 }

    As the original interval contains d-a = 5 elements, the requirement is that each of the three new intervals must contain at least one element. The return value of our solution corresponds to splitting the original interval into intervals of length 1, 3, and 1.

  53. 100

    106

    Returns: {102, 104 }

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: