DP #11 Combinatorics DP

B. Mashmokh and ACM

Problem Statement: here

Solution:

We are asked to find out the number of sequences. The dp which we will use to construct the solution is 2D. Given the constraints, 2D dp will pass it.

Let dp[i][j] denote the number of sequences that are of length i and whose last element is j.

Since all the numbers are between 1 and n, we are having O(n*k) space complexity.

The DP transition will be:

dp[i][j] = ∑ dp[i-1][d] where d | j. 

So, we saw that if d divides  j, then dp[i-1][d] will add to dp[i][j]. In general, all multiples of d, which are at most n, will need dp[i-1][d] to be added to their answer.

So, to fast our solution fro O(n*k*sqrt(n)), we can use the harmonic sum complexity of O(nlogn).

The code

ll dp[2005][2005]; void solve() { ll n,k; cin >> n >> k; clr(dp,0); rep(i,1,n+1) dp[1][i] = 1; rep(len,2,k+1){ rep(i,1,n+1){ for(int j=i;j<=n;j+=i){ dp[len][i] = (dp[len][i] + dp[len-1][j])%M1; } } } ll ans = 0; rep(i,1,n+1) ans = (ans + dp[k][i])%M1; cout << ans; }

Segment Trees #4 Segment Tree on Rooted Tree: Point Queries + DP

JosephLand Problem Code: JTREE    

DP + Segment Tree

Problem Statement: here

The problem, in short, says: You have a tree with edges directed towards the root and nodes having some tickets. Each ticket allows you to move k units forward to your capital with a cost w. 

We need to answer queries which ask us for a minimum cost of traveling from node x.

This problem is tricky because of the larger constraints on the values of N, M, and Q. This is a problem of the type where you use Segment Trees as an optimization technique. 

Approach:

Let us say, we are at node x in our tree and we wish to get the minimum possible cost to travel to node 1(the capital city). This node is at depth H. So, it has H-1 nodes in its path. 

Let us break the problem into a simple version:
We want to decide which ticket is the best option among the available tickets at that node.
We will keep track of the minimum possible cost from a node in the dp[node].
We can use the recurrence for calculating the minimum possible cost: THIS IS A PSEUDO CODE.

for(ticket : all tickets){ //Iterate over all tickets available at node X cost = ticket.cost; k = ticket.k; for(nodes:nodes_in_path_of_X_upto_k_distance){ dp[X] = min(dp[X],dp[nodes] + cost); } }

Here we are iterating over all possible tickets at node X and then iterating over all the nodes up to depth k above it and taking the minimum. This makes the complexity of code O(Q + N*M)

But, we can heavily optimize our code if we use segment trees in finding out the minimum value up to the depth k above it. We can answer the query in logN time and reduce the overall complexity to 

O(Q + M*logN) which will pass easily.

How to use Segment Trees? 

We will apply dfs from the root node. Each time we iterate over all possible tickets, we can use query function to know the minimum possible value above k depths. We will build the segment tree on the depth. Once, we finish iterating a particular subtree, i.e that node and dfs over all it's children, we will update the depth to infinite so that it does not affect the answer for other branches of my tree.

Initially, we have not started iteration on any nodes, so the answer of dp[x] will be infinite and tree[ind] will also be infinite.  So, we don't need to build a tree here, because all values are initially infinite.

Now, dp[1] will be zero. Because we don't need any cost to visit node 1 if we are at node 1 itself.

So, we will also update the tree with dp[1] value. Note that the depth of node 1 is 0. 

The code:

ll N,m; vector<ll> adj[100005]; vector<pll> tickets[100005]; ll tree[400025]; ll dp[100005]; void update(ll ind, ll l, ll r, ll t, ll val){ if (t < l || t > r){ return; } if (l == r){ tree[ind] = val; return; } ll mid = (l+r)/2; update(2*ind,l,mid,t,val); update(2*ind+1,mid+1,r,t,val); tree[ind] = min(tree[2*ind],tree[2*ind+1]); } ll query(ll ind, ll l, ll r, ll qs, ll qe){ if (qe < l || qs > r){ return INF; } if (l >= qs && r <= qe){ return tree[ind]; } ll mid = (l+r)/2; return min(query(2*ind,l,mid,qs,qe),query(2*ind+1,mid+1,r,qs,qe)); } void dfs(ll node, ll depth){ for(auto i:tickets[node]){ ll k = i.F; ll w = i.S; dp[node] = min(dp[node],query(1,0,N,max((1ll)*0,depth-k),depth)+w); } update(1,0,N,depth,dp[node]); for(ll child:adj[node]){ dfs(child,depth+1); } update(1,0,N,depth,INF); } void solve() { cin >> N >> m; rep(i,0,N-1){ ll a,b; cin >> a >> b; adj[b].PB(a); } rep(i,0,m){ ll v,d,w; cin >> v >> d >> w; tickets[v].PB({d,w}); } rep(i,0,400025) tree[i] = INF; rep(i,0,100005) dp[i] = INF; dp[1] = 0; update(1,0,N,0,0); dfs(1,0); ll q; cin >> q; rep(i,0,q){ ll node; cin >> node; cout << dp[node] << endl; } } int32_t main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1; // cin>>t; test(t){ solve(); } return 0; }

DP #10 Indian National Olympiad Problem

Calvin's Game Problem Code: INOI1301 (Codechef)

Problem Statement: here

Solution: 

Let me make the question clear first. 

You first start with the forward phase, in which you move either zero or more moves.

Once you terminate your forward phase, you start your backward phase and you have to reach cell 1.

Approach: For moving forward, let us keep a dp array as forward_dp. 

For each index > k, we can use the recurrence dp[ind] = a[ind] + max(dp[ind-1],dp[ind-2])

This is easy because for each position, you can either jump one and reach it, or jump 2 and reach it.

Once, we have terminated our forward phase, we now need to return to cell 1. Returning from any index to index 1,  is same as going from cell 1 to that particular index. So, we keep a backward_dp array. 

Base case : backward_dp[1] = a[1]

backward_dp[2] = a[1]+a[2], because you have to ultimately reach cell 1.

Then, we can use the above recurrence and find out the values.

Once both the dp tables are constructed, we can start iterating from index k to the last index and update the maximum ans considering the current index as the last cell of forward phase and beginning of the backward phase. 

ans = max(ans, forward_dp[ind] + backward_dp[ind] - a[ind])

we are subtracting a[ind] because it was added twice, one for each dp computation.

The code:

void solve() { ll n,k; cin >> n >> k; ll a[n+1]; rep(i,1,n+1) cin >> a[i]; ll forward_dp[n+1] = {}; ll backward_dp[n+1] = {}; ll ans = INT_MIN; backward_dp[1] = a[1]; backward_dp[2] = a[1] + a[2]; rep(i,1,n+1){ if (i > k) forward_dp[i] = a[i] + max(forward_dp[i-1],forward_dp[i-2]); if (i > 2) backward_dp[i] = a[i] + max(backward_dp[i-1],backward_dp[i-2]); if (i >= k) ans = max(ans,forward_dp[i] + backward_dp[i] - a[i]); } cout << ans; }

DP #9 Largest square formed in a matrix

Maximal Square

Problem Statement: here

Solution:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0 (credits : Leetcode)

We want to count the number of one's in the maximum square sub matrix of given matrix. We can treat the index [i][j] as the ending point of our square and look at the maximumm square submatrix I can create. Let us call dp[i][j] the maximum size submatrix when [i,j] is the end point. 

We can compute dp[i][j] as: dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]) + 1;

What's that and how does it come?? So, we want to create a square matrix with [i,j] as the ending index, dp[i-1][j] denotes the maximum sub-matrix size ending at [i-1,j]. Similarly for other two. For my current index, let us say x is the answer. That means, I can construct a square of side x which ends at [i,j]. For a square of side x, we must have it's length size, width size and diagnol size as well exactly equal to x. When we take min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]) we are actually asking for the maximum side I can take and add 1 to it. Inclusion of dp[i-1][j] gives the horizontal side of square, dp[i][j-1] gives the vertical side of square and dp[i-1][j-1] gives the diagonal of square. When taken min of this 3, we get the side for our current possible square.

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if (n == 0) return 0;
        int m = matrix[0].size();
        int dp[n][m];
        for(int i=0;i<n;i++) dp[i][0] = matrix[i][0]-'0';
        for(int j=0;j<m;j++) dp[0][j] = matrix[0][j]-'0';
        int mx = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if (i==0 || j==0){
                    mx = max(mx,dp[i][j]);
                    continue;
                }
                if (matrix[i][j] == '0'){
                    dp[i][j]  = 0;
                }
                else{
                    dp[i][j] = min(dp[i-1][j],min(dp[i-1][j-1],dp[i][j-1]))+1;
                    mx = max(mx,dp[i][j]);
                }
            }
        }
        return mx*mx;
    }
};

DP #8 Minimum sum partition

Minimum Sum Partition

Problem Statement: here

Solution:

We saw in the last question DP #7, how we can create a dp to get equal partition. Here, we gonna use that to answer for the absolute minimum difference. Since we know that after the dp table is computed, if dp[sum] =  true, then we can construct that sum using any of the subset. We also know the total sum, so the difference can be computed easily.

Implementation:

#include<bits/stdc++.h> using namespace std; int main(){ int t; cin >> t; while(t--){ int n; cin >> n; int a[n]; int ts = 0; for(int i=0;i<n;i++){ cin >> a[i]; ts += a[i]; } bool dp[ts+1]; memset(dp,0,sizeof(dp)); dp[0] = 1; for(int i=1;i<=n;i++){ for(int j=ts;j>=a[i-1];j--){ dp[j] = (dp[j] || dp[j-a[i-1]]); } } int ans = INT_MAX; for(int i=0;i<=ts;i++){ if (dp[i]) ans = min(ans,abs(ts - 2*i)); } cout << ans << endl; } }

DP #7 Partition Equal Subset Sum

Partition Equal Subset Sum

Problem Statement: here

Solution: 

Firstly, if the total sum is odd, we can simply return false.

Also, note that this problem is again a classic knapsack problem. We saw in CF #637D as well. Here we are given a target sum and are asked to pick those elements who sum up exactly to target sum.

So, we will maintain a 2D dp array dp[i][j] will denote true if it possible to generate a sum j using any of the first i integers. 

Transition : dp[i][j] = dp[i-1][j] || dp[i-1][j-a[i]] 

Explaination: If we know the answer for i-1 indices, then for ith index it becomes easy to understand. We can either leave the element at current index for contribution to current subset sum or we can use it. If we leave it, then it becomes the responsibility of first i-1 indices to gather the sum j. we know it is nothing but equal to dp[i-1][j]. If we decide to pick the current element, it becomes dp[i-1][j-a[i]] because to get sum of j, now we have a[i] contribution from current index, so we need j-a[i] sum from elements up to previous index.

Base condition : dp[0][0] = true as it is always possible to get zero sum using zero elements.

Implementation:

class Solution { public: bool canPartition(vector<int>& a) { int sum = 0; for(int i: a) sum += i; if (sum&1) return 0; sum /=2; bool dp[a.size()+1][sum+1]; memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i=1;i<=a.size();i++){ for(int j=1;j<=sum;j++){ if(j >= a[i-1]) dp[i][j] = (dp[i-1][j] || dp[i-1][j-a[i-1]]); else dp[i][j] = dp[i-1][j]; } } return dp[a.size()][sum]; } };

Can we optimize it??

Yes, we can!

We do not need 2 dimensions if we watch carefully, our dp is depending only on the previous state and no more information from the past is required to construct the solution for present. We can reduce it to one dimension with a bit of care. The approach is similar to coin change problem for this case.

class Solution { public: bool canPartition(vector<int>& a) { int sum = 0; for(int i: a) sum += i; if (sum&1) return 0; sum /=2; bool dp[sum+1]; memset(dp,0,sizeof(dp)); dp[0] = 1; for(int i=1;i<=a.size();i++){ for(int j=sum;j>=a[i-1];j--){ dp[j] = (dp[j] || dp[j-a[i-1]]); } } return dp[sum]; } };

