Arranging Cows
플래티넘 II의견: 0
You are given a length-\(N\) bitstring \(s_{1\dots N}\) (\(2\le N\le 10^9\)). In one
operation, you can reverse a range \(s_{l\dots r}\) if the following conditions
are true:
- The size of the range is even.
- The first half of the range consists of one character (either \(0\) or \(1\)), and the second half contains the opposite character
- Either \(l = 1\) or \(s_{l-1} \neq s_l\)
- Either \(r = N\) or \(s_{r+1} \neq s_r\)
Find the minimum number of operations to move all of the \(1\)s to the front, or
report that it is impossible. If it is possible to do so, also output the number
of sequences of operations achieving this minimum, modulo \(10^9+7\).
Problem credits: Sujay Konda
SCORING
- Input 3: \(N \leq 10\), all tests are distinct
- Input 4: \(R\le 10\)
- Inputs 5-8: \(R\le 100\), the sum of \(R^2\) over all tests does not exceed \(10^5\), the minimum number of operations is guaranteed to equal \(R/2-1\).
- Inputs 9-12: \(R\le 100\), the sum of \(R^2\) over all tests does not exceed \(10^5\).
- Inputs 13-16: No additional constraints.
Problem credits: Sujay Konda
The first line contains \(T\) (\(1 \leq T \leq 2026\)), the number of independent
tests. Each test is specified in the following format:
The bitstring is given in a compressed format. The first line contains \(R\), the
number of runs in the string (\(2\le R\le 800\)), and the first character of the
string (either 0 or 1).
The next line contains \(R\) space-separated integers \(l_1,l_2,l_3,\ldots l_R\)
(\(0
\(s\). It's guaranteed that \(N=\sum_{i=1}^Rl_i\le 10^9\).
Additionally, it is guaranteed that the sum of \(R^2\) over all tests does not
exceed \(1.5\cdot 10^6\).
For each test case, print the minimum number of operations to move all of the
\(1\)s to the front or \(-1\) if it is impossible, as well as the number of
sequences of operations achieving this minimum modulo \(10^9+7\).
9
2 0
1 1
2 1
1 1
2 1
2 1
2 0
1 2
5 0
1 1 1 2 1
3 0
1 2 1
8 0
1 1 2 1 1 2 1 1
6 0
3 3 1 2 2 1
7 0
5 1 1 3 2 1 11 1
0 1
0 1
-1 0
2 1
-1 0
4 7
3 1
4 1Here is the sequence of two operations for the fifth testcase:
\(010110 \to 100110 \to 111000.\)
5
2 1
1 1
4 1
1 1 1 1
6 1
1 1 1 1 1 1
8 1
1 1 1 1 1 1 1 1
10 1
1 1 1 1 1 1 1 1 1 10 1
1 1
2 1
3 3
4 9In all of these test cases, the minimum number of operations equals \(R/2-1\).
Here are all three possible sequences of three operations for the fourth test
case:
(1)
10101010
-> 11001010
-> 11001100
-> 11110000
(2)
10101010
-> 10110010
-> 10001110
-> 11110000
(3)
10101010
-> 10101100
-> 11001100
-> 11110000
평가 및 의견
Arranging Cows
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Arranging Cows