Statistics

Problem Statement for "PatrolRoute"

Problem Statement

There are exactly X*Y places in the Planar Kingdom: For each pair of integers (x, y) such that 0 <= x < X and 0 <= y < Y there is a place with coordinates (x, y). When a citizen of the kingdom wants to move from (x1, y1) to (x2, y2), the required time is |x1 - x2| + |y1 - y2| (where |t| denotes the absolute value of t).

In order to improve stability in the kingdom, the police wants to introduce a specific patrol route. The route will contain exactly three places A, B, and C. A policeman will visit these three places and verify that everything is as it should be. The three places that determine a valid route must satisfy the following criteria::

  • x-coordinates of A, B and C are pairwise distinct.
  • y-coordinates of A, B and C are pairwise distinct.
  • Let T be the total time required to follow along the route: first from A to B, then from B to C and finally from C back to A. T must be between minT and maxT, inclusive.

You are given the ints X, Y, minT, and maxT. Return the number of different patrol routes that satisfy these criteria, modulo 1,000,000,007. Two routes are considered to be different if there is a place that belongs to one of them, but does not belong to the other one.

Definition

Class:
PatrolRoute
Method:
countRoutes
Parameters:
int, int, int, int
Returns:
int
Method signature:
int countRoutes(int X, int Y, int minT, int maxT)
(be sure your method is public)

Constraints

  • X and Y will each be between 3 and 4,000, inclusive.
  • minT will be between 1 and 20,000, inclusive.
  • maxT will be between minT and 20,000, inclusive.