DP #6 Inversions in Permutations

DP+Binary Search+Ordered Set

Inversions in Permutations

Problem Statement: here

Solution:

The editorial is good enough, I would suggest you to read after this one.

So, some parts are taken from editorial itself.

$N\le 500$
$R \leq 200,000$
$K\leq 10^{18}$
$Q \leq 2000$

$Here\; each\; different\; test\; case\; is\; a\; different\; query\; which\; we\; are\; asking.$

$So,\; we\; want\; to\; find\; the\; Kth\; lexicographically\; smallest\; permutation\; using\; [1,N]\; numbers.$

Preprocessing

$We\; will\; build\; 2d\; DP\; table,\; which\; will\; store\; the\; number\; of\; permutations.$

$More\; formally,\; dp[i][j]\; will\; store\; the\; number\; of\; permutations\; using\; numbers\; in\; the\; range$

$[1,i]$ and having exactly j inversions. We will compute this for all i in range [1,500].

Here the value 500 is because maximum value of N is 500.

Another critical observation is that what is the maximum number of inversions I 

can generate using the [1,N] numbers. So, the only permutation with zero 

inversion is: 1 2 3 4 5 6 7 8 9...................N

So, if we move any number from its index to any index below it, it will be an
inversion.More formally, for all indices j, j<i, we have inversions if we swap the
elements of the permutation with zero inversions. 

So, any index i will give at max (i-1) inversions, because it has (i-1) indices behind. 

If, we consider zero based indexing, (i-1) becomes i.

So, total number of inversions is summation i, where i varies from 0 to n-1.

So, for any given i in our dp table, we can have at max i*(i-1)/2 inversions, and that

will be the size of second parameter. 

Constructing the DP table:

Base case : for exactly  zero inversions, the count is 1.

For exactly, the maximum number of inversions, the permutation will become sorted

in decreasing order, and the count is 1 for that case as well.

For having exactly j inversions, we need to think how we can compute it efficiently.

dp[i][j] -> we want count of those permutations where we are using [1,i] numbers 
and exactly j inversions.

dp[n][r]=k=1∑min(n,r+1)​dp[n−1][r−(k−1)] 

This is the recurrence relation we have used. 

Let's understand how does it come. So,we know if we keep any element on the

first position, it will contribute (element - 1) inversions. For, example , if any 

permutation starts with 3, we are sure it has at least 2 inversions, because 1and 2 will 

come somewhere in this sequence and they will form inversion pair with 3.

So basically, we are trying to keep every possible element, let's say k, on first place, 

once we fix that first place, we are now left with a sequence of i-1 integers and 

j - (k-1) inversions. 

One thing to note is that inversions are ordinal. So, which element I am placing 
in front will not decide anything except the amount of inversions it has already done.

So, my k  can vary from 1 to i in this case. But, wait we also want to make sure that 

j - (k-1) does not go negative, What does that mean ?? 

For example, we have i = 6, j = 3. So, for obvious reasons, we cannot place anything 

above 4 in the first place, because if we place 5, it has already done 4 inversions, and

we need only 3 inversions. So, at max my k value should be r+1. So, we take 
minimum of (n,r+1) and calculate the inversion table. 

That was exciting, right?!!

The author's code uptill this part is:

#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

ordered_set; #define ll long long #define siz(i) ((i) * ((i) - 1) / 2) const ll INF = 1e18, N = 501; vector<ll> dp[N]; inline ll get_sum(int idx, int l, int r){ l = max(l, 0); r = min(r, siz(idx)); ll sum = 0; for(int i = l; i <= r; i++){ sum += dp[idx][i]; if(sum >= INF) return INF; } return sum; } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); for(int i = 1; i < N; i++) dp[i].resize(siz(i) + 1); for(int i = 1; i < N; i++){ int s = siz(i); dp[i][0] = dp[i][s] = 1; for(int j = 1; j <= s / 2; j++) dp[i][j] = dp[i][s - j] = get_sum(i - 1, j - i + 1, j); } }

