USACO 2025 US Open Contest, Platinum
Problem 2. Lazy Sort
Contest has ended.
Log in to allow submissions in analysis mode
Farmer John has $N$ cows ($2 \leq N \leq 5\cdot 10^6$) and is attempting to get them to sort a non-negative integer array $A$ of length $N$ by relying on their laziness. He has a lot of heavy boxes so he lines the cows up one behind another, where cow $i+1$ is behind cow $i$, and gives $a_i$ boxes to cow $i$ ($0\le a_i$).
Cows are inherently lazy so they always look to pass their work off to someone else. From cow $1$ to $N-1$ in order, each cow looks to the cow behind them. If cow $i$ has strictly more boxes than cow $i+1$, cow $i$ thinks this is "unfair" and gives one of its boxes to cow $i+1$. This process repeats until every cow is satisfied.
Farmer John will then note the number of boxes $b_i$ that each cow $i$ is holding and create an array $B$ out of these values. If $B = sorted(A)$, then Farmer John will be happy. Unfortunately, Farmer John forgot all but $Q$ values ($2 \leq Q \leq \min(N, 100)$) in $A$. Luckily, those values include the number of boxes he was going to give to the first and last cow. Each value that FJ remembers is given in the form $c_i \; v_i$ representing that $a_{c_i}=v_i$ ($1 \leq c_i \leq N$, $1\le v_i\le 10^9$). Determine the number of different ways the missing values can be filled in so that he will be happy mod $10^9+7$.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains two space-separated integers $N$ and $Q$ representing the number of cows and queries respectively.The next $Q$ lines contain two space separated integers $c_i \; v_i$ representing that cow $c_i$ initially holds $v_i$ boxes. It is guaranteed that $c_1 = 1$, $c_Q = N$, and $c_i < c_{i+1}$ (the order of the cows is strictly increasing).
OUTPUT FORMAT (print output to the terminal / stdout):
Print the number of different ways modulo $10^9+7$ that values $a_i$ can be assigned such that Farmer John will be happy after the cows perform the lazy sort. It is guaranteed that there will be at least one valid assignment.SAMPLE INPUT:
3 2 1 3 3 2
SAMPLE OUTPUT:
2In this example, FJ remembers the values at the ends of the array. The arrays $[3,2,2]$ and $[3,3,2]$ are the valid arrays that will make FJ happy at the end of the lazy sorting.
SAMPLE INPUT:
6 3 1 1 3 3 6 5
SAMPLE OUTPUT:
89
SCORING:
- Inputs 3-4: $N,v_i\le 100$
- Inputs 5-6: $N\le 100$ and $v_i \leq 10^6$
- Inputs 7-9: $N \leq 2\cdot 10^5$ and $v_i \le 10^6$
- Inputs 10-12: $N \leq 2\cdot 10^5$
- Inputs 13-15: No additional constraints.
Problem credits: Suhas Nagar