STRCSE - Editorial

editorial
1

PROBLEM LINK:

TCPC - YET ANOTHER STAIRCASE PROBLEM

Author: Om Bindal
Editorialist: Om Bindal

DIFFICULTY:

MEDIUM

PREREQUISITES:

Distributive DP, Math

Problem Statement:

Count the number of ways to reach Nth cell. Chef is given K non intersecting segments [L_1,R_1], [L_2,R_2],..., [L_K,R_K]. K is less than or equal to 10. Let S be the union of all integers contained in these K segments. When Chef is on cell i, he can pick an integer d from S and move to cell i+d. Chef cannot move past Nth cell.

EXPLANATION:

First, the naivest solution is a Dynamic Programming (DP) where f_i ​:= the number of ways to go to Cell i, and check all the possible move for each i, but this needs a time complexity of \mathrm{O}(N^2)

Let us consider optimizing by making use of the fact that the ways of moving can be written as a sum of small number of segments (S=\cup [l_j,r_j] ). This can be solved either in so-called “distributing DP” or “receiving DP.” This time, let’s understand distributing DP.

Assume that we have already obtained the values until f_i ​. When transiting from i, for all d \in S, we want to add f_i to f_{i+d} .

Here, we want to use the fact that the difference of neighboring values of f changes at O(K) positions. Let a_i = f_{i} - f_{i-1}, then this can be optimized by performing the operations of a_{i + l_j} := a_{i + l_j} + f_i, a_{i + r_j + 1} := a_{i + r_j + 1} - f_i ​ for each j, and then restore f by f_i = f_{i-1} + a_i ​.

The total time complexity is \mathrm{O}(KN) .

Note that it is known that this problem can be solved in a total of \mathrm{O}(N \log N) time even when the transitions cannot be written as a sum of small number of segments.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h> 
using namespace std; 
#define ll long long
#define vi vector<int>
#define vpii vector<pair<int,int>>
#define pii pair<int,int>
#define ff first 
#define ss second
#define endl "\n"
#define print(x) cout<<x<<endl
#define printt(x,y) cout<<x<<" "<<y<<"\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define vvi vector<vector<int>>
#define sz(x) (int)x.size()
#define maxq priority_queue<int>
#define minq priority_queue<int,vector<int>,greater<int>>
const int M = 1e9 + 7;
const int N = 200005;

int32_t main() {
    int n;
    cin >> n;
    int k;
    cin >> k;
    vector<pii> ranges(k);
    for (auto &r : ranges)
        cin >> r.first >> r.second;
    sort(all(ranges));

    vector<ll> dp(n + 1, 0);
    vector<ll> sum(k, 0);
    dp[1] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < k; ++j) {
            dp[i] += sum[j];
            dp[i] %= M;
        }
        for (int j = 0; j < k; ++j) {
            if (i - ranges[j].first + 1 > 0) {
                sum[j] += dp[i - ranges[j].first + 1];
                sum[j] %= M;
            }
            if (i - ranges[j].second > 0) {
                sum[j] -= dp[i - ranges[j].second];
                sum[j] = (sum[j] + M) % M;
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}