Rest Part - I will continue with this post ahead!!

CF #637D

D. Nastya and Scoreboard

Problem Statement: here

Solution

This question is a classic example of the knapsack problem, where you need to choose exactly k number of items. So, we can say it as a derived knapsack problem. 

We will solve it using 2d DP.

dp[i][j] -> where it means using the last i positions and j sticks in total, can we get a solution, if yes then it should be as large number as possible.

The dp transition  will be :

You loop through the last position to first position:

Inside this loop, you loop for the possible value of sticks used from 0 to k, 

Inside this loop, you loop from digit 9 to 0.

we can create a function separately, which can return us the total number of sticks i can use to convert the ith string into given digit. If the function results -1, then we cannot convert it and we simply continue. Also, if the cost exceeds the possible value of sticks I am using (by variable j in my code), even then I continue, because it is not possible to construct the number. 

On the other hand, if I get a valid cost  which is less than or equal to the current sticks I have in hand,

I need to check, if I use this much of sticks, was it possible to construct the solution from next up index to last index using the remaining sticks (remember I was looping from behind). 

So, my dp transition in this case becomes : dp[i][j] = digit, only if dp[i+1][j-cost] is not equal to -1, means I have a digit stored at it,  means It is possible to construct the solution. Once, I get a possible digit, I will break the loop, because I need to place maximum possible digit each time, so I don't need to check for each and every digit. 

Once this dp table is filled. 

If my value of dp[1][k] is not -1 then solution exist. 

Why dp[1][k], because I was looping backwards and from n to 1, If i can use exactly k sticks then there must be a digit at dp[1][k], which will tell me that I am the maximum possible digit you can use to construct your solution, so if it exist, i use it and then using the cost to convert a[1] to that digit, I can determine my next digit, simply by doing dp[i+1][k] where I update my k with k -= cost of conversion. 

So, at the end, it makes sense to loop backwards, because I want to place the maximum digit at first place,So I need to know if while doing so, is it possible to construct solution from remaining sticks and next position. 

Nice question on the derived knapsack.

Implementation:

vector<string> digits = { "1110111", "0010010", "1011101",
"1011011", "0111010", "1101011", "1101111", "1010010",
"1111111", "1111011" };

ll check(string d1, string d2){
    ll cost = 0;
    rep(i,0,7){
        if (d1[i] == '1' and d2[i] == '0'){
            return -1;
        }
        cost += (d1[i] != d2[i]);
    }
    return cost;
}

void solve(){ ll n,k; cin >> n >> k; string a[n+1]; rep(i,1,n+1) cin >> a[i]; int dp[n+5][k+5]; clr(dp,-1); dp[n+1][0] = 0; repp(i,n+1,1){ rep(j,0,k+1){ repp(d,10,0){ ll cost = check(a[i],digits[d]); if (cost == -1 || cost > j){ continue; } else{ if (dp[i+1][j-cost] != -1){ dp[i][j] = d; break; } } } } } if (dp[1][k] == -1){ cout << -1 << endl; return; } string ans; rep(i,1,n+1){ int dig = dp[i][k]; ans += to_string(dig); k -= check(a[i],digits[dig]); } cout << ans << endl; }

DP #5 : Russian Doll Envelopes

DP #5: Russian Doll Envelopes

Problem Statement: here

Solution:

This is a follow-up question from DP #4: Box stacking problem. This is slightly easy variant but involves a similar concept. I am not going to explain the DP solution which takes O(n^2) time. 

The implementation is easy and straightforward as in Box stacking Problem.

Code: 

class Solution { public: int maxEnvelopes(vector<vector<int>>& a) { sort(begin(a), end(a), greater<vector<int>>()); int dp[a.size()+5]; int mx = 0; for(int i=0;i<a.size();i++){ dp[i+1] = 1; for(int j=0;j<i;j++){ if (a[j][0] > a[i][0] and a[j][1] > a[i][1]){ dp[i+1] = max(dp[i+1],dp[j+1]+1); } } mx = max(mx,dp[i+1]); } return mx; }

};

What next -?

Try out the O(NlogN) version of above code. We are simply doing the LIS and

that can be done in O(NLogN).

DP #4 Box Stacking Problem

DP #4: Box Stacking Problem

Problem Statement: here

Solution : 

A box can be placed on top of another only if both it’s base dimensions width and depth are less than a box on which it stacked on. There is no restriction on height, a tall box can be placed on a short box.

The point is that we can rotate the box, and change the (l,b,h) configuration and we can treat each box as 3 different boxes because we can use multiple instances of the given box. 

Another constraint is that we can place a box on top of another box only if the width of the top box < width of the bottom box and similarly for depth. So, we first need to construct 3*n boxes and then sort them on the basis of the base area and apply LIS for height. 

Implementation: 

int Solution::solve(vector<vector<int> > &A) { int n = A.size(); vector<pair<int,pair<int,int>>> v; for(int i = 0; i< n; i++){ int l,b,h; l = A[i][0]; b = A[i][1]; h = A[i][2]; v.push_back({l,{max(b,h),min(b,h)}}); v.push_back({b,{max(l,h),min(l,h)}}); v.push_back({h,{max(b,l),min(b,l)}}); } sort(begin(v),end(v),[](pair<int,pair<int,int>> a, pair<int,pair<int,int>> b){ return ((long long int)a.second.first*(long long int)a.second.second) >=

((long long int)b.second.first*(long long int)b.second.second); }); int dp[3*n + 5]; int mxheight = -1; for(int i = 0; i< v.size(); i++){ dp[i] = v[i].first; for(int j = 0; j< i; j++){ if(v[j].second.first > v[i].second.first and v[j].second.second >

v[i].second.second){ dp[i] = max(dp[i],dp[j]+v[i].first); } } mxheight = max(mxheight, dp[i]); } return mxheight; }

Try next : https://leetcode.com/problems/russian-doll-envelopes/

I will post solution to this question later on!

DP #3 : Count Distinct Subsequences

DP #3 Count Distinct Subsequences

Problem Statement - here

Solution - 

I am going to give the bottom-up solution for most of the DP problem series. Figuring out the top-down solution is the reader's duty. It is easy sometimes to code the top-down recurrence relation.

Coming to the problem statement, We want to find out the number of distinct subsequences. Let's create a dp array, dp[i] where dp[i] denotes the count of subsequences from index 0 to i inclusive.

So, if we know the i-1 index count of distinct subsequences, then if the s[i] is not encountered uptill now, we can simply double the dp[i-1], because to each of the dp[i-1] strings, we can generate new dp[i-1] strings by adding this character s[i]. 

But, if s[i] is already encountered for some index j < i. Then we need to consider the repetitions.

For example - "DEFABCA" we can create subsequence "DEA" using two different A, but both of them imply the same string "DEA". So,  we need to make sure that whenever we meet a character that is repeating, we subtract the count of subsequences formed in which s[j] was the last character. So, the transition becomes :

dp[i] = 2*dp[i-1] - dp[j-1] where j is the most recent index where it got repeated. 

So, basically, we are subtracting it because the dp[j-1] denotes the count of subsequences that ends at position j,  which has the same character as that of position i, so instead of ending at j, if they would have ended at index i, then it means the same thing in terms of the subsequence, so we don't need to count them twice. 

Code:

class Solution {

class Solution { public: int MOD = 1000000007; int distinctSubseqII(string s) { map<char,int> m; // Tracks last index of char int dp[s.size()+5]; dp[0] = 0; dp[1] = 1; m[s[0]] = 1; for(int i=1;i<s.size();++i){ dp[i+1] = (2*dp[i] + 1)%MOD; // + 1 because ith character alone can also

be answer. if (m[s[i]] > 0){ dp[i+1] = (dp[i+1] - dp[m[s[i]]-1] -1 + MOD)%MOD; } m[s[i]] = i+1; } return dp[s.size()]; } };

AtCoder Beginner Contest 163

E : Active Infants

Problem Statement - here

Solution :

To make ourselves clear, we can rearrange them in any order we like. So, it is clear that for every element we have to keep it as far as possible from its current position. But wait, our first priority should be the one who has maximum weight, because it contributes maximum to our happiness. So, we should sort the weights in decreasing order and then what?

Let's say we are at the ith index of our sorted weights, whose initial position is ind and its weight is w. We have already placed our (i-1) elements. These elements are either to the very start or the very end of our array. So, this ith element will either come in front or at back. Let's say we have already placed L elements to left and R elements to right, then L+R = i-1.

so the transitions are now very easy to write:

dp[L+1][R] = max(dp[L+1][R],dp[L][R]  + abs(L+1 - ind)*w)

dp[L][R+1] = max(dp[L][R],dp[L][R+1] + abs(n - R- ind)*w)

We can simply loop till i-1 assuming the current index as the number of elements placed to Left (L) first and calculate the first transition table and then assume it as #elements to the right (R) and calculate the second transition table. 

The Implemented Code:

ll dp[2005][2005] = {}; void solve() { ll n; cin>>n; pll a[n+1]; rep(i,1,n+1) cin >> a[i].F , a[i].S = i; sort(a+1,a+n+1,greater<pll>()); rep(i,1,n+1){ rep(j,0,i){ ll L = j; ll R = i-1-j; dp[L+1][R] = max( dp[L+1][R], dp[L][R] + abs(L+1 - a[i].S)*a[i].F ); R = j; L = i-1-j; dp[L][R+1] = max( dp[L][R+1], dp[L][R] + abs(n - R - a[i].S)*a[i].F ); } } ll ans = 0; rep(i,0,n+1){ ans = max(ans,dp[i][n-i]); } cout << ans << endl; }

DP #2 : TopCoder SRM 782

DIV 2C - Empty The Box

Problem Statement - here

Solution: We need to find the expected value of the total penalty. The expected value of a penalty score is nothing but - 

 E(X)= ∑ xp(x). here X denotes all the possible subsets of [1....T] whose sum equals X. 

Let's randomly choose any given subset of [1.....T] whose sum equals X. Now, since we have 2 D-dice, we can easily calculate the probability of getting sum as X. 

For example: if X = 12 and the value of D is  6, then the probability of getting 12 when 2 dice (D = 6) are thrown is nothing but 1/36.  

So, once we loop over all the possible subsets whose sum equals X, we can easily calculate X.P(X), once we do that we can add it to our expected value of X. 

The next thing to consider is - it is said in the question that we can only choose a particular subset (whose sum equals X) if the tokens are available to us. So, to ensure this we will loop over all the possible subsets of T. 

Concepts Involved - BITMASKING, DYNAMIC PROGRAMMING.

We know the value of T is at most 50. We can easily mask each subset of T in O(2^T) time. 

Given this subset - consider it as the set of available tokens on the desk. We can compute what is the value of the sum of tokens which are available (this corresponds to the set bits of our number). In the worst case, it might happen that we could not pick up any tokens in the subset. In this case, the value of X becomes this total and we will add X.P(X) to our expected value table. Also, it may happen that we can pick up some tokens from this subset and then the remaining subset reduces to a lesser value whose answer (best response) is already computed. So we can take the minimum of all possible options and update the answer for the current subset of available tokens.

Implementation : 

we will precompute the probability of getting the sum as X, given the dice value D.

Here is the snippet for that part - 

double* rollprob = new double[2*D+1](); for(int i = 1; i<=D;++i){ for (int j = 1; j<=D;++j){ rollprob[i+j] += 1./(D*D); } }

Let's create the DP array which will store the minimum expected value for each subset of T. 

double* dp = new double[1<<T]();

Now let's loop over all the possible subsets of tokens in the range [1......T]. In this - we will loop from the subset which has no tokens in it and will gradually increase to the subset which has all the tokens in it. 

for(long long int subset = 0; subset<(1<<T);++subset){

}

Once we have the subset, we will first calculate the value of tokens present in it - we can create a separate function that will give us this value.

double Calculate(long long int subset){ double t = 1,sum=0; while(subset > 0){ if (subset&1) sum += t; subset >>=1; t++; } return sum; }

Once our function is created, we will use it to compute the value of our subset. We will try to find another smaller subset that can be picked up by throwing a dice. For example, suppose our subset has [1,3,5,7] and it's sum = 16. If I can get a score of 9,4,etc.. I can remove [1,3,5] or [1.3] respectively. So that's what I am searching for. And, what will I remove then? This will be the minimum of what is remaining after i remove each. So, I will compute the X(random value) as minimum at each step and finally update it.

Complete Code : 

class EmptyTheBox{ public: double Calculate(long long int subset){ double t = 1,sum=0; while(subset > 0){ if (subset&1) sum += t; subset >>=1; t++; } return sum; } double minExpectedPenalty(int D, int T){ double* rollprob = new double[2*D+1](); for(int i = 1; i<=D;++i){ for (int j = 1; j<=D;++j){ rollprob[i+j] += 1./(D*D); } } int excess = 0; while(T > 2*D) excess+=T,T--; T = min(2*D,T); double* dp = new double[1<<T](); for(long long int subset = 0; subset<(1<<T);++subset){ for (int roll = 2; roll <= 2*D; ++roll){ double X = Calculate(subset); for(long long int reduceset = 1;reduceset < (1<<T);++reduceset){   if (((subset&reduceset) == reduceset) && (Calculate(reduceset) == roll)){ X = min(X,dp[subset^reduceset]); } } dp[subset] += rollprob[roll]*X; } } return (dp[(1<<T)-1] + excess); } };

Code Link - https://ideone.com/T0hqih

DP #1 : AtCoder Beginner Contest 162

ABC #162 F - Select Half

Problem Statement - here

Solution -> We will be using 1d DP to solve the problem. We will make the prefix sum array for odd positions beforehand. Let's denote it as ps[ ]. (eg -> ps[5] = ps[3] + a[5])

So, let's break the problem into 2 halves ->

1. When the current index in consideration (i) is odd
2. When i is even.

Case 01 - When i is even:

We need to choose exactly i/2 elements.

SO, dp[i] = max(dp[i-2]+a[i],ps[i-1]).

Let's understand the above line -

I have 2 choices for the current index:

1. If i include current index in my answer, then the problem reduces to exactly i/2 - 1elements. This is nothing but (i-2)/2. So dp[i-2] comes into play.
2. If I decide to leave my current index. Problem reduces to finding max of exactly i/2 elements in the range of [0,i-1] where (i-1)/2 < i/2. And also, there is exactly one sequence, that can give i/2 elements. This is 1,3,5,7,....i-1. So it is nothing but prefix sum of all odd positions up to i-1.

Case 02 - When i is odd:

This case is simple. Since i/2 is same as (i-1)/2, we can transform this as 

dp[i] = max(dp[i-1],a[i]+dp[i-2])

Let's understand this line.

dp[i-1] is fairly clear. It comes if I decide not to pick my current element. Then it is the same as a subproblem of size i-1. Because even in the subproblem of size i-1.  I need to pick exactly i/2 elements.

But, If I want to pick up my current element, the subproblem reduces to i-2. So a[i] + dp[i-2] comes into picture. This happens because, If i pick up an element, the problem reduces to exactly picking up i/2 - 1 more elements. This is nothing but (i-2)/2. So the problem reduces to dp[i-2].

Code - 

#include<bits/stdc++.h>

using namespace std;

#define ll                  long long int

#define endl                '\n'

#define rep(i,a,b)          for(ll i=a;i<b;i++)

void solve()

{

    ll n;

    cin>>n;

    ll a[n+1];

    rep(i,1,n+1) cin >> a[i];

    ll ps[n+1],dp[n+1];

    dp[0] = 0;dp[1] = 0;

    ps[1] = a[1];

    for(ll i=3;i<=n;i+=2) ps[i] = ps[i-2] + a[i];

    rep(i,2,n+1){

        if (i&1){

            dp[i] = max(dp[i-1],a[i]+dp[i-2]);

        }

        else{

            dp[i] = max(dp[i-2] + a[i],ps[i-1]);

        }

    }

    cout << dp[n] << endl;

}

int32_t main(){

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    solve();

    return 0;

}