Manhattan | Topcoder Archive

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:

x_i = (a * y_i-1 + b) % m, for i > 0.
y_i = (a * x_i + b) % m, for i >= 0.

with x₀=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

```
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.
```
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.
```
100
```
```
912
```
```
1023
```
```
103871
```
```
Returns: {0, 54 }
```
Intersections 0 (0,1023) and 54 (96346,97580) are furthest apart.

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.