Examples

  1. 3

    3

    1

    20000

    Returns: 6

    The time requirement is very flexible in this case. There are 6 patrol routes where both x and y coordinates of places are pairwise distinct.

  2. 3

    3

    4

    7

    Returns: 0

    The time of 7 is too small for any patrol route.

  3. 4

    6

    9

    12

    Returns: 264

  4. 7

    5

    13

    18

    Returns: 1212

  5. 4000

    4000

    4000

    14000

    Returns: 859690013

    Don't forget about the modulo!

  6. 3

    3

    8

    16490

    Returns: 6

  7. 3

    5

    10

    10

    Returns: 24

  8. 3

    74

    49

    54

    Returns: 20688

  9. 3

    965

    845

    15653

    Returns: 534553440

  10. 3

    2848

    58

    413

    Returns: 331326708

  11. 3

    3852

    2094

    4759

    Returns: 97261732

  12. 3

    4000

    138

    1403

    Returns: 120856025

  13. 3

    4000

    3192

    18090

    Returns: 604282241

  14. 3

    4000

    4126

    4373

    Returns: 962485226

  15. 3

    4000

    948

    2176

    Returns: 130607277

  16. 5

    3

    10

    12

    Returns: 42

  17. 4

    4

    8

    12

    Returns: 96

  18. 6

    19

    4

    18776

    Returns: 116280

  19. 4

    596

    4

    11528

    Returns: 842577120

  20. 7

    1139

    539

    1512

    Returns: 709062678

  21. 4

    3328

    1

    16142

    Returns: 305292795

  22. 6

    4000

    4

    13687

    Returns: 40151047

  23. 7

    4000

    3528

    5968

    Returns: 263582038

  24. 8

    4000

    3357

    7339

    Returns: 167595594

  25. 10

    4000

    3195

    6204

    Returns: 468314247

  26. 69

    3

    16

    43

    Returns: 53214

  27. 78

    10

    9

    81

    Returns: 22615296

  28. 59

    55

    202

    202

    Returns: 5324592

  29. 69

    764

    449

    536

    Returns: 255131323

  30. 49

    1939

    7

    7454

    Returns: 47536481

  31. 15

    3175

    1750

    5517

    Returns: 355443154

  32. 64

    4000

    918

    3723

    Returns: 419556572

  33. 88

    4000

    2885

    6204

    Returns: 688183076

  34. 54

    4000

    696

    4511

    Returns: 44199280

  35. 41

    4000

    3850

    5823

    Returns: 407417253

  36. 919

    3

    1349

    1392

    Returns: 21210882

  37. 662

    4

    34

    492

    Returns: 352261560

  38. 290

    57

    452

    684

    Returns: 338550943

  39. 189

    331

    154

    10373

    Returns: 325724526

  40. 826

    2274

    2648

    4657

    Returns: 206951426

  41. 550

    3214

    1431

    3693

    Returns: 191123235

  42. 792

    4000

    702

    4928

    Returns: 536532765

  43. 725

    4000

    6003

    6772

    Returns: 679294073

  44. 902

    4000

    559

    2527

    Returns: 884141942

  45. 428

    4000

    2443

    4815

    Returns: 743555437

  46. 2237

    3

    406

    1233

    Returns: 811851535

  47. 2632

    5

    2004

    14285

    Returns: 436563411

  48. 1278

    62

    504

    899

    Returns: 858000322

  49. 1734

    666

    1482

    2578

    Returns: 959315776

  50. 1050

    1910

    3645

    15557

    Returns: 96866904

  51. 1797

    3221

    1860

    6896

    Returns: 239429453

  52. 1068

    4000

    2

    8140

    Returns: 487587099

  53. 2644

    4000

    2950

    16801

    Returns: 240109543

  54. 1153

    4000

    2614

    7521

    Returns: 567674971

  55. 2672

    4000

    1

    6995

    Returns: 558833528

  56. 3179

    3

    1601

    10334

    Returns: 47540751

  57. 3722

    6

    1835

    4700

    Returns: 630079540

  58. 3097

    67

    6

    16139

    Returns: 417332860

  59. 3073

    896

    2971

    5162

    Returns: 42264110

  60. 3611

    1909

    3455

    15516

    Returns: 265817429

  61. 3684

    3658

    790

    3571

    Returns: 642256061

  62. 3912

    4000

    5511

    11808

    Returns: 655385380

  63. 3571

    4000

    5

    17352

    Returns: 546521875

  64. 3463

    4000

    9932

    11412

    Returns: 603574675

  65. 3802

    4000

    6309

    16618

    Returns: 370713244

  66. 4000

    3

    3169

    6678

    Returns: 172914481

  67. 4000

    7

    2339

    3206

    Returns: 138485080

  68. 4000

    90

    1330

    7479

    Returns: 235469308

  69. 4000

    153

    1417

    7391

    Returns: 804113801

  70. 4000

    2201

    1181

    18727

    Returns: 838302983

  71. 4000

    3439

    4704

    12176

    Returns: 892445093

  72. 4000

    4000

    154

    14115

    Returns: 271094810

  73. 4000

    4000

    7

    6955

    Returns: 12515125

  74. 4000

    4000

    3536

    13883

    Returns: 829054842

  75. 4000

    4000

    2958

    11049

    Returns: 530782180

  76. 4000

    3

    966

    7406

    Returns: 398387820

  77. 4000

    5

    4581

    7565

    Returns: 768689693

  78. 4000

    81

    7

    2216

    Returns: 88083667

  79. 4000

    763

    353

    3088

    Returns: 609972979

  80. 4000

    2415

    6498

    8052

    Returns: 906988521

  81. 4000

    3786

    1

    17433

    Returns: 211309943

  82. 4000

    4000

    4757

    11014

    Returns: 941272513

  83. 4000

    4000

    2264

    6947

    Returns: 770259243

  84. 4000

    4000

    9278

    14869

    Returns: 18742782

  85. 4000

    4000

    7615

    10237

    Returns: 761102148

  86. 4000

    3

    6925

    6925

    Returns: 0

  87. 4000

    7

    791

    1684

    Returns: 535319677

  88. 4000

    88

    1068

    5291

    Returns: 637493061

  89. 4000

    525

    4986

    17078

    Returns: 154085517

  90. 4000

    1039

    5973

    6375

    Returns: 686890365

  91. 4000

    3702

    595

    2847

    Returns: 954799055

  92. 4000

    4000

    5668

    12617

    Returns: 934060675

  93. 4000

    4000

    5351

    9402

    Returns: 904618957

  94. 4000

    4000

    3176

    3942

    Returns: 597294897

  95. 4000

    4000

    10577

    18396

    Returns: 294461960

  96. 4000

    3

    5187

    19979

    Returns: 211944834

  97. 4000

    7

    2

    19417

    Returns: 320264334

  98. 4000

    56

    2492

    5314

    Returns: 532258081

  99. 4000

    419

    4176

    18328

    Returns: 96662287

  100. 4000

    1126

    6818

    6818

    Returns: 328603423

  101. 4000

    3161

    1

    15656

    Returns: 635094855

  102. 4000

    4000

    1

    16087

    Returns: 841484969

  103. 4000

    4000

    1

    15583

    Returns: 881384874

  104. 4000

    4000

    14660

    15978

    Returns: 306325003

  105. 4000

    4000

    4408

    9435

    Returns: 255776655

  106. 4000

    4000

    1

    20000

    Returns: 841484969

  107. 4000

    4000

    1

    7

    Returns: 0

  108. 4000

    4000

    15996

    15996

    Returns: 95904024

  109. 4000

    4000

    15997

    20000

    Returns: 0

  110. 4000

    4000

    9

    15995

    Returns: 649676921

  111. 4000

    4000

    1

    19998

    Returns: 841484969

  112. 4000

    4000

    4000

    20000

    Returns: 445258349

  113. 4000

    4000

    20000

    20000

    Returns: 0

  114. 4000

    4000

    331

    20000

    Returns: 888967583

  115. 3999

    2999

    1999

    19998

    Returns: 40906664

  116. 3970

    3121

    1

    14560

    Returns: 449660083

  117. 4000

    4000

    2138

    2140

    Returns: 100744667

  118. 4000

    3999

    10000

    20000

    Returns: 423622390

  119. 3795

    3997

    3

    19997

    Returns: 124289875

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: