Statistics

Problem Statement for "BoxFilling"

Problem Statement

We have a box that consists of (sizeX x sizeY x sizeZ) = N unit cubes. These cubes have coordinates ranging from (1,1,1) to (sizeX,sizeY,sizeZ).

We want to number the unit cubes, using integers from 1 to N. We will do this algorithmically.

We will call a box "1-dimensional (1D)" if at least two of its dimensions are 1, "2-dimensional (2D)" if exactly one of its dimensions is 1, and "3-dimensional (3D)" otherwise.

The algorithm used to number a 1-dimensional box is simple: order the cubes according to the sums of their coordinates (in ascending order), and number them in this order.

To number a 2-dimensional box, we follow this algorithm:

  • If X size is greater than 1, consider all cubes with both Y and Z coordinates minimal, number them as a 1D box, and throw them away.
  • If we still have a 2D box, if Y size is greater than 1, consider all cubes with both X and Z coordinates minimal, number them as a 1D box, and throw them away.
  • If we still have a 2D box, if Z size is greater than 1, consider all cubes with both X and Y coordinates minimal, number them as a 1D box, and throw them away.
  • Recursively number the rest of the box.

For example, a 4x5x1 box filled using this algorithm looks as follows: 

z=1
   x:1  2  3  4
 y:+--+--+--+--+
  1| 1| 2| 3| 4|
   +--+--+--+--+
  2| 5| 9|10|11|
   +--+--+--+--+
  3| 6|12|15|16|
   +--+--+--+--+
  4| 7|13|17|19|
   +--+--+--+--+
  5| 8|14|18|20|
   +--+--+--+--+

To number a 3-dimensional box, we follow this algorithm:

  • Consider all cubes with the Z coordinate minimal, number them as a 2D box, and throw them away.
  • If we still have a 3D box, consider all cubes with the Y coordinate minimal, number them as a 2D box, and throw them away.
  • If we still have a 3D box, consider all cubes with the X coordinate minimal, number them as a 2D box, and throw them away.
  • Recursively number the rest of the box.

For example, a 4x3x3 box filled using this algorithm looks as follows: 

z=1
   x:1  2  3  4
 y:+--+--+--+--+
  1| 1| 2| 3| 4|
   +--+--+--+--+
  2| 5| 7| 8| 9|
   +--+--+--+--+
  3| 6|10|11|12|
   +--+--+--+--+

z=2
   x:1  2  3  4
 y:+--+--+--+--+
  1|13|14|15|16|
   +--+--+--+--+
  2|21|25|26|27|
   +--+--+--+--+
  3|22|28|29|30|
   +--+--+--+--+

z=3
   x:1  2  3  4
 y:+--+--+--+--+
  1|17|18|19|20|
   +--+--+--+--+
  2|23|31|32|33|
   +--+--+--+--+
  3|24|34|35|36|
   +--+--+--+--+

You will be given the box dimensions sizeX, sizeY, and sizeZ, and the coordinates of a single cube (cubeX,cubeY,cubeZ). Write a method that will compute the number assigned to the cube at the given coordinates, when using the algorithm described above.

Definition

Class:
BoxFilling
Method:
getNumber
Parameters:
int, int, int, int, int, int
Returns:
long
Method signature:
long getNumber(int sizeX, int sizeY, int sizeZ, int cubeX, int cubeY, int cubeZ)
(be sure your method is public)

Notes

  • Note that the box described by sizeX, sizeY, and sizeZ is not necessarily a 3D box.

Constraints

  • sizeX, sizeY and sizeZ will be between 1 and 109, inclusive.
  • The volume of the box will not exceed 1018.
  • cubeX will be between 1 and sizeX, inclusive.
  • cubeY will be between 1 and sizeY, inclusive.
  • cubeZ will be between 1 and sizeZ, inclusive.

