Maximize Minimum Difference
플래티넘 II의견: 0
*Note: The time limit for this problem is 4s, twice the default.*
Moo! You are given an integer \(N\) (\(2\le N\le 2000\)). Consider all permutations
\(p=[p_0,p_1,\dots, p_{N-1}]\) of \([0,1,2\dots, N-1]\). Let
\(f(p)=\min_{i=0}^{N-2}|p_i-p_{i+1}|\) denote the minimum absolute difference
between any two consecutive elements of \(p\). and let \(S\) denote the set of all
\(p\) that achieve the maximum possible value of \(f(p)\).
You are additionally given \(K\) (\(0\le K\le N\)) constraints of the form \(p_i=j\)
(\(0\le i,j
constraints, modulo \(10^9+7\).
Problem credits: Benjamin Qi
SCORING
- Input 5: \(N=15\)
- Input 6: \(N=2000\)
- Inputs 7-9: For all test cases, the constraint \(p_0=\lfloor N/2\rfloor\) appears.
- Inputs 10-13: For all test cases, there exists some constraint \(p_i = j\) with \(j\) equal to \(\lfloor N/2\rfloor\).
- Inputs 14-20: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(T\) (\(1\le TN\le 2\cdot 10^4\)) and \(N\), meaning that you
will need to solve \(T\) independent test cases, each specified by a different set
of constraints.
Each test case starts with \(K\), followed by \(K\) lines each containing \(i\) and
\(j\). It is guaranteed that
- The same \(i\) does not appear more than once within the same test case.
- The same \(j\) does not appear more than once within the same test case.
For each test case, the answer modulo \(10^9+7\) on a separate line.
3 4
0
1
1 1
2
0 2
2 32
0
1The maximum possible value of \(f(p)\) is \(2\), and \(S=\{[2,0,3,1], [1,3,0,2]\}\).
9 11
2
0 5
6 9
3
0 5
6 9
1 0
4
0 5
6 9
1 0
4 7
5
0 5
6 9
1 0
4 7
2 6
6
0 5
6 9
1 0
4 7
2 6
9 3
7
0 5
6 9
1 0
4 7
2 6
9 3
5 2
8
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
9
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
3 1
10
0 5
6 9
1 0
4 7
2 6
9 3
5 2
7 4
3 1
8 106
6
1
1
1
1
1
1
1\(p=[5, 0, 6, 1, 7, 2, 9, 4, 10, 3, 8]\) should be counted for all test cases.
10 11
0
1
3 8
2
3 8
5 7
3
3 8
5 7
4 2
4
3 8
5 7
4 2
10 6
5
3 8
5 7
4 2
10 6
8 10
6
3 8
5 7
4 2
10 6
8 10
1 9
7
3 8
5 7
4 2
10 6
8 10
1 9
7 5
8
3 8
5 7
4 2
10 6
8 10
1 9
7 5
2 3
9
3 8
5 7
4 2
10 6
8 10
1 9
7 5
2 3
6 0160
20
8
7
2
1
1
1
1
1\(p=[4, 9, 3, 8, 2, 7, 0, 5, 10, 1, 6]\) should be counted for all test cases.
5 987
3
654 321
543 210
432 106
2
654 321
543 210
1
654 321
1
0 493
00
538184948
693625420
932738155
251798971Make sure to output the answer modulo \(10^9+7\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > December > Platinum
평가 및 의견
Maximize Minimum Difference
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Maximize Minimum Difference