a bit of codeforces: Round #266 (Div. 2)

Problem C - Number of Ways

Problem Statement:
C. Number of Ways

Summary:
Find the number of ways to divide sequence into 3 segments such that each segment contain the same total sum

Solution:
Use 1D Array Sum sum[i] which forms the cumulative sum table. Then we are only interested in elements with values \( u = \frac{ \text{sum[n]} }{3} \) and \( v = \frac{2( \text{sum[n]} ) }{3} \). Then we compute count[i], in which if sum[i] == v, then count[i] is the number of elements up to before element i which is equal to u. Answer will be the sum of all count[i].



Problem D - Increase Sequence

Problem Statement:
D. Increase Sequence

Summary:
Given a[i], and operation [l, r] that increases a[i] in [l, r] by 1, find the number of ways such a set of operations can be carried out to make all a[i] = H, such that for any two [l, r] and [m, n], \(l \neq m\) and \(r \neq n\).

Solution
The problem is solvable using DP, but choosing the important parameters is not as obvious (or not obvious at all to me). Firstly, the approach is by choosing what to do at each element i. This will depend on the number of open segments (open brackets, open interval) by the time we reach point i. Now if we want to close a segment, we can arbitrarily choose any segments we want, and the choice of segment we close does not matter which can be proven using the following swap argument:
Given indexes \(L, L'\) and \(R, R'\) where both \(R, R'\) come later after \(L, L'\). Then the combination of segments \(L,R\) and \(L',R'\) modify the underlying element in exactly the same way as segments \(L, R'\) and \(L', R\).
To solve the problem, we maintain 2 parameter (i,j) where i is the i-th element, and j is the number of open segments by the time we reach i. This means that we have the following choice at i:
1. Close any of the j open segment
2. Close any of the j open segment, and immediately open a new segment
3. Open a new segment
4. Open a new segment and immediately close it
5. Do nothing, and continue
The applicability of each case depends on a[i] + j and what we can do so that it is equal to H. Below is a top-down DP implementation. A more concise, cool, and faster bottom-up DP can also be written but haven't got the strength to do so.

typedef long long Long;
Long MOD = (int) 1e9 + 7;
Long a[2003];
Long dp[2003][2003];
Long H;
int N;
 
Long rec(int i, int j){
    if(j < 0) return 0;
    if(i == N && j != 0) return 0;
    if(i == N && j == 0) return 1;
    if(a[i] + j > H || a[i] + j + 1 < H) return 0;
    if(dp[i][j] != -1) return dp[i][j];
    Long ret = 0;
    if( a[i] + j == H ){
        // close a bracket
        ret += j * rec(i+1, j-1);
        ret %= MOD;
        // skip
        ret += rec(i+1, j);
        ret %= MOD;
    } else if( a[i] + j + 1 == H ){
        // close and open
        ret += j * rec(i+1, j);
        ret %= MOD;
        // open
        ret += rec(i+1, j+1);
        ret %= MOD;
        // open and close
        ret += rec(i+1, j);
        ret %= MOD;
    }
    dp[i][j] = ret;
    return ret;
}