Official Editorial

Implementation

C++

#include <cassert>
#include <iostream>
#include <vector>


const int MOD = 1e9 + 7;


long long pow(long long base, long long exp) {
	assert(exp >= 0);
	base %= MOD;
	long long res = 1;

Java

import java.io.*;


public class Bots {
	private static final int MOD = (int)Math.pow(10, 9) + 7;
	public static void main(String[] args) throws IOException {
		int max_moves = Integer.parseInt(
		    new BufferedReader(new InputStreamReader(System.in)).readLine());


		long total_states = 1;
		long curr_level = 1;

Python

Warning!

Due to Python's slow speed, the below code only passes all test cases if you submit with PyPy.

MOD = int(1e9) + 7




def mod_inv(n: int):
	return pow(n, MOD - 2, MOD)




max_moves = int(input())


total_states = 1

Solution 2

Let us first define a DP recurrence relation, with dp[b][r]\texttt{dp}[b][r] being the number of unique states where the blue bot has made bb moves and the red bot has made rr moves:

dp[b][r]=dp[b−1][r]+dp[b][r−1]\texttt{dp}[b][r]=\texttt{dp}[b - 1][r] + \texttt{dp}[b][r - 1]

It follows that the answer is the sum of all the elements in dp\texttt{dp}.

This is what dp\texttt{dp} might look like for n=4n=4:

1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
1 4 10 20 35
1 5 15 35 70

Note that these numbers are exactly the same as the ones in Pascal's triangle, only rotated a bit! These numbers form a rotated square of length n+1n+1 (henceforth referred to as xx), and we can express its sum as

∑i=0x−1∑j=ix+i−1(ji)\sum_{i=0}^{x-1} \sum_{j=i}^{x+i-1} {j \choose i}

Using the hockey stick identity, we see that this equals

∑i=0x−1(x+ii+1)=∑i=1x(x+i−1i)\begin{align*} &\sum_{i=0}^{x-1} {x+i \choose i+1}\\ =&\sum_{i=1}^{x} {x+i-1 \choose i} \end{align*}

We also know from the hockey stick identity that ∑i=0a(a+i−1i)=(2aa)\sum\limits_{i=0}^{a} {a+i-1 \choose i} = {2a \choose a}. Thus, we get that

∑i=1x(x+i−1i)=∑i=0x(x+i−1i)−(x+i−10)=(2xx)−1=(2n+2n+1)−1\begin{align*} &\sum_{i=1}^{x} {x+i-1 \choose i}\\ =&\sum_{i=0}^{x} {x+i-1 \choose i} - {x+i-1 \choose 0}\\ =&{2x \choose x} - 1\\ =&{2n+2 \choose n+1} - 1 \end{align*}

Implementation 2

Time Complexity: O(Nlog⁡MOD)\mathcal{O}(N \log MOD)

C++

#include <cassert>
#include <iostream>
#include <vector>


using std::cout;
using std::endl;
using std::pair;


const int MOD = 1e9 + 7;

Java

import java.io.*;


public class Bots {
	private static final int MOD = (int)Math.pow(10, 9) + 7;
	public static void main(String[] args) throws IOException {
		int maxMoves = Integer.parseInt(
		    new BufferedReader(new InputStreamReader(System.in)).readLine());


		int[] resBinom = new int[] {2 * maxMoves + 2, maxMoves + 1};
		long resNum = 1;

Python

Warning!

Due to Python's slow speed, the below code only passes all test cases if you submit with PyPy.

MOD = int(1e9) + 7




def mod_inv(n: int):
	return pow(n, MOD - 2, MOD)




max_moves = int(input())


res_binom = [2 * max_moves + 2, max_moves + 1]

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum