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; }

DSU #1 Dish Owner CodeChef

Dish Owner Problem Code: DISHOWN

Problem Statement: here

Solution: This is the first problem in the Disjoint Set Union series, so bare a small lecture from my side. Disjoint Set Union is a technique that allows us to deal with disjoint sets. We can solve problems involving disjoint sets. The two important functions of this data structure is:

1. Find(x) -> It will find the root node of my current component/set.
2. Union(x,y) -> It is used for uniting two disjoint sets. We can assign the root node of one set the parent of another, depending on SOME rules. Sometimes, it depends on the height of the subtree or rank or number of nodes in set or any other rule.

The code snippet uses the rank and path compression technique for DSU.

// DSU starts here.................. struct subset { ll parent; ll rank; }; ll find(struct subset subsets[], ll i) { // find root and make root as parent of i (path compression) if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } void Union(subset subsets[], ll x, ll y) { ll xroot = find(subsets, x); ll yroot = find(subsets, y); // Attach smaller rank tree under root of high rank tree // (Union by Rank) if (subsets[xroot].rank < subsets[yroot].rank) subsets[xroot].parent = yroot; else if (subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot; // If ranks are same, then make one as root and increment // its rank by one else { subsets[yroot].parent = xroot; subsets[xroot].rank++; } } //DSU ends here....................

The Approach for question: 

Initially, we can set the parent of ith dish the ith index itself, because ith chef owns it.

Then important observation is:

1. The root dish for ith chef is now set as the initial dish he had.
2. The important thing to note is, every chef will come forward with the dish of maximal score to fight and that dish is nothing but the initial dish only. Because if his initial dish is bigger than other dishes of other chefs, he is getting all of their dishes, but all dishes of other chefs are already smaller than his initial dish, otherwise another chef would have won. So, when we find the root of any disjoint set, we can check for the score on that dish and figure out which chef will win and assign accordingly.

The Code:

struct subset { ll parent; ll rank; }; ll find(struct subset subsets[], ll i) { // find root and make root as the parent of i (path compression) if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } void solve() { ll n; cin >> n; ll a[n+1]; rep(i,1,n+1) cin >> a[i]; subset myset[n+1]; rep(i,1,n+1){ myset[i].parent = i; myset[i].rank = 0; } ll m; cin >> m; rep(i,0,m){ ll r; cin >> r; if (r == 0){ ll x,y; cin >> x >> y; ll xroot = find(myset,x); ll yroot = find(myset,y); if(xroot == yroot) { cout<<"Invalid query!"<<endl; } if (a[xroot] < a[yroot]){ myset[xroot].parent = yroot; } else if (a[xroot] > a[yroot]){ myset[yroot].parent = xroot; } } else{ ll x; cin >> x; cout << find(myset,x) << endl; } } }

Segment Trees #7 Xenia and Bit Operations

D. Xenia and Bit Operations

Problem Statement: here

Solution: [EASY BUT DIFFERENT] 

This construction of segment trees is non-trivial.

So, as we have been told, each leaf will store the value of the array. But, remember, as what we always do to build our segment tree is perform the same nature of operation, like take max of child, or min or sum or diff or etc, here we need to check about the parity of depth. Based on parity. we will take either xor/or of their children. We know, the depth of our tree is n, because there are exactly 2^n leaf nodes. If we are at any depth d in our tree, nodes in this depth will be xor of children if the parity of n and d are same else we will take or.

The Code:

ll n,m; ll a[(1<<18) + 1]; ll seg[4*(1<<18) + 5]; void push(ll ind){ ll depth = (ll)log2(ind); if ((depth^n)&1) seg[ind] = seg[2*ind]|seg[2*ind+1]; else seg[ind] = seg[2*ind]^seg[2*ind+1]; } void build(ll ind, ll l, ll r){ if (l == r){ seg[ind] = a[l]; return; } ll mid = (l+r)/2; build(2*ind,l,mid); build(2*ind+1,mid+1,r); push(ind); } void update(ll ind, ll l, ll r , ll t, ll val){ if (t < l || t > r){ return; } if (l == r){ seg[ind] = val; return; } ll mid = (l+r)/2; update(2*ind,l,mid,t,val); update(2*ind+1,mid+1,r,t,val); push(ind); } void solve() { cin >> n >> m; rep(i,0,1<<n) cin >> a[i]; build(1,0,(1<<n) - 1); rep(i,0,m){ ll j,val; cin >> j >> val; update(1,0,(1<<n)-1,--j,val); cout << seg[1] << endl; } }

LIS #1 LIS on Trees

F - LIS on Tree

Problem Statement: here

Solution:

There is more than one way to solve this problem. We shall see two different implementations. 

The first implementation is an easy version and it uses LIS in O(nlogn) approach. We will apply dfs from the root node and insert each element as if we do it in a linear array. But, the only difference is, once the subtree query is finished, replace the old version for the next subtree.

The second implementation involves using segment trees to answer the LIS in O(nlogn) approach. I will include this approach and its brief explanation as to my next post in the series on segment trees.

So, stay tuned with it! 

To learn how to compute LIS in O(nlogn) check my this post

Using the Vector for LIS:  AC in 121mS

V(ll) adj[200005]; ll n,k; ll val[200005]; ll dp[200005]; V(ll) v; // declaring vector void dfs(ll node, ll parent){ ll rep = -1; auto it = lower_bound(all(v),val[node]); ll ind = it - v.begin(); if (it != v.end()) { rep = *it; *it = val[node]; } else v.PB(val[node]); dp[node] = v.size(); for(ll child:adj[node]){ if (child != parent){ dfs(child,node); } } if (rep != -1){ v[ind] = rep; } else{ v.pop_back(); } } void solve() { cin >> n; rep(i,1,n+1) cin >> val[i]; rep(i,0,n-1){ ll x,y; cin >> x >> y; adj[x].PB(y); adj[y].PB(x); } dfs(1,-1); rep(i,1,n+1) cout << dp[i] << endl; }

Using a Set for LIS: AC in 175mS

V(ll) adj[200005]; ll n,k; ll val[200005]; ll dp[200005]; set<ll> s; void dfs(ll node, ll parent){ ll rep = -1; auto it = s.lower_bound(val[node]); if (it != s.end()) { rep = *it; s.erase(it); } s.insert(val[node]); dp[node] = s.size(); for(ll child:adj[node]){ if (child != parent){ dfs(child,node); } } s.erase(val[node]); if (rep != -1){ s.insert(rep); } } void solve() { cin >> n; rep(i,1,n+1) cin >> val[i]; rep(i,0,n-1){ ll x,y; cin >> x >> y; adj[x].PB(y); adj[y].PB(x); } dfs(1,-1); rep(i,1,n+1) cout << dp[i] << endl; }

Using a multi set for  LIS: AC in 186mS

V(ll) adj[200005]; ll n,k; ll val[200005]; ll dp[200005]; multiset<ll> s; void dfs(ll node, ll parent){ ll rep = -1; auto it = s.lower_bound(val[node]); if (it != s.end()) { rep = *it; s.erase(it); } s.insert(val[node]); dp[node] = s.size(); for(ll child:adj[node]){ if (child != parent){ dfs(child,node); } } s.erase(s.find(val[node])); if (rep != -1){ s.insert(rep); } } void solve() { cin >> n; rep(i,1,n+1) cin >> val[i]; rep(i,0,n-1){ ll x,y; cin >> x >> y; adj[x].PB(y); adj[y].PB(x); } dfs(1,-1); rep(i,1,n+1) cout << dp[i] << endl; }

Questions to look ahead?

1. https://open.kattis.com/problems/neverjumpdown 
1. I will upload the solution to this soon.
2. You can leave a comment if you find some exciting problems on LIS over trees

Understanding the NlogN Approach for LIS

O(nlogn) algorithm for The LIS

We already know about the quadratic time LIS approach using Dynamic Programming.

Today, we gonna see and understand the shortest O(nlogn) approach for LIS.

Let the sequence be A = {3,6,5,4,7,10}

We know the LIS lengths for each index is {1,2,2,2,3,4}

Approach:

We will loop over the array and store the LIS at each index in a separate vector. If the incoming element is smaller than any element in our LIS, then we take the lower bound to find the next greater element and replace it with the current element. This is because replacing the element will not change the LIS length and also if a smaller element is added to LIS, then we can get more advantages from future elements. 

For example let our sequence be just S ={ 3, 6, 4, 5}

If we consider the LIS for the first index = {3}

If we consider the LIS for the Second index = {3,6}

But, when we consider the LIS for the third index, we have two options: {3,6} or {3,4}.

We will choose {3,4} because 4 is less than 6. The advantage will be clear on the very next index.

When we consider the LIS for the fourth index = {3,4,5}. But, if we had chosen {3,6} on the third index, we would have missed the 5 because {3,6,5} is not LIS. 

So, at every possible index, we just find the lower_bound of the current element and if it exists in the vector of LIS, we replace that with our element. If it does not exist, we simply push our element because it is the largest element in our LIS. 

To know the LIS at any particular index, we can simply check out the size of our vector.

vector<int> v;
for (int i = 0; i < n; i++) {
    auto it = lower_bound(v.begin(), v.end(), a[i]);
    if (it != v.end()) *it = a[i];
    else v.push_back(a[i]);
}
return v.size();

This finds a strictly-increasing LIS, but you can easily modify it to find the longest nondecreasing sequences by changing lower_bound to upper_bound.

Questions for Practice ??

1. https://www.spoj.com/problems/LMIS/
2. https://www.spoj.com/problems/ELIS/

AtCoder Beginner Contest 165

C - Many Requirements

Problem Statement: here

Solution:

TAG - BackTracking, Full Search

The problem must be solved using the concept of recursion. The constraints were so small, that we could generate all the possible permutations of sequence A and check each sequence with all queries and compute the maximum answer.

I used simple recursion for each possible value of my current position. Since the element at the current position should be greater than the previous element, I pass the previous element as a parameter. Also do not forget to remove the element from vector once your forward recursion is complete.

The code:

V(ll) v; V(ll) q[51]; ll n,m,qp; ll ans = INT_MIN; void full(ll pos, ll past){ if (pos == n){ ll tsum = 0; rep(i,0,qp){ if (v[q[i][1]-1] - v[q[i][0]-1] == q[i][2]){ tsum += q[i][3]; } } ans = max(ans,tsum); return; }

rep(i,past,m+1){ v.PB(i); full(pos+1,i); v.pop_back(); } } void solve(){ cin >> n >> m >> qp; rep(i,0,qp){ rep(j,0,4){ ll t; cin >> t; q[i].PB(t); } } full(0,1); cout << ans << endl; }

Floor Function

Problem Statement: here

Solution:

This problem was simply based on a binary search. I applied the binary search blindly and it gave me AC. So, there is nothing to discuss I guess, but if you are not sure how binary search is working, (like me, lol NO!) you can take up values of A and B and check for values of x varying from 1 to N and plot it roughly. 

void solve() { ll a,b,n; cin >> a >> b >> n; ll low = 0; ll high = n; ll ans = INT_MIN; while(low <= high){ ll mid = (low + high)/2; if ((a*mid)/b - a*(mid/b) >= ans){ low = mid+1; ans = (a*mid)/b - a*(mid/b); } else high = mid-1; } cout << ans; }