Examples

  1. 4

    5

    1

    2

    4

    1

    Returns: 13

    This is the box from the first example in the problem statement.

  2. 4

    3

    3

    2

    2

    2

    Returns: 25

    This is the box from the second example in the problem statement.

  3. 4

    3

    3

    4

    2

    1

    Returns: 9

    Same box, different cube coordinates.

  4. 2

    2

    2

    1

    1

    1

    Returns: 1

  5. 43633

    35453

    34533

    2344

    32442

    34221

    Returns: 9416237809215

  6. 1000000

    1000000

    1000000

    999841

    999232

    999932

    Returns: 999999999546400154

  7. 999934

    999924

    999941

    998724

    992241

    325462

    Returns: 692973738900507323

  8. 1000000000

    1000000000

    1

    998912415

    999134151

    1

    Returns: 999998817158001926

  9. 349899

    20683

    89110

    105181

    20683

    26132

    Returns: 644865205656070

  10. 3

    1

    10

    3

    1

    2

    Returns: 14

  11. 1

    1

    100000000

    1

    1

    47000000

    Returns: 47000000

    This is a very tall 1D box.

  12. 5

    2

    6

    4

    2

    6

    Returns: 59

  13. 4

    2

    4

    3

    2

    3

    Returns: 28

  14. 1000000000

    1

    1

    1000000000

    1

    1

    Returns: 1000000000

  15. 1

    1000000000

    1

    1

    1000000000

    1

    Returns: 1000000000

  16. 1

    1

    1000000000

    1

    1

    1000000000

    Returns: 1000000000

  17. 1000000000

    1

    1

    47

    1

    1

    Returns: 47

  18. 1

    1000000000

    1

    1

    47

    1

    Returns: 47

  19. 1

    1

    1000000000

    1

    1

    47

    Returns: 47

  20. 3

    1

    2

    2

    1

    2

    Returns: 5

  21. 2

    1

    48

    1

    1

    1

    Returns: 1

  22. 1

    3

    491135

    1

    1

    19291

    Returns: 19293

  23. 2

    1

    994702553

    1

    1

    975014645

    Returns: 975014646

  24. 1

    3

    988703112

    1

    2

    635723059

    Returns: 1624426173

  25. 3

    999961341

    1

    1

    31218745

    1

    Returns: 31218747

  26. 1

    52

    3

    1

    49

    2

    Returns: 102

  27. 48

    50

    1

    2

    47

    1

    Returns: 189

  28. 1

    51

    508454

    1

    2

    267980

    Returns: 776532

  29. 1

    52

    992660308

    1

    51

    108001006

    Returns: 49741016457

  30. 1

    52

    984353891

    1

    42

    957621003

    Returns: 41316130954

  31. 1

    47

    994343975

    1

    43

    945117277

    Returns: 42707564399

  32. 516111

    2

    1

    118065

    2

    1

    Returns: 634176

  33. 523993

    52

    1

    236347

    5

    1

    Returns: 2332507

  34. 1

    513606

    494935

    1

    207959

    466429

    Returns: 166488203632

  35. 1

    525068

    996710029

    1

    493158

    691216624

    Returns: 491550955659957

  36. 511302

    1

    985560256

    487280

    1

    894429690

    Returns: 480255415853274

  37. 1

    484164

    981558429

    1

    249724

    53465395

    Returns: 245176314325122

  38. 1

    989834408

    3

    1

    791698928

    2

    Returns: 1781533337

  39. 1

    984872327

    48

    1

    958865932

    48

    Returns: 47247865301

  40. 980051520

    528867

    1

    924038514

    413562

    1

    Returns: 405359696352339

  41. 1

    993363290

    989959638

    1

    975881011

    200747797

    Returns: 357848029728542287

  42. 1

    997142563

    988002237

    1

    938064725

    80639748

    Returns: 153578806491566569

  43. 982597407

    1

    991537759

    968352925

    1

    919627413

    Returns: 969754236793678161

  44. 982756927

    2

    1

    155324915

    1

    1

    Returns: 155324915

  45. 1

    987346472

    50

    1

    84751548

    3

    Returns: 2059444586

  46. 1

    984316375

    473030

    1

    902996866

    472012

    Returns: 464609539984189

  47. 1

    990794289

    999035968

    1

    20637372

    76065819

    Returns: 40638965184528071

  48. 989366054

    1

    987230912

    795273476

    1

    906260736

    Returns: 939475238091781064

  49. 992255658

    1

    992114542

    947471997

    1

    23985260

    Returns: 47020341473071457

  50. 1

    995235059

    2

    1

    492067918

    1

    Returns: 492067918

  51. 1

    996987719

    53

    1

    978792345

    50

    Returns: 49831190723

  52. 981385614

    506045

    1

    930238065

    487962

    1

    Returns: 478887659629882

  53. 988338034

    1

    982308506

    933110182

    1

    740759356

    Returns: 911050438075716502

  54. 989376259

    1

    982278586

    938190191

    1

    949570910

    Returns: 969586401095301238

  55. 992035549

    1

    995354274

    95394872

    1

    53771614

    Returns: 103973770119495989

  56. 3

    2

    1000000000

    1

    1

    34248627

    Returns: 34248634

  57. 1000000000

    7

    52

    473442063

    1

    46

    Returns: 51473442327

  58. 2

    529095

    1000000000

    2

    46211

    919290065

    Returns: 575328233842589

  59. 1000000000

    7

    1098597

    58657200

    1

    1078639

    Returns: 1078665586094446

  60. 145586463

    7

    981252921

    133291431

    7

    92734981

    Returns: 953040502835740969

  61. 50

    1000000000

    4

    41

    69755937

    3

    Returns: 142069756402

  62. 51

    52

    1000000000

    1

    50

    25032173

    Returns: 99025034823

  63. 52

    506297

    1000000000

    47

    503085

    382697714

    Returns: 23792983117575484

  64. 1000000000

    51

    800604

    35939812

    51

    520509

    Returns: 40550853827347977

  65. 50

    20298146

    985311652

    28

    2023336

    913441299

    Returns: 542031205731949383

  66. 1000000000

    528563

    7

    6811973

    509749

    2

    Returns: 1038325599853655

  67. 1000000000

    474349

    53

    911783887

    327329

    5

    Returns: 2224965126620687

  68. 502343

    470936

    4227053

    494636

    465248

    1934165

    Returns: 999206081641057904

  69. 529050

    1732241

    1091176

    22410

    1685226

    997946

    Returns: 74160940979926265

  70. 2104

    480882

    988348065

    1960

    433727

    37701101

    Returns: 931778937096482326

  71. 1000000000

    890109

    3

    10613203

    825064

    2

    Returns: 1715226677726146

  72. 934327

    51

    1000000000

    180310

    50

    37949909

    Returns: 45962517042223096

  73. 2438694

    808555

    507146

    40634

    635679

    504762

    Returns: 140908252248549928

  74. 971636

    1195300

    861032

    45571

    1184342

    844559

    Returns: 131758831140063191

  75. 948236

    1068

    987066211

    25400

    1002

    33612656

    Returns: 936998055497553823

  76. 984247619

    203200897

    5

    966737801

    26297451

    1

    Returns: 30535313041022051

  77. 20303901

    985032383

    50

    1167918

    677870461

    47

    Returns: 921172924105320728

  78. 992707497

    518381

    1943

    919968436

    45111

    1830

    Returns: 941454769320453932

  79. 881

    994806305

    1140818

    797

    901733841

    942290

    Returns: 904379039274411666

  80. 1000000000

    5

    5

    970636429

    5

    1

    Returns: 4970636429

  81. 3

    1000000000

    52

    1

    655495368

    49

    Returns: 50655495614

  82. 2

    505103

    1000000000

    1

    88480

    672655341

    Returns: 88517535963483

  83. 1000000000

    5

    1052983

    847228024

    5

    1042692

    Returns: 5254634577550814

  84. 5

    995526251

    200898770

    1

    994280079

    196415205

    Returns: 196417137791622623

  85. 52

    1000000000

    6

    50

    909726292

    6

    Returns: 309909726392

  86. 52

    47

    1000000000

    15

    3

    297893530

    Returns: 206297900722

  87. 51

    1000000000

    484176

    4

    81830858

    241728

    Returns: 1694501779082890

  88. 1000000000

    50

    961090

    106059480

    6

    919601

    Returns: 5725352470740871

  89. 47

    21362770

    995966135

    47

    10120208

    970970146

    Returns: 988916553098574687

  90. 499497

    1000000000

    6

    19835

    959372261

    6

    Returns: 2517329473468031

  91. 1000000000

    514620

    47

    353436874

    44262

    14

    Returns: 6734771392718715

  92. 494462

    521072

    3881229

    77856

    35031

    1508219

    Returns: 141131505038546038

  93. 2034521

    496519

    989924

    1970522

    19459

    75307

    Returns: 67084200183850705

  94. 1949

    520233

    985933599

    95

    152680

    97243500

    Returns: 48538359904700369

  95. 1000000000

    1065387

    6

    52456683

    16448

    1

    Returns: 16464304356416

  96. 899646

    1000000000

    48

    826296

    80631492

    48

    Returns: 43109717689443092

  97. 2377774

    859940

    489059

    2316345

    21370

    460221

    Returns: 75841504768171871

  98. 1217007

    836318

    982506

    1200332

    14107

    150712

    Returns: 42214664507084574

  99. 973008

    1033

    994519124

    93091

    562

    27265689

    Returns: 543221412711672163

  100. 999031444

    2

    500484747

    986402040

    2

    435889745

    Returns: 963623859675761530

  101. 998469893

    48

    20865259

    36565437

    4

    19488971

    Returns: 81986149509669408

  102. 985421146

    1970

    515102

    939856849

    1917

    5720

    Returns: 972652855792247297

  103. 975

    999343671

    1025954

    30

    973962108

    19367

    Returns: 29780872697553672

  104. 6

    2

    8

    5

    1

    4

    Returns: 37

  105. 2

    2

    5

    1

    2

    3

    Returns: 15

  106. 2

    3

    4

    2

    3

    3

    Returns: 23

  107. 2

    3

    3

    1

    2

    3

    Returns: 13

  108. 2

    2

    3

    2

    2

    2

    Returns: 10

  109. 999999

    999123

    999000

    998000

    998000

    998005

    Returns: 998122876628125004

  110. 999999

    99998

    99995

    15678

    34567

    56785

    Returns: 3001147856047072

  111. 999999999

    999999999

    1

    999999999

    999999999

    1

    Returns: 999999998000000001

  112. 1000000000

    1000000000

    1

    1000000000

    1000000000

    1

    Returns: 1000000000000000000

  113. 1

    1

    1

    1

    1

    1

    Returns: 1

  114. 10000

    100000

    1000000

    9999

    99999

    999999

    Returns: 999910898019997

  115. 1000000

    999999

    1000001

    465737

    756374

    987654

    Returns: 847501537734964594

  116. 1000000000

    30000000

    30

    30000000

    20000000

    27

    Returns: 800200079359997972

  117. 100000000

    100000000

    1

    100000000

    100000000

    1

    Returns: 10000000000000000

  118. 1000000000

    1000000000

    1

    500000000

    500000000

    1

    Returns: 749999999000000000

  119. 1000000

    1000000

    1000000

    999999

    999999

    999999

    Returns: 999999999999999993

  120. 1000000000

    1

    987898788

    987654321

    1

    794086235

    Returns: 947990115301349723

  121. 2

    3

    4

    2

    2

    2

    Returns: 19

  122. 3

    2

    10

    3

    1

    2

    Returns: 9

  123. 200000000

    20

    250000000

    199999998

    17

    249999997

    Returns: 850000022099999179

  124. 1

    2

    2

    1

    2

    2

    Returns: 4

  125. 99999999

    2

    99999999

    2

    2

    2

    Returns: 9999999900000002

  126. 9999999

    6

    99999999

    3

    1

    2

    Returns: 59999997

  127. 1000000

    1000000

    1000000

    378248

    5625

    253465

    Returns: 16778710005253953

  128. 8

    8

    8

    8

    1

    8

    Returns: 120

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: