PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: rohan_217
Tester: wasd2401
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Dynamic programming
PROBLEM:
N monsters appear, one after another.
When the i-th monster appears, you’ll fight it immediately, even if others are alive.
When you defeat a monster, you’ll go back to fighting whichever monster you were fighting previously.
You just defeated the K'th monster. How many possible orders of defeating the remaining monsters exist?
EXPLANATION:
First off, we need to know where we stand.
When the K'th monster has been just defeated, which possible states can the monsters be in?
That is, which of them can be still alive (after having appeared), which of them are definitely defeated already, and which of them can have not appeared yet?
Answer
Clearly, monsters that haven’t appeared yet will form some suffix, i.e, will be x, x+1, \ldots, N for some x \gt K.
Then, you can observe that:
- Monsters K, K+1, \ldots, x-1 will definitely be defeated already, having appeared.
- Monsters 1, 2, 3, \ldots, K-1 can all be either alive or defeated; i.e, any subset of them can be alive and the remainder will be defeated.
This is not hard to see: at any point of time, you will be fighting the monster with highest index that has appeared and is still alive; so when the K'th monster is killed, it should be this monster - meaning nothing higher than it can remain alive.
Further, for monsters 1, 2, 3, \ldots, K-1, there’s always a sequence of moves that leaves any chosen subset alive: for each i = 1, 2, \ldots, K-1, let the i'th monster appear; defeat it if you need to otherwise just fight it without defeating it.
So, we have some subset S of the first K-1 monsters alive (of which we’ll be fighting the largest one), and the remaining monsters will be x, x+1, \ldots, N for some x \gt K.
Let’s fix both S and x, and try to compute the number of orders of defeating the remaining monsters.
There are two choices for what happens:
- Defeat the monster we’re currently fighting (say m), and move on to fighting the next alive smaller one.
- Or, monster x appears, and we switch to fighting it immediately.
Both choices clearly lead to different orders: in the first case, we start with m, while in the second, the first monster we defeat will definitely be something \geq x.
This means they both contribute separately to the answer.
Further, observe that the subset S itself doesn’t matter - only its size (because we only defeat the largest monster in it at any point anyway).
Similarly, only the number of monsters that haven’t appeared yet matters.
This leads to a somewhat natural recursive formulation for the process.
Let f(x, y) denote the number of orders if x monsters haven’t appeared yet, and y monsters are currently alive (of which we’ll be fighting the largest).
Then,
- If the largest alive monster is defeated before the next appears, we have f(x, y-1) orders.
- If the next monster appears first instead, we have f(x-1, y+1) orders.
So, quite simply, f(x, y) = f(x, y-1) + f(x-1, y+1).
Be careful about x = 0 and/or y = 0, in which case one or both transitions might not be possible.
You can take f(0, 0) = 1 as the base case.
Now, notice that 0 \leq x,y \leq 1000, so using dynamic programming you can simply precompute all the f(x, y) values and store them!
Then, for a given N and K:
- Fix x, the number of monsters that haven’t appeared yet. This is between 0 and N-K.
- Fix y, the numbers of monsters that are still alive. This is between 0 and K-1.
- For a fixed choice of y, you have \binom{K-1}{y} choices of subsets.
- For a fixed subset and x, there are f(x, y) orders.
So, the overall answer is
which is easily computed in \mathcal{O}(N^2) since f(x, y) has been precomputed.
TIME COMPLEXITY:
\mathcal{O}(N^2) per testcase.
CODE:
Tester's code (C++)
/*
* * * *** * *****
* * * * * * * *
* * * *** ***** *
* * * * * * * * *
* * * * * * **
*
* *
*****
* *
***** * *
_* *_
| * * * * | ***
|_* _ *_| * *
* * *
***** * **
* * ***
{===* *===}
* IS * ***
* IT * * *
* RATED?* *
* * * **
* * ***
* *
***** * *
* *
* *
* *
***
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define osl tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ld long double
#define forl(i, a, b) for(ll i = a; i < b; i++)
#define rofl(i, a, b) for(ll i = a; i > b; i--)
#define fors(i, a, b, c) for(ll i = a; i < b; i += c)
#define fora(x, v) for(auto x : v)
#define vl vector<ll>
#define vb vector<bool>
#define pub push_back
#define pob pop_back
#define fbo find_by_order
#define ook order_of_key
#define yesno(x) cout << ((x) ? "YES" : "NO")
#define all(v) v.begin(), v.end()
const ll N = 1e3 + 4;
const ll mod = 1e9 + 7;
// const ll mod = 998244353;
vl fact(N,1);
ll modinverse(ll a) {
ll m = mod, y = 0, x = 1;
while (a > 1) {
ll q = a / m;
ll t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) x += mod;
return x;
}
ll gcd(ll a, ll b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
bool poweroftwo(ll n) {
return !(n & (n - 1));
}
ll power(ll a, ll b, ll md = mod) {
ll product = 1;
a %= md;
while (b) {
if (b & 1) product = (product * a) % md;
a = (a * a) % md;
b /= 2;
}
return product % md;
}
ll barfi(ll n, ll r){
if(n<r || r<0) return 0;
ll p=modinverse(fact[r])*modinverse(fact[n-r]);
p%=mod;
return (p*fact[n])%mod;
}
void panipuri() {
ll n, m = 0, k = -1, c = 0, sum = 0, q = 0, ans = 0, p = 1;
string s;
bool ch = true;
cin >> n>>k;
vector<vl> dp(n,vl(n));
dp[0][0]=1;
forl(i,1,n){
c=0;
rofl(j,i,0){
c+=dp[i-1][j-1];
c%=mod;
dp[i][j]=c;
}
dp[i][0]=c;
// cout<<c<<' ';
}
forl(i,k-1,n){
forl(j,0,k){
c=j+n-1-i;
ans+=dp[c][j]*barfi(k-1,j);
ans%=mod;
}
}
cout<<ans;
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int laddu = 1;
cin >> laddu;
forl(i,1,N){
fact[i]=i*fact[i-1];
fact[i]%=mod;
}
forl(i, 1, laddu + 1) {
// cout << "Case #" << i << ": ";
panipuri();
cout << '\n';
}
}
Editorialist's code (Python)
mod = 10**9 + 7
N = 3005
C = [ [0 for _ in range(N)] for _ in range(N) ]
dp = [ [0 for _ in range(N)] for _ in range(N) ]
for i in range(N):
C[i][0] = 1
for j in range(1, i+1):
C[i][j] = (C[i-1][j] + C[i-1][j-1]) % mod
dp[0][0] = 1
for sm in range(1, N):
for x in reversed(range(sm+1)):
y = sm - x
if x > 0: dp[x][y] = dp[x-1][y]
if y > 0: dp[x][y] = (dp[x][y] + dp[x+1][y-1]) % mod
for _ in range(int(input())):
n, k = map(int, input().split())
ans = 0
for lt in range(k):
ways = C[k-1][lt]
for i in range(n-k+1):
ans = (ans + ways*dp[lt][i]) % mod
print(ans)