USACO 2026 US Open

Problem 1. Arranging Cows


Contest has ended.

Log in to allow submissions in analysis mode


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:

  1. The size of the range is even.
  2. The first half of the range consists of one character (either $0$ or $1$), and the second half contains the opposite character
  3. Either $l = 1$ or $s_{l-1} \neq s_l$
  4. 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$.

INPUT FORMAT (input arrives from the terminal / stdin):

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<l_i<10^9$), the lengths of maximal consecutive blocks of equal characters in $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$.

OUTPUT FORMAT (print output to the terminal / stdout):

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$.

SAMPLE INPUT:

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 1

SAMPLE OUTPUT:

1 1
0 1
0 1
-1 0
2 1
-1 0
4 7
3 1
4 1

Here is the sequence of two operations for the fifth testcase: $010110 \to 100110 \to 111000.$

SAMPLE INPUT:

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 1

SAMPLE OUTPUT:

0 1
1 1
2 1
3 3
4 9

In 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

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

Contest has ended. No further submissions allowed.