ThreePoints
TCO12 Parallel Round 2C · 2012-03-27 · by rng_58
TCO12 Parallel Round 2C · 2012-03-27 · by rng_58 · Math, Search
Problem Statement
Problem Statement
There is a two-dimensional infinite plane. Toastman painted N of the grid points in the plane black. These grid points are numbered 0 through N-1. The coordinates of point i are (x[i],y[i]). They are chosen in such a way that no two points share the same x-coordinate and no two points share the same y-coordinate.
Toastwoman wants to color three of these N points: some point r will be red, some point g green, and some point b blue. She thinks a coloring is beautiful if x[r] < x[g] < x[b] and at the same time y[r] < y[b] < y[g]. (Note that the order of colors for the y-coordinate is not the same as the order for the x-coordinate.)
In order to have a large set of points, we will generate one using a pseudorandom generator. You will be given theint N specifying the number of points, and eight int s: xzero, xmul, xadd, xmod, yzero, ymul, yadd, and ymod. Generate the coordinates of the points in the following way:
Toastwoman wants to color three of these N points: some point r will be red, some point g green, and some point b blue. She thinks a coloring is beautiful if x[r] < x[g] < x[b] and at the same time y[r] < y[b] < y[g]. (Note that the order of colors for the y-coordinate is not the same as the order for the x-coordinate.)
In order to have a large set of points, we will generate one using a pseudorandom generator. You will be given the
- x[0] = xzero
- For each i between 1 and N-1, inclusive, x[i] = (x[i-1] * xmul + xadd) % xmod
- y[0] = yzero
- For each i between 1 and N-1, inclusive, y[i] = (y[i-1] * ymul + yadd) % ymod
Notes
- There is a solution that does not use any properties of the pseudorandom generator. This solution would solve any set of N points within the time limit.
Constraints
- N will be between 3 and 300,000, inclusive.
- xmod and ymod will be between N and 1,000,000,000, inclusive.
- xzero, xmul and xadd will be between 0 and xmod - 1, inclusive.
- yzero, ymul and yadd will be between 0 and ymod - 1, inclusive.
- No two points will have the same x-coordinate.
- No two points will have the same y-coordinate.
Examples
0)
9 3 8 6 11 5 7 8 11 Returns: 8
There are 9 points. The coordinates of points are (3, 5), (8, 10), (4, 1), (5, 4), (2, 3), (0, 7), (6, 2), (10, 0), and (9, 8). There are 8 beautiful coloring.
1)
300000 3 8 6 999999997 5 7 8 999999997 Returns: 748746671709844
2)
300000 985630507 87425790 563581248 999999937 87797782 944618609 944054191 999999937 Returns: 749364484652325
3)
300000 140860447 513229178 410736925 999999937 198517093 601121366 992497434 999999937 Returns: 747826412223783
4)
300000 576911469 473167597 126264043 999999937 676027818 666805780 735431024 999999937 Returns: 752657319963487
Submissions are judged against all 51 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ThreePoints with a public method long long countColoring(int N, int xzero, int xmul, int xadd, int xmod, int yzero, int ymul, int yadd, int ymod) · 51 test cases · 2 s / 256 MB per case