Statistics

Problem Statement for "Manhattan"

Problem Statement

My whole family lives in Manhattan, and consists of n people numbered 0 through (n - 1). The roads in Manhattan are a bit peculiar: they all go from North to South or from West to East, and together they form a complete grid of roads. Therefore, the distance between two intersections (x,y) and (x',y') equals abs(x-x')+abs(y-y'). Knowing the intersections where my family members live, I'd like to find the two different persons with the furthest distance between them. You are to help me by returning a int[] containing the 0-based indices of the people who form the furthest pair. If there are several furthest pairs, return the one among them with the smallest first index. If there are still multiple pairs left, return the one among them with the smallest second index.

The intersection where the ith family member lives is defined by the following sequence: 
xi = (a * yi-1 + b) % m, for i > 0.
yi = (a * xi + b) % m, for i >= 0.
with x0=0.

Definition

Class:
Manhattan
Method:
furthestPair
Parameters:
int, int, int, int
Returns:
int[]
Method signature:
int[] furthestPair(int n, int a, int b, int m)
(be sure your method is public)

Constraints

  • n will be between 2 and 250,000, inclusive.
  • a, b and m will each be between 1 and 1,000,000,000, inclusive.

Examples

  1. 10

    7

    13

    23

    Returns: {2, 6 }

    The intersections where my family members live are (0,13), (12,5), (2,4), (18,1), (20,15), (3,11), (21,22), (6,9), (7,16) and (10,14). The 2nd and 6th intersections (zero-indexed) are furthest apart. The distance is abs(2-21)+abs(4-22)=37.

  2. 10

    17

    17

    17

    Returns: {0, 1 }

    All of them live at (0,0), so all pairs have distance 0. The lexicographically first pair is {0, 1}. Please note that we are looking for two different persons, so pair {0, 0} is invalid.

  3. 100

    912

    1023

    103871

    Returns: {0, 54 }

    Intersections 0 (0,1023) and 54 (96346,97580) are furthest apart.

  4. 250000

    1

    1

    1000000000

    Returns: {0, 249999 }

  5. 250000

    63

    17

    1

    Returns: {0, 1 }

  6. 245453

    1

    123456789

    213574341

    Returns: {26588, 114131 }

  7. 249252

    33

    124512

    234522

    Returns: {92, 197 }

  8. 234123

    124512

    21435463

    45125111

    Returns: {196780, 226826 }

  9. 241234

    3

    6786721

    104395301

    Returns: {0, 234592 }

  10. 200000

    7

    50000000

    104402897

    Returns: {3986, 19510 }

  11. 212345

    51

    5421

    912453927

    Returns: {0, 41193 }

  12. 234512

    5123451

    654321245

    995325212

    Returns: {8890, 40468 }

  13. 223454

    23451

    3465215

    54353621

    Returns: {15517, 91423 }

  14. 54321

    23451

    3465215

    543536

    Returns: {3607, 3623 }

  15. 249999

    5342324

    425234431

    645234512

    Returns: {2004, 6744 }

  16. 250000

    43532532

    65326255

    21235432

    Returns: {118368, 217282 }

  17. 222222

    45907832

    23094682

    2304598

    Returns: {76540, 86936 }

  18. 2000

    566562

    2345256

    21451

    Returns: {121, 152 }

  19. 10000

    1000000000

    1000000000

    12345

    Returns: {21, 231 }

  20. 2

    123

    456

    789

    Returns: {0, 1 }

  21. 2

    175

    175

    175

    Returns: {0, 1 }

  22. 250000

    84728345

    84728345

    84728345

    Returns: {0, 1 }

  23. 92007

    396661373

    378703534

    64

    Returns: {0, 6 }

  24. 124410

    532609101

    627802741

    72

    Returns: {1, 3 }

  25. 105832

    239508656

    410620146

    33

    Returns: {0, 3 }

  26. 75586

    284763544

    899436620

    72

    Returns: {1, 7 }

  27. 5

    655748329

    179812622

    32

    Returns: {0, 2 }

  28. 3

    648253259

    934483318

    42

    Returns: {0, 1 }

  29. 250000

    1

    49999999

    1000000000

    Returns: {0, 9 }

  30. 250000

    912

    1023

    103871

    Returns: {0, 3321 }

  31. 250000

    34345354

    54353

    235354544

    Returns: {0, 45145 }

  32. 250000

    423243

    42342

    100000000

    Returns: {0, 240003 }

  33. 25000

    912

    1023

    103871

    Returns: {0, 3321 }

  34. 250000

    799999999

    899999999

    999999998

    Returns: {0, 229067 }

  35. 250000

    999997

    987651

    1000000

    Returns: {0, 32212 }

  36. 250000

    964811441

    746601218

    521772220

    Returns: {183516, 247257 }

  37. 249995

    531357995

    699233448

    999999997

    Returns: {91735, 164240 }

  38. 250000

    11251234

    312341412

    812341211

    Returns: {148861, 151664 }

  39. 250000

    997654321

    542312743

    542312743

    Returns: {0, 1 }

  40. 250000

    999999991

    999999993

    999999997

    Returns: {0, 31170 }

  41. 250000

    999999998

    123456789

    1000000000

    Returns: {1623, 142775 }

  42. 250000

    91234

    1023234

    103871234

    Returns: {720, 5229 }

  43. 250000

    324244543

    2342

    1000000000

    Returns: {0, 66491 }

  44. 249999

    989989989

    999999999

    777777777

    Returns: {1, 2 }

  45. 250000

    113578923

    25298742

    999999997

    Returns: {51779, 97860 }

  46. 10000

    100000701

    100000003

    100000005

    Returns: {0, 1552 }

  47. 250000

    13

    17

    999999997

    Returns: {0, 167068 }

  48. 250000

    999999999

    999937

    1000000000

    Returns: {0, 1 }

  49. 250000

    999999998

    999999997

    999999999

    Returns: {0, 1 }

  50. 250000

    999999998

    999999995

    999999997

    Returns: {0, 1 }

  51. 250000

    926478857

    957846251

    999823477

    Returns: {8818, 150881 }

  52. 250000

    1

    2

    3

    Returns: {0, 1 }

  53. 250000

    51277316

    52516122

    512751255

    Returns: {139950, 247717 }

  54. 25000

    999999999

    999999999

    1000000000

    Returns: {0, 1 }

  55. 100000

    1

    1

    1000100

    Returns: {0, 99999 }

  56. 25000

    798765311

    139876531

    239876531

    Returns: {10902, 21301 }

  57. 250000

    943720

    994852

    839208

    Returns: {185, 773 }

  58. 250000

    912

    1023

    1000000000

    Returns: {0, 157848 }

  59. 250000

    1

    1

    1000000000

    Returns: {0, 249999 }

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: