NRooksPosition
SRM 795 · 2020-12-11 · by misof
Problem Statement
This problem takes place on an infinite grid of unit squares. There are N tokens on the grid. Currently, token number i is in the square at coordinates (X[i], Y[i]). Multiple tokens may share the same square at any time.
You can move the tokens. The only allowed operation is called a step and involves moving one token into one of the four squares adjacent to its current square.
We say that the N tokens are in an N rooks position if the tokens occupy N consecutive rows of the grid and at the same time they occupy N consecutive columns of the grid. (Each of those rows and columns must actually be occupied by one of the tokens. In other words, if the tokens are in this position and we would cut out the smallest rectangle that contains all tokens, we would have an N times N board on which the tokens represent one possible position of N rooks that don't attack each other.)
Given the initial positions of all tokens, find the minimum number of steps needed to move all tokens into some valid N rooks position.
As we need to have large inputs, please be so kind and use the following simple pseudocode to generate the arrays X and Y with the coordinates of all points:
L = length(Xprefix)
for i = 0 to L-1:
X[i] = Xprefix[i]
Y[i] = Yprefix[i]
for i = L to N-1:
X[i] = (A * X[i-1] + B * X[i-2]) mod C
Y[i] = (A * Y[i-1] + B * Y[i-2]) mod C
Notes
- The reference solution is fast enough for any input within the allowed range of N. It does not depend on the pseudorandom generator in any way.
Constraints
- N will be between 2 and 10^6, inclusive.
- Xprefix will have between 2 and min(500,N) elements, inclusive.
- Yprefix will have the same number of elements as Xprefix.
- All elements of Xprefix and Yprefix will be between 0 and 10^9 - 1, inclusive.
- A and B will be between 0 and 10^9 - 1, inclusive.
- C will be between 1 and 10^9, inclusive.
3
{5, 8, 7}
{1, 3, 5}
0
0
1
Returns: 3
The initial configuration of tokens looks as follows (X grows to the right, Y grows upwards): ......2. ........ .......1 ........ ....0... One optimal solution is to move token 0 one step right, then one step up, and then move token 2 one step down, producing: ........ ......2. .......1 .....0.. ........ The tokens are now in three consecutive rows and three consecutive columns.
999999
{0, 0}
{0, 0}
0
0
1
Returns: 499999000000
999,999 tokens, all of them start at (0,0). One optimal solution is to distribute them to the points (-499999,499999) to (499999,-499999).
2
{953523433, 43}
{2324, 244525243}
4
7
47
Returns: 1198046307
Two tokens far from each other. They must almost-meet somewhere. It doesn't really matter whether we push just one of them the whole way or whether we push each of them a part of the way towards the other.
10
{47, 530}
{9421, 125521}
1234567
7654321
987654321
Returns: 5509135972
X = {47, 530, 26419276, 176189634, 267705568, 376691149, 738601310, 368332752, 756100319, 534681602, } Y = {9421, 125521, 902603039, 753444129, 36706724, 375900842, 810804826, 812632368, 128411635, 285087958, }
2
{7,8}
{9,9}
12
33
4
Returns: 1
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NRooksPosition with a public method long long minSteps(int N, vector<int> Xprefix, vector<int> Yprefix, int A, int B, int C) · 88 test cases · 2 s / 256 MB per case