Connection Status:
Competition Arena > Manhattan

Manhattan

SRM 319 · 2006-09-18 · by Jan_Kuipers

SRM 319 · 2006-09-18 · by Jan_Kuipers · Simple Math
Class Name: Manhattan
Return Type: int[]
Method Name: furthestPair
Arg Types: (int, int, int, int)
Problem Statement

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.

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
0)
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.

1)
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.

2)
100
912
1023
103871
Returns: {0, 54 }

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

3)
250000
1
1
1000000000
Returns: {0, 249999 }
4)
250000
63
17
1
Returns: {0, 1 }

Submissions are judged against all 59 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Manhattan with a public method vector<int> furthestPair(int n, int a, int b, int m) · 59 test cases · 2 s / 256 MB per case

Submitting as anonymous