ComponentsForever
TCO19 SRM 760 · 2019-06-11 · by misof
Problem Statement
This problem has a non-standard time limit of 5 seconds.
A community of n frogs lives in a pond. The frogs are numbered 0 through n-1. Frog i lives at coordinates (X[i], Y[i]). Use the following pseudocode to generate these coordinates:
for i = 0 .. len(Xprefix)-1:
X[i] = Xprefix[i]
Y[i] = Yprefix[i]
state = seed
for i = len(Xprefix) .. n-1:
state = (1103515245 * state + 12345)
X[i] = state modulo Xrange
state = state modulo 2^31
state = (1103515245 * state + 12345)
Y[i] = state modulo Yrange
state = state modulo 2^31
A hop is a move in which each coordinate of a frog changes by +1 or -1. In other words, in a hop a frog can move from its current location to any of the four diagonally adjacent locations.
Each frog has a walkie-talkie. There are two integers L < R that describe their range. Two frogs can communicate using their walkie-talkies if and only if there is some X in the closed interval [L,R] such that one frog can reach the other by making exactly X hops. Note that X does not have to be the smallest possible number of hops between the two frogs.
A new frog named Manish recently visited this pond. Manish is an experienced politician. Ideally, he would want to make each frog a different promise. However, Manish knows that some frogs can communicate, and he cannot make different promises to two frogs who can talk to each other. Let P(L,R) be the largest number of different promises Manish can give the frogs for the values L and R.
You are given the
Notes
- In the definition of the return value, Y^(-1) denotes the inverse element to Y when computing modulo 10^9 + 7. You may assume that for each valid input this value exists.
Constraints
- n will be between 2 and 75,000, inclusive.
- Xprefix will have between 0 and min(n,200) elements, inclusive.
- Yprefix will have the same number of elements as Xprefix.
- Each element of Xprefix and Yprefix will be between 0 and 500,000,000 inclusive.
- seed will be between 0 and 500,000,000 inclusive.
- Xrange and Yrange will each be between 1 and 500,000,001 inclusive.
- Llo and Rhi will satisfy 1 <= Llo < Rhi <= 500,000,000.
- The input will be such that the locations of the n frogs will all be distinct.
2
{1,4}
{1,3}
1
1
1
1
5
Returns: 2
We have two frogs: one at (1, 1) and the other at (4, 3). Regardless of the range of the walkie-talkies, these two frogs cannot communicate. Hence, Manish can always make two distinct promises.
2
{1,3}
{1,3}
1
1
1
1
5
Returns: 1
Here we have two frogs located at (1, 1) and (3, 3). For any pair (L, R) such that 1 <= L < R <= 5, the closed interval [L,R] will contain some value x such that the first frog can get to the other in x hops. Hence, regardless of the range of walkie-talkies, Manish must always tell both frogs the same promise.
2
{5,21232}
{6,123}
1
1
1
1
5132
Returns: 2
These two frogs are too far from each other, the ranges of walkie-talkies we are interested in are not sufficient to reach from one frog to the other.
18
{16, 21, 33, 46, 10}
{22, 25, 46, 18, 8}
1253
47
31
12
86
Returns: 394234239
For reference, the full arrays X and Y once you finish generating them should look as follows: X = { 16, 21, 33, 46, 10, 19, 8, 15, 42, 38, 21, 25, 2, 11, 1, 11, 29, 45 } Y = { 22, 25, 46, 18, 8, 28, 14, 24, 21, 26, 15, 30, 28, 23, 16, 30, 23, 9 }
9
{28, 33, 6, 14, 20, 35, 49, 15, 46}
{48, 32, 11, 28, 1, 22, 24, 41, 1}
1522
9
35
18
55
Returns: 512091044
If the range for the walkie-talkies is [18,19], [18,20], or [19,20], Manish will be able to make four different promises. In each of the 700 other valid scenarios Manish can only make two different promises. Thus, the expected number of promises is (3*4 + 700*2) / 703 =
Submissions are judged against all 79 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ComponentsForever with a public method int countComponents(int n, vector<int> Xprefix, vector<int> Yprefix, int seed, int Xrange, int Yrange, int Llo, int Rhi) · 79 test cases · 2 s / 256 MB per case