Statistics

Problem Statement for "ChocolateBreaking"

Problem Statement

You have a rectangular chocolate that consists of rows times cols unit squares. The chocolate is still in its wrapper. Without removing the wrapper, you want to break the chocolate into exactly pieces parts by breaking it fully between some rows and between some columns.

If your goal cannot be achieved, return -1. If it can be achieved, among all valid ways to break the chocolate find the one that minimizes the difference between the area of the largest and the area of the smallest piece. Return that difference.

Definition

Class:
ChocolateBreaking
Method:
minDiff
Parameters:
int, int, long
Returns:
long
Method signature:
long minDiff(int rows, int cols, long pieces)
(be sure your method is public)

Constraints

  • rows will be between 1 and 10^9, inclusive.
  • cols will be between 1 and 10^9, inclusive.
  • pieces will be between 1 and 10^14, inclusive.

Examples

  1. 20

    30

    6

    Returns: 0

    You want to break a 20x30 chocolate into 6 pieces. There are two perfect ways to do so: either you break it into six 10x10 squares or into six 20x5 rectangles. In either case, the difference between the biggest and the smallest piece is zero.

  2. 3

    3

    5

    Returns: -1

    Given the restrictions in the problem statement, it is impossible to break a 3x3 chocolate into exactly five pieces.

  3. 5

    5

    4

    Returns: 5

    There are two ways to break a 5x5 chocolate into four pieces: One is to break it between any three columns (or any three rows), producing a single 2x5 piece and three 1x5 pieces. The other is to break it on either side of the middle row and on either side of the middle column of unit squares. This produces a 2x2 piece, two 2x3 pieces, and a 3x3 piece. In either case, the difference between the biggest and the smallest piece is 5. (In the first case it is 10-5, in the second case it is 9-4.)

  4. 3

    10

    4

    Returns: 3

  5. 4

    7

    1

    Returns: 0

    You don't need to break anything if you only need one piece. The difference between the largest and the smallest piece is obviously zero.

  6. 1000000

    1000000

    999914001833

    Returns: 3

  7. 10000000

    10000000

    99999080001827

    Returns: 3

  8. 4

    6

    15

    Returns: 3

    This is the smallest non-trivial test (i.e., with a solution that is not -1) that fails if you don't check that each piece must have both dimensions positive.

  9. 10000000

    10000000

    99995271001363

    Returns: -1

  10. 987654321

    987654321

    99995271001363

    Returns: 997

  11. 4718803

    255999072

    104554406420

    Returns: 953

  12. 128654

    56300

    398384431

    Returns: -1

  13. 6

    2507971

    14823990

    Returns: 1

  14. 94494

    33064496

    85092

    Returns: 12190

  15. 276590639

    1193

    24

    Returns: 1193

  16. 8945303

    7815141

    3972

    Returns: 678287

  17. 81

    247443

    1

    Returns: 0

  18. 76123533

    8736258

    71002

    Returns: 207138

  19. 348

    133

    51

    Returns: 65

  20. 12

    42677

    6

    Returns: 0

  21. 19

    103

    13

    Returns: 19

  22. 93141

    371828

    858471555

    Returns: -1

  23. 504901299

    1163439

    1003

    Returns: 1163439

  24. 1

    257000819

    102

    Returns: 1

  25. 171

    224588210

    3977126227

    Returns: 9

  26. 50010

    1096951

    75198252

    Returns: -1

  27. 31513

    3677

    1

    Returns: 0

  28. 33531870

    58

    81102786

    Returns: 12

  29. 55525680

    187003764

    1881390

    Returns: 148737

  30. 2536895

    129166

    4443723

    Returns: 14357

  31. 39011912

    355083

    3183908773

    Returns: -1

  32. 65368319

    1

    2366812

    Returns: 1

  33. 1240

    44775

    41

    Returns: 1240

  34. 40

    106686299

    5

    Returns: 0

  35. 2478386

    6770

    14

    Returns: 3385

  36. 106

    150058730

    2883476

    Returns: 53

  37. 4312

    12

    4

    Returns: 0

  38. 110712

    7761

    81979605

    Returns: 6

  39. 246507517

    8369982

    71486

    Returns: 348796

  40. 237379

    8

    21

    Returns: 8

  41. 11918

    1

    3

    Returns: 1

  42. 4

    32347735

    4831

    Returns: 4

  43. 234731

    15

    112

    Returns: 15

  44. 22696922

    277763

    2

    Returns: 0

  45. 370

    32

    896

    Returns: 1

  46. 84877

    17

    160

    Returns: 17

  47. 1322

    265041149

    3899995326

    Returns: 75

  48. 3669764

    58818919

    6

    Returns: 1834882

  49. 990

    40355407

    1

    Returns: 0

  50. 5536424

    784

    108890

    Returns: 392

  51. 82079131

    11085

    806935087318

    Returns: -1

  52. 902939807

    165

    23801956402

    Returns: 6

  53. 6

    22546479

    37156074

    Returns: 1

  54. 81

    29267708

    393708

    Returns: 27

  55. 443027738

    155889

    371196

    Returns: 17321

  56. 6

    28

    117

    Returns: -1

  57. 755318

    11853

    854970

    Returns: 422

  58. 10380821

    52

    921689

    Returns: 52

  59. 73317

    24

    429136

    Returns: 3

  60. 201003968

    35488

    3

    Returns: 35488

  61. 2691

    17

    64707523

    Returns: -1

  62. 311397

    3281090

    32632344444924

    Returns: -1

  63. 24

    850331850

    1519

    Returns: 24

  64. 3533

    26508

    5

    Returns: 3533

  65. 3

    1

    240070

    Returns: -1

  66. 593677405

    368933862

    35776

    Returns: 4999183

  67. 63898124

    1512

    214566

    Returns: 252

  68. 8135

    109708

    17067506749

    Returns: -1

  69. 5

    62121

    1501688

    Returns: -1

  70. 1245881

    10729417

    284148

    Returns: 13808

  71. 60

    156928

    729134

    Returns: 8

  72. 181000599

    258713

    7770

    Returns: 36959

  73. 1

    1892871

    3530861845262

    Returns: -1

  74. 17808

    501469

    2772

    Returns: 212

  75. 289292

    899

    24299896

    Returns: 6

  76. 55050855

    171947608

    59

    Returns: 55050855

  77. 48213

    1

    20692845945

    Returns: -1

  78. 17

    44211

    929227272611

    Returns: -1

  79. 63

    102315

    8977

    Returns: 63

  80. 19967

    3673

    183925

    Returns: 39

  81. 1369931

    257446

    17503280753053

    Returns: -1

  82. 50

    92

    16514267780117

    Returns: -1

  83. 65357

    7574

    65166083859179

    Returns: -1

  84. 1691143

    16240

    16941398578222

    Returns: -1

  85. 15

    1621

    1488551331551

    Returns: -1

  86. 20928

    14

    7319069411333

    Returns: -1

  87. 12610551

    4293

    17913483492737

    Returns: -1

  88. 8821

    1623142

    57209191075709

    Returns: -1

  89. 58232595

    19948

    1430842641841

    Returns: -1

  90. 348

    2

    4821222179083

    Returns: -1

  91. 289346930

    96

    9036467300429

    Returns: -1

  92. 18788297

    15915910

    6915242412797

    Returns: 18

  93. 3

    45457

    39359974975963

    Returns: -1

  94. 8048921

    24

    13556402993953

    Returns: -1

  95. 7336

    130019955

    13545597338554

    Returns: -1

  96. 21

    22

    12647713275683

    Returns: -1

  97. 5

    9471

    13527701992361

    Returns: -1

  98. 16078388

    1105

    32124732961907

    Returns: -1

  99. 55856

    15467314

    61094404206919

    Returns: -1

  100. 87530

    37183534

    5590851026467

    Returns: -1

  101. 29474102

    351538

    183625827002

    Returns: -1

  102. 134572

    792

    3524315761969

    Returns: -1

  103. 23

    21179648

    2885054507882

    Returns: -1

  104. 57

    73

    29235326801313

    Returns: -1

  105. 3

    15515

    32423209864213

    Returns: -1

  106. 783

    78822

    3035177226721

    Returns: -1

  107. 2330998

    139195

    21720563931295

    Returns: -1

  108. 4

    27592768

    14579178289331

    Returns: -1

  109. 113650

    2414

    48382750852517

    Returns: -1

  110. 47862260

    124578991

    47633432015111

    Returns: -1

  111. 6444

    452

    28567469497211

    Returns: -1

  112. 3750

    74

    16521886694237

    Returns: -1

  113. 23070

    4748

    48988064334493

    Returns: -1

  114. 40293625

    2870775

    1931970957337

    Returns: -1

  115. 58202

    291169

    6388813403177

    Returns: -1

  116. 6520316

    247

    4422160996081

    Returns: -1

  117. 12299

    772409

    86590804719043

    Returns: -1

  118. 81

    431266740

    25107654798409

    Returns: -1

  119. 37204

    2428

    14361466909505

    Returns: -1

  120. 21057117

    835

    44549540598347

    Returns: -1

  121. 3250246

    3

    18664341230459

    Returns: -1

  122. 75557218

    1985

    16607181541117

    Returns: -1

  123. 7

    3970

    23957104738793

    Returns: -1

  124. 108029778

    1

    6363599039053

    Returns: -1

  125. 402

    31068360

    157529929703

    Returns: -1

  126. 1

    6

    13399932452789

    Returns: -1

  127. 12722549

    1165

    85002861851

    Returns: -1

  128. 2

    920

    45703839616559

    Returns: -1

  129. 11120952

    5

    8333857892333

    Returns: -1

  130. 103583

    10367985

    53616698381683

    Returns: -1

  131. 219601876

    885699707

    56479553909179

    Returns: -1

  132. 1072

    7

    622314854027

    Returns: -1

  133. 425384

    169385

    12511474140799

    Returns: -1

  134. 23

    514436168

    11390127008773

    Returns: -1

  135. 383917

    69511

    6916515168389

    Returns: -1

  136. 929600835

    9

    132098367853

    Returns: -1

  137. 11251

    44

    337232163383

    Returns: -1

  138. 15435

    62603646

    12376374207091

    Returns: -1

  139. 949635

    4

    385903936871

    Returns: -1

  140. 289992

    92522876

    10822871417713

    Returns: -1

  141. 127332005

    60

    881032704197

    Returns: -1

  142. 19

    110701070

    46836293047067

    Returns: -1

  143. 1995

    60479

    37168170686399

    Returns: -1

  144. 3

    48381406

    117342320891

    Returns: -1

  145. 2564

    137

    378952758757

    Returns: -1

  146. 9

    41

    48021549987811

    Returns: -1

  147. 16

    107738722

    1371646963003

    Returns: -1

  148. 197254836

    805

    3200178473053

    Returns: -1

  149. 3795217

    822233580

    21275745526333

    Returns: 96

  150. 11236503

    2227

    546803503621

    Returns: -1

  151. 1000000000

    1000000000

    70368744177664

    Returns: 239

  152. 806732351

    620440129

    70368744177664

    Returns: 170

  153. 477792040

    167135896

    17584491679747

    Returns: 3409

  154. 205169864

    489595010

    28925463358229

    Returns: -1

  155. 860408746

    785395201

    536647641989

    Returns: 2817

  156. 383733899

    144780631

    22696388428027

    Returns: -1

  157. 457293695

    678737879

    34162989901061

    Returns: -1

  158. 124768466

    753790074

    6078566748941

    Returns: 9244

  159. 371115611

    621260085

    1738541712767

    Returns: 793

  160. 199524446

    235237798

    24744278639667

    Returns: -1

  161. 896111176

    656148090

    14405602024483

    Returns: -1

  162. 317322534

    580391204

    57514884990973

    Returns: 114

  163. 974630388

    112738098

    1078186788851

    Returns: 2352

  164. 433903229

    950137163

    60128449165267

    Returns: -1

  165. 757631083

    723784894

    8477001079973

    Returns: 600

  166. 766574063

    142708358

    27895424386723

    Returns: -1

  167. 666678279

    466068895

    5713742752087

    Returns: -1

  168. 696522359

    550200886

    6641665772089

    Returns: 748

  169. 442489325

    431150913

    60813663188417

    Returns: -1

  170. 750364372

    379749952

    41084693913611

    Returns: -1

  171. 593684037

    374214649

    941542420723

    Returns: 977

  172. 496785468

    782951182

    20081822867189

    Returns: -1

  173. 975313313

    428610375

    61263635132549

    Returns: -1

  174. 312617237

    372297390

    7399295299029

    Returns: -1

  175. 925547801

    741592965

    16318824784879

    Returns: -1

  176. 497811676

    316656721

    38707772145091

    Returns: -1

  177. 428994774

    756135483

    39125081586923

    Returns: -1

  178. 925205548

    844611073

    1353125491258

    Returns: -1

  179. 601418462

    261660824

    64446602899021

    Returns: -1

  180. 890170009

    314741079

    49876183191409

    Returns: -1

  181. 123044474

    279104229

    7115351770138

    Returns: -1

  182. 376786381

    394585479

    7993993836767

    Returns: -1

  183. 236799442

    780465333

    16440724969817

    Returns: -1

  184. 167840405

    368899047

    13556402993953

    Returns: 2116

  185. 310220039

    978963227

    29711089386893

    Returns: -1

  186. 946501844

    903155222

    19005564406406

    Returns: -1

  187. 791335284

    861297829

    10085988365983

    Returns: -1

  188. 195235703

    653183244

    16165268351033

    Returns: 1091

  189. 781831997

    239680270

    18117999664447

    Returns: 1529

  190. 300899350

    275266565

    16311925995457

    Returns: -1

  191. 824758605

    855742131

    14020693119002

    Returns: -1

  192. 845355946

    979353884

    53663583203401

    Returns: -1

  193. 614439135

    103019008

    19069589250623

    Returns: 2742

  194. 130031113

    145160425

    5161021537163

    Returns: -1

  195. 710540353

    366347893

    4516416274423

    Returns: 12886

  196. 758860204

    484830460

    1684627379749

    Returns: 11567

  197. 790385811

    551549861

    75088782063871

    Returns: -1

  198. 478278856

    956681768

    522663060343

    Returns: 24906

  199. 233078622

    674900164

    35083853027849

    Returns: -1

  200. 274818307

    548894878

    9366121197151

    Returns: 9098

  201. 687475765

    869507662

    388437321137

    Returns: 22660

  202. 882833774

    356712327

    842764551053

    Returns: 9182

  203. 284826109

    523858902

    8799666311627

    Returns: 8427

  204. 528846152

    618235816

    2005963316659

    Returns: 13274

  205. 506300368

    402861080

    10446613191307

    Returns: 10980

  206. 513471446

    564039111

    10202947985821

    Returns: 11955

  207. 915292291

    221421267

    2143948696447

    Returns: 5086

  208. 638972606

    203449407

    26438226283493

    Returns: 4651

  209. 392678418

    755527278

    1345065839171

    Returns: 12266

  210. 412143708

    648172288

    11763268698469

    Returns: 9618

  211. 659093563

    213487991

    3367728164887

    Returns: 6455

  212. 352116429

    371407624

    28847406708793

    Returns: -1

  213. 317017055

    361113807

    10664577031777

    Returns: 7385

  214. 777092594

    155685176

    22964307782863

    Returns: 3691

  215. 421912140

    537803022

    16901598570847

    Returns: 13329

  216. 938294969

    696163939

    661796040223

    Returns: 15108

  217. 751533458

    222940195

    5904479671973

    Returns: 6576

  218. 946698844

    567974423

    6130564120223

    Returns: 20132

  219. 906725828

    489615518

    531463760371

    Returns: 19380

  220. 551344393

    801046872

    1833600613127

    Returns: 27261

  221. 110158471

    704666415

    10855142006153

    Returns: 3309

  222. 624332417

    485046584

    7705482598829

    Returns: 20142

  223. 1000000000

    1000000000

    70368744177664

    Returns: 239

  224. 833691343

    935468797

    70368744177664

    Returns: 211

  225. 4

    5

    16

    Returns: 1

  226. 6

    1

    6

    Returns: 0

  227. 5

    5

    20

    Returns: 1

  228. 7

    1

    3

    Returns: 1

  229. 7

    5

    24

    Returns: 3

  230. 100

    100

    10000

    Returns: 0

  231. 2

    1

    2

    Returns: 0

  232. 12

    8

    77

    Returns: 3

  233. 64

    54

    30

    Returns: 9

  234. 3

    3

    9

    Returns: 0

  235. 5

    5

    9

    Returns: 3

  236. 10000

    10000

    289

    Returns: 1177

  237. 3

    5

    15

    Returns: 0

  238. 5

    3

    10

    Returns: 1

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: