Statistics

Problem Statement for "AlternateColors2"

Problem Statement

Bob is playing with his ball destroyer robot. Initially, Bob had r red balls, g green balls and b blue balls. The robot repeated the following 3-step program until there were no balls left:

  • If there is at least one red ball available, destroy one red ball.
  • If there is at least one green ball available, destroy one green ball.
  • If there is at least one blue ball available, destroy one blue ball.
Bob forgot how many balls of each color he initially had. He only remembers that there were n balls in total and that the k-th (1-based index) ball that was destroyed was red. Return the total number of different initial settings that match that description. Formally, return the number of different tuples (r, g, b) such that r + g + b = n and the k-th ball that was destroyed was red.

Definition

Class:
AlternateColors2
Method:
countWays
Parameters:
int, int
Returns:
long
Method signature:
long countWays(int n, int k)
(be sure your method is public)

Notes

  • It follows from the constraints that the return value will always fit into a long.

Constraints

  • n will be between 1 and 100000, inclusive.
  • k will be between 1 and n, inclusive.

Examples

  1. 100000

    100000

    Returns: 1666700000

  2. 1

    1

    Returns: 1

    There was only one ball. This ball was necessarily the first ball destroyed. Therefore, it had to be red.

  3. 2

    2

    Returns: 1

  4. 3

    3

    Returns: 3

    There are three cases in which the third ball to be destroyed is red: r = 3, b = 0, g = 0. r = 2, b = 1, g = 0. r = 2, b = 0, g = 1.

  5. 4

    4

    Returns: 4

  6. 1000

    1000

    Returns: 167000

  7. 6

    4

    Returns: 9

  8. 1000

    500

    Returns: 124833

  9. 1000

    501

    Returns: 125833

  10. 1000

    502

    Returns: 249585

  11. 6

    1

    Returns: 21

  12. 3

    1

    Returns: 6

  13. 4

    1

    Returns: 10

  14. 1000

    503

    Returns: 125832

  15. 1000

    504

    Returns: 125832

  16. 1000

    505

    Returns: 249088

  17. 1000

    506

    Returns: 125833

  18. 1000

    2

    Returns: 1

    In order for the second destroyed ball to be red, there would have to be zero balls of the other colors.

  19. 100000

    100000

    Returns: 1666700000

  20. 56278

    5627

    Returns: 100300340

  21. 56278

    1

    Returns: 1583634781

  22. 100000

    1

    Returns: 5000050000

  23. 1000

    1

    Returns: 500500

  24. 6

    6

    Returns: 8

  25. 62

    31

    Returns: 1008

  26. 100000

    50000

    Returns: 1249983333

  27. 80000

    40000

    Returns: 1600020000

  28. 5

    3

    Returns: 7

  29. 74534

    544

    Returns: 2750738739

  30. 74534

    545

    Returns: 13515684

  31. 74534

    546

    Returns: 13515684

  32. 875

    43

    Returns: 359331

  33. 875

    44

    Returns: 11971

  34. 874

    45

    Returns: 13617

  35. 100000

    49999

    Returns: 2500108335

  36. 70863

    69730

    Returns: 837378790

  37. 12400

    3703

    Returns: 50850651

  38. 24179

    16610

    Returns: 87889537

  39. 51792

    47007

    Returns: 443272961

  40. 13866

    504

    Returns: 2287320

  41. 54965

    6086

    Returns: 105301873

  42. 87565

    79838

    Returns: 1268008577

  43. 10484

    3755

    Returns: 10775964

  44. 78436

    41970

    Returns: 803753480

  45. 40378

    10792

    Returns: 563516141

  46. 530

    283

    Returns: 67536

  47. 40317

    27381

    Returns: 243042129

  48. 71796

    20481

    Returns: 420297541

  49. 67027

    38501

    Returns: 613170018

  50. 70844

    44538

    Returns: 721159296

  51. 98911

    71781

    Returns: 1507942561

  52. 23657

    22120

    Returns: 94070694

  53. 60495

    38763

    Returns: 531262187

  54. 33703

    22273

    Returns: 232884428

  55. 23671

    10885

    Returns: 147898518

  56. 63145

    9116

    Returns: 177993383

  57. 9052

    7040

    Returns: 12982765

  58. 47920

    19560

    Returns: 248679320

  59. 40827

    19542

    Returns: 202305298

  60. 62887

    11558

    Returns: 219987721

  61. 25736

    730

    Returns: 318828039

  62. 90062

    86396

    Returns: 1349647069

  63. 27830

    14022

    Returns: 97312680

  64. 47805

    20634

    Returns: 257849342

  65. 13933

    2890

    Returns: 73006835

  66. 4101

    93

    Returns: 129729

  67. 93227

    4641

    Returns: 140722489

  68. 11814

    4450

    Returns: 41340642

  69. 73904

    24008

    Returns: 495339805

  70. 66302

    22795

    Returns: 1363670574

  71. 22947

    9639

    Returns: 58260179

  72. 88732

    18249

    Returns: 484328989

  73. 51413

    12604

    Returns: 942606258

  74. 75021

    17224

    Returns: 2051538184

  75. 58238

    6928

    Returns: 1442860335

  76. 32653

    1561

    Returns: 499977351

  77. 85534

    12358

    Returns: 3004269500

  78. 37917

    2950

    Returns: 647186989

  79. 78624

    32165

    Returns: 670575324

  80. 20582

    2482

    Returns: 179810298

  81. 18418

    1906

    Returns: 147422556

  82. 37379

    6010

    Returns: 560876892

  83. 99342

    47773

    Returns: 2531335503

  84. 63954

    30887

    Returns: 499469256

  85. 75697

    24510

    Returns: 518329310

  86. 63222

    23517

    Returns: 403469921

  87. 42782

    14432

    Returns: 171082081

  88. 55614

    2632

    Returns: 1451193315

  89. 81409

    22385

    Returns: 523959254

  90. 62627

    66

    Returns: 1377090

  91. 50980

    11127

    Returns: 168493361

  92. 52263

    2427

    Returns: 41349691

  93. 48078

    5543

    Returns: 83727336

  94. 71029

    2480

    Returns: 57647367

  95. 44684

    16528

    Returns: 597040290

  96. 4077

    1875

    Returns: 1965015

  97. 31272

    16275

    Returns: 125525085

  98. 23483

    12856

    Returns: 129558981

  99. 86101

    38775

    Returns: 862332239

  100. 53908

    25493

    Returns: 349794676

  101. 21480

    11177

    Returns: 59213592

  102. 79474

    42537

    Returns: 825346901

  103. 34992

    16173

    Returns: 145071761

  104. 91207

    46363

    Returns: 2056848693

  105. 51637

    26837

    Returns: 341907174

  106. 87787

    44402

    Returns: 970702401

  107. 9435

    4631

    Returns: 10993280

  108. 27759

    13290

    Returns: 93539450

  109. 73958

    33948

    Returns: 644842260

  110. 99836

    45561

    Returns: 1170311341

  111. 46109

    22049

    Returns: 257874750

  112. 33538

    16970

    Returns: 141711081

  113. 5916

    2840

    Returns: 4255109

  114. 8729

    4670

    Returns: 9952177

  115. 55418

    26761

    Returns: 785642691

  116. 91855

    49113

    Returns: 1101802857

  117. 8864

    4338

    Returns: 9682416

  118. 95555

    49306

    Returns: 2234807148

  119. 40425

    18468

    Returns: 192017952

  120. 22296

    12028

    Returns: 118001598

  121. 63796

    33989

    Returns: 530266660

  122. 83821

    44761

    Returns: 1679615031

  123. 9165

    4287

    Returns: 10040031

  124. 13246

    6622

    Returns: 43871856

  125. 22140

    11751

    Returns: 63722353

  126. 2116

    2048

    Returns: 746109

  127. 14416

    13569

    Returns: 34522645

  128. 19922

    19920

    Returns: 66154320

  129. 5452

    4411

    Returns: 5317963

  130. 26650

    23121

    Returns: 116306013

  131. 72962

    59501

    Returns: 857066808

  132. 55906

    46266

    Returns: 505440628

  133. 79161

    75101

    Returns: 1041689774

  134. 60020

    53374

    Returns: 615142071

  135. 30228

    27997

    Returns: 153959720

  136. 37867

    35597

    Returns: 238138754

  137. 46355

    39424

    Returns: 374158221

  138. 31498

    27455

    Returns: 162640192

  139. 93441

    87950

    Returns: 1450203889

  140. 29916

    28127

    Returns: 148637728

  141. 44058

    37547

    Returns: 316467060

  142. 9196

    8836

    Returns: 14140608

  143. 2818

    2437

    Returns: 1373165

  144. 4720

    4572

    Returns: 3710940

  145. 78822

    71736

    Returns: 1027139960

  146. 15877

    13094

    Returns: 40724849

  147. 27279

    27185

    Returns: 124031594

  148. 93339

    89418

    Returns: 1449495586

  149. 9740

    9290

    Returns: 15780313

  150. 9157

    8914

    Returns: 13997803

  151. 1699

    1574

    Returns: 478937

  152. 12597

    11582

    Returns: 26278881

  153. 40027

    38309

    Returns: 266548210

  154. 12043

    10476

    Returns: 23766552

  155. 38946

    33170

    Returns: 247245329

  156. 1

    1

    Returns: 1

  157. 2

    1

    Returns: 3

  158. 5

    3

    Returns: 7

  159. 8

    3

    Returns: 13

  160. 8

    3

    Returns: 13

  161. 5

    5

    Returns: 6

  162. 4

    2

    Returns: 1

  163. 7

    6

    Returns: 10

  164. 10

    3

    Returns: 17

  165. 9

    1

    Returns: 45

  166. 99997

    4

    Returns: 4999450018

  167. 99998

    49998

    Returns: 1249950000

  168. 100000

    8

    Returns: 199997

  169. 10000

    1234

    Returns: 42282791

  170. 100000

    33334

    Returns: 3148140741

  171. 100000

    7

    Returns: 4999650011

  172. 24566

    578

    Returns: 4661569

  173. 14

    10

    Returns: 42

  174. 100000

    4

    Returns: 4999750006

  175. 99999

    55555

    Returns: 2325126749

  176. 1000

    30

    Returns: 9860

  177. 999

    888

    Returns: 164576

  178. 43

    27

    Returns: 291

  179. 100000

    98765

    Returns: 1666445796

  180. 8

    7

    Returns: 15

  181. 100000

    99998

    Returns: 1666699997

  182. 16

    9

    Returns: 45

  183. 20000

    10000

    Returns: 100005000

  184. 100000

    99999

    Returns: 1666700001

  185. 99999

    4

    Returns: 4999650009

  186. 30

    13

    Returns: 271

  187. 12312

    12312

    Returns: 25268328

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: