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

Suffix Arrays #2 Longest Repeated Substring

Power of String

Problem Statement: here

Solution:

We have to find the longest substring occurring in the string at least K times.

The golden point is: 

EVRY SUBSTRING IS A PREFIX OF SOME SUFFIX.

So, we can quickly calculate the suffix array and LCP array of the given string.

Once, we have calculated the suffix array, we now want the substring of the maximum common prefix, but it should be present at least k times. This means, in LCP array, it should be present in at least k-1 consecutive elements. So, we can use the sliding window technique to find out the minimum in a sliding window of length k-1.

Why does the longest substring need to be present in consecutive suffix array indices??

Since we know that suffix array is nothing but lexicographically shortest suffixes array. Let's say the length of the longest substring is x, and let us represent is by L. Then our string can be represented as:

S = A₁LA₂L....Aₚ, where L is the longest substring repeating at least K times. So, when we look at the suffix array, all the suffixes which start with this L, they have to be present together in our suffix array, because a large part of it is common. But, it might be possible that we have a suffix that starts from L and shares prefix length much larger than just L. Thus, we consider the minimum of the entire window because we know in minimum, they will be sharing exactly L length, if they would have been sharing more, that would have already been included in counting for L.

Complexities:

Building Suffix Array - O(NlogN)

Building LCP Table - O(N)

Computing minimum in a sliding window - O(N)

Thus, the overall complexity is O(NlogN). We could have even used any RMQ data structure like segment trees to answer the minimum in the sliding window, but we have used the most optimal way of doing it - using a monotonic queue. I will make a separate blog post (maybe) discussing the monotonic queue and its wide applications.

The code:

#include<bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define M1 1000000007 #define M2 998244353 #define ll long long int #define pll pair<ll,ll> #define mll map<ll,ll> #define F first #define S second #define PB push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define V(a) vector<a> #define endl '\n' #define test(t) while(t--) #define PI acos(-1.0) #define rep(i,a,b) for(ll i=a;i<b;i++) #define repp(i,b,a) for(ll i=b-1;i>=a;i--) #define clr(ar, val) memset(ar, val, sizeof(ar)) #define setbits(x) __builtin_popcountll(x) #define zrobits(x) __builtin_ctzll(x) #define ps(y) fixed << setprecision(y) #define all(x) begin(x),end(x) #define allr(x) rbegin(x),rend(x) const int inf= 0x3f3f3f3f; const ll INF= 0x3f3f3f3f3f3f3f3f; const int dx[4]= { 0, -1, 0, 1 }; const int dy[4]= { -1, 0, 1, 0 }; ll floor_div(ll a, ll b) { return a / b - (((a ^ b) < 0) and a % b); } ll ceil_div(ll a, ll b){ return a / b + (((a ^ b) >= 0) and a % b); } vector<int> suffix_array_cyclic(string s){ int n = s.size(), N = n + 256; vector<int> sa(n), ra(n); for(int i = 0; i < n; i++) sa[i] = i, ra[i] = s[i]; for(int k = 0; k < n; k ? k *= 2 : k++) { vector<int> nsa(sa), nra(n), cnt(N); for(int i = 0; i < n; i++) nsa[i] = (nsa[i] - k + n) % n; for(int i = 0; i < n; i++) cnt[ra[i]]++; for(int i = 1; i < N; i++) cnt[i] += cnt[i - 1]; for(int i = n - 1; i >= 0; i--) sa[--cnt[ra[nsa[i]]]] = nsa[i]; int r = 0; for(int i = 1; i < n; i++) { if(ra[sa[i]] != ra[sa[i - 1]]) r++; else if(ra[(sa[i] + k) % n] != ra[(sa[i - 1] + k) % n]) r++; nra[sa[i]] = r; } ra = nra; } return sa; } vector<int> kasai(string s, vector<int> sa) { int n = s.size(), k = 0; vector<int> ra(n), lcp(n); for(int i = 0; i < n; i++) ra[sa[i]] = i; for(int i = 0; i < n; i++) { if(k) k--; if(ra[i] == n - 1) {k = 0; continue;} int j = sa[ra[i] + 1]; while(k < n && s[(i + k) % n] == s[(j + k) % n]) k++; lcp[ra[i]] = k; if(ra[(sa[ra[i]] + 1) % n] > ra[(sa[ra[j]] + 1) % n]) k = 0; } return lcp; } inline void INP() { #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif } void solve() { ll n,k; cin >> k >> n; if (k == 1){ cout << n << endl; return; } string s; cin >> s; s += '#'; vector<int> sa = suffix_array_cyclic(s); vector<int> lcp = kasai(s,sa); lcp.erase(lcp.begin()); // for(int i: lcp) cout << i << " ";cout << endl; deque<pair<int,int>> dq; int gmax = INT_MIN; rep(i,0,k-1){ while(!dq.empty() and dq.back().F >= lcp[i]){ dq.pop_back(); } dq.push_back({lcp[i],i}); } gmax = max(gmax,dq.front().F); rep(i,k-1,lcp.size()-1){ while(!dq.empty() and dq.back().F >= lcp[i]){ dq.pop_back(); } dq.push_back({lcp[i],i}); while(dq.front().S <= i-(k-1)) dq.pop_front(); gmax = max(gmax,dq.front().F); } cout << gmax << 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; }

Segment Trees #6 Offline Queries

KQUERY - SPOJ

Problem Statement: here

Solution:
I will be sharing 3 different Approaches. Starting from the one which will give TLE.
So, the statement in the question is quite simple, you just need to output the number of elements in the range which are greater then k.

First Approach - Using Ordered Set in Segment Trees

If you are not familiar with ordered sets, have a look here.

 The only problem is how to create the build function as to how will we merge the two nodes. So, since the merging can be a problem, we can use the update function and we can update the tree by adding new elements each time. So, overall complexity of building the tree goes to O(N*logN*logN).  Because, for each element, we have logN nodes for traversal, and at each node, it takes logN time to perform the insert operation. After that for each query,  we have logN*logN complexity too. Because order of key function takes logN time to process.

So, the overall complexity is O((N+Q)*logN*logN). But still, it will throw TLE, maybe because the order of  key may take more than logN time per query.

Implementation:

#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define o_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> //member functions : //1. order_of_key(k) : number of elements strictly lesser than k //2. find_by_order(k) : k-th element in the set

o_set ped[4*30000 + 5]; int n; int a[30005]; void update(int ind, int l, int r, int t, int val){ if (t < l || t > r){ return; } if (l == r){ ped[ind].insert(-1*val); return; } int mid = (l+r)/2; update(2*ind,l,mid,t,val); update(2*ind+1,mid+1,r,t,val); ped[ind].insert(-1*val); } int query(int ind, int l, int r, int qs, int qe, int k){ if (l > qe || r < qs){ return 0; } if (l >= qs and r<= qe){ return ped[ind].order_of_key(-1*k); } int mid = (l+r)/2; return query(2*ind,l,mid,qs,qe,k) + query(2*ind+1,mid+1,r,qs,qe,k); } void solve() { cin >> n; rep(i,0,n){ cin >> a[i]; update(1,0,n-1,i,a[i]); } int q; cin >> q; rep(p,0,q){ int i,j,k; cin >> i >> j >> k; cout << query(1,0,n-1,--i,--j,k) << endl; } }

Second Approach - Processing Queries Offline

So, the idea is to store all queries and sort them on the basis of their k values. Also, sort the input array. Initially, we assume our k = 0. So, all the elements are greater than 0, so we build a segment tree wherein each leaf node which represents the array elements will be 1, denoting they are greater than k. 

Now, we start to loop over the sorted queries, since for each query, the k value is greater than the previous query, we know for sure, that elements which are smaller than previous query k value will be smaller than our k value. Since the input array is also now sorted, we can loop over the input array to the point where it's elements are either less than or equal to our current k value. Again, we are sure that for all upcoming queries, all elements below this index will surely be smaller than our future k values. 

Once we loop over the input array, we start to update the segment tree with that particular leaf node's value set equal to zero. Remember, we initially placed all bits set because our k was 0. But, once we loop over queries we get different k, once we loop over the array and check if array element is less than or equal to k, we simply update the segment tree and set the bit to zero. Once our array loop is terminated, we simply perform query over the required query range to get the sum of all set bits.

The code:

int sum[4*30000 + 5]; int n; pair<int,int> a[30005]; pair<pair<int,int>,pair<int,int>> q[200005]; int ans[200005]; void build(int ind, int l, int r){ if (l == r){ sum[ind] = 1; return; } int mid = (l+r)>>1; build(2*ind,l,mid); build(2*ind+1,mid+1,r); sum[ind] = sum[2*ind] + sum[2*ind+1]; } void update(int ind, int l, int r, int p){ if (p < l or p > r){ return; } if (l == r){ sum[ind] = 0; return; } int mid = (l+r)/2; update(2*ind,l,mid,p); update(2*ind+1,mid+1,r,p); sum[ind] = sum[2*ind] + sum[2*ind+1]; } int get_sum(int ind, int l, int r, int qs, int qe){ if (l > qe || r < qs){ return 0; } if (l >= qs and r<= qe){ return sum[ind]; } int mid = (l+r)/2; return get_sum(2*ind,l,mid,qs,qe) + get_sum(2*ind+1,mid+1,r,qs,qe); } void solve() { cin >> n; rep(i,0,n){ cin >> a[i].F; a[i].S = i; } build(1,0,n-1); int qr; cin >> qr; rep(i,0,qr){ cin >> q[i].S.F >> q[i].S.S >> q[i].F.F; q[i].F.S = i; } sort(a,a+n); sort(q,q+qr); int pos = 0; rep(i,0,qr){ int k = q[i].F.F; while(pos < n and a[pos].F <= k){ update(1,0,n-1,a[pos].S); pos++; } ans[q[i].F.S] = get_sum(1,0,n-1,--q[i].S.F,--q[i].S.S); } rep(i,0,qr) cout << ans[i] << endl; }

Third Approach -  Using Fenwick Trees

This approach becomes crucial when we have updates as well, we will look at this approach in the future problem of our series, namely this problem - https://www.spoj.com/problems/KQUERYO/

Suffix Arrays #1 Longest Common Substring

A Story with Strings Problem Code: SSTORY

Problem Statement: here

Solution:

This is the first problem with suffix arrays. so I will give a little boring lecture on it. So, bare with me.

Suffix Arrays

This is another data structure that operates on strings. It is a much lighter version, also known as a compressed version of suffix trees, which is itself a special case of trie data structure. 

Let us come out of the ocean. Suffix Array is a data structure that stores the suffix strings in lexicographically shortest order. Note, we do not store the strings, instead, we just store the starting index of our suffix. Using the starting index, obviously, we can create the entire suffix string.

Use cases:

We will see many different applications of suffix arrays.

Today, as you saw in the problem statement, we are finding the Longest Common Substring of given 2 strings. 

We will construct the suffix array in O(nlogn) time. You can also use O(nlog^2n) to form the suffix array. After this, we can construct the LCP table of this suffix array in O(n) time. 

The LCP table tells us the longest common prefix of suffixes of our string. This construction is widely used in many questions, which involve operations with substrings.  

The way LCP is constructed is that we look at the suffix string present at index i in our suffix array and compare it with i+1 suffix string. Then, the longest common prefix among them is the value of LCP[i].

So, in our question, we can form a single string s = s2 + '#' + s1. Please note that the senital character must have precedence less than any other value present in s1 or s2. This will make sure, that it comes at the very start of our suffix array, and we can then continue to move on from the next index.

Once we have computed the LCP table,  we know that LCP[i] gives us the longest common prefix for suffixes starting at suffix[i] and suffix[i+1]. To make sure that these suffixes belong to 2 different strings, we can check whether the index at suffix[i] is less than the length of s2 or index of suffix[i+1] less than the length of s2 and the other greater than s2. Since, suffix[i] stores the index of the start of suffix string, this is possible to do!

Also, once you implement, you will notice some failures because of some test cases. 

Try these tests then and you will figure out the mistake.

Test 01:

abcadlfghijkl

abcdlfabcde

Test 02:

abcmdef

abcdefabcdl

My code:

#include<bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define M1 1000000007 #define M2 998244353 #define ll long long int #define pll pair<ll,ll> #define mll map<ll,ll> #define F first #define S second #define PB push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define V(a) vector<a> #define endl '\n' #define test(t) while(t--) #define PI acos(-1.0) #define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++) #define repp(i,b,a) for(ll i=(ll)(b-1);i>=(ll)a;i--) #define clr(ar, val) memset(ar, val, sizeof(ar)) #define setbits(x) __builtin_popcountll(x) #define zrobits(x) __builtin_ctzll(x) #define ps(y) fixed << setprecision(y) #define all(x) begin(x),end(x) #define allr(x) rbegin(x),rend(x) const int inf= 0x3f3f3f3f; const ll INF= 0x3f3f3f3f3f3f3f3f; const int dx[4]= { 0, -1, 0, 1 }; const int dy[4]= { -1, 0, 1, 0 }; vector<int> suffix_array_cyclic(string s){ int n = s.size(), N = n + 256; vector<int> sa(n), ra(n); for(int i = 0; i < n; i++) sa[i] = i, ra[i] = s[i]; for(int k = 0; k < n; k ? k *= 2 : k++) { vector<int> nsa(sa), nra(n), cnt(N); for(int i = 0; i < n; i++) nsa[i] = (nsa[i] - k + n) % n; for(int i = 0; i < n; i++) cnt[ra[i]]++; for(int i = 1; i < N; i++) cnt[i] += cnt[i - 1]; for(int i = n - 1; i >= 0; i--) sa[--cnt[ra[nsa[i]]]] = nsa[i]; int r = 0; for(int i = 1; i < n; i++) { if(ra[sa[i]] != ra[sa[i - 1]]) r++; else if(ra[(sa[i] + k) % n] != ra[(sa[i - 1] + k) % n]) r++; nra[sa[i]] = r; } ra = nra; } return sa; } vector<int> kasai(string s, vector<int> sa) { int n = s.size(), k = 0; vector<int> ra(n), lcp(n); for(int i = 0; i < n; i++) ra[sa[i]] = i; for(int i = 0; i < n; i++) { if(k) k--; if(ra[i] == n - 1) {k = 0; continue;} int j = sa[ra[i] + 1]; while(k < n && s[(i + k) % n] == s[(j + k) % n]) k++; lcp[ra[i]] = k; if(ra[(sa[ra[i]] + 1) % n] > ra[(sa[ra[j]] + 1) % n]) k = 0; } return lcp; } void solve() { string s1,s2; cin >> s1 >> s2; int l2 = s2.size(); string s = s2 + '#' + s1 + '$'; vector<int> v = suffix_array_cyclic(s); vector<int> lcp = kasai(s,v); int mx = 0; map<string,bool> sm; for(int i=0;i<v.size()-1;i++){ if (min(v[i],v[i+1]) < l2 and max(v[i],v[i+1])>l2){ mx = max(mx,lcp[i]); } } if (mx == 0){ cout << 0 << endl; return; } for(int i=0;i<v.size()-1;i++){ if (min(v[i],v[i+1]) < l2 and max(v[i],v[i+1])>l2){ if (lcp[i] == mx){ sm[s.substr(max(v[i],v[i+1]),mx)] = true; } } } string fans = s2.substr(0,mx); if (sm[fans]){ cout << fans << endl; cout << mx << endl; return; } for(int i=mx;i<=s2.size();i++){ fans.erase(fans.begin()); fans += s2[i]; if (sm[fans]){ cout << fans << endl; cout << mx << endl; return; } } } 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; }

Time Complexity: O(nlogn)

What next??

Try out https://www.spoj.com/problems/LCS/

This problem is exactly the above one, but with my approach only you will be able to pass all tests, the time restrictions are tight. Although, this is a simpler version of the problem we discussed because it only asks for the maximum size of the substring. So, I won't discuss this problem.

Want a little challenging task?

Try out https://open.kattis.com/problems/lifeforms

We will be discussing this problem soon. 

Segment Trees #5 Range Updates and Range Queries

Counting Zeroes Problem Code: COUNZ

Problem Statement: here

Solution:

As you have seen in the title of the post, we are going to perform range updates in this question. Till now, in our series, we have only done point updates. We know point updates take O(logN) time complexity. Doing range updates will then take complexity to O(NlogN). This will surely give TLE.

So, for dealing with range updates, we use the technique of Lazy Propagation, where the complexity of Range updates boils down to O(logN).

Approach: 

We know the product will have the number of zeroes equal to :

min(num_of_2,num_of_5) in it's prime factorization, only exception being when the value itself is zero.

So, we use this thumb rule and write our functions!

Time Complexity Analysis:

1. Building Segment Tree: O(NlogM) where M is the maximum element in the array.  
1. Because For each leaf node, we need logM time for each element to figure out its factorization or simply the power of 2 and 5.
2. Update Function: 
1. It takes logN for each Query  + factorization takes logM.
3. Query Function:
1. It takes logN for each Query  + factorization takes logM.

Overall complexity: O(N*logM + Q*(logN + logM))

So, we now know the power of lazy propagation to answer range updates. It is so simple to implement and efficient to use, also it is by far the only way to tackle range updates efficiently in segment trees.

The Code:

ll n; ll a[100005]; ll tree[4*100005 + 2][3]; ll lazy[4*100005 + 2]; void process(ll ind, ll l){ tree[ind][0] = tree[ind][1] = tree[ind][2] = 0; ll num = l; if (num == 0){ tree[ind][0]++; return; } while(num%2 == 0){ tree[ind][1]++; num/=2; } while(num%5 == 0){ tree[ind][2]++; num/=5; } return; } void build(ll ind, ll l ,ll r){ if (l == r){ process(ind,a[l]); return; } ll mid = (l+r)/2; build(2*ind,l,mid); build(2*ind+1,mid+1,r); rep(i,0,3){ tree[ind][i] = tree[2*ind][i] + tree[2*ind+1][i]; } } void update(ll ind, ll l, ll r, ll us, ll ue, ll val){ //First Step - Never we go down if you have lazy value at node, first resolve it if (lazy[ind] != -1){ process(ind,lazy[ind]); rep(i,0,3){ tree[ind][i] *= (r-l+1); } //if not a leaf node, pass on the lazy value if ( l!=r ){ lazy[2*ind] = lazy[2*ind + 1] = lazy[ind]; } // Lazy value resolved. lazy[ind] = -1; } if (r < us || l > ue){ return; } if (l >= us and r <= ue){ process(ind,val); rep(i,0,3){ tree[ind][i] *= (r-l+1); } if ( l!=r ){ lazy[2*ind] = lazy[2*ind + 1] = val; } return; } ll mid = (l+r)/2; update(2*ind,l,mid,us,ue,val); update(2*ind+1,mid+1,r,us,ue,val); rep(i,0,3){ tree[ind][i] = tree[2*ind][i] + tree[2*ind+1][i]; } } V(ll) query(ll ind, ll l,ll r, ll qs, ll qe){ //First Step - Never we go down if you have lazy value at node, first resolve it if (lazy[ind] != -1){ process(ind,lazy[ind]); rep(i,0,3){ tree[ind][i] *= (r-l+1); } //if not a leaf node, pass on the lazy value if ( l!=r ){ lazy[2*ind] = lazy[2*ind + 1] = lazy[ind]; } // Lazy value resolved. lazy[ind] = -1; } if (r < qs || l> qe){ V(ll) v(3,0); return v; } if (l>= qs and r<=qe){ V(ll) v(3,0); rep(i,0,3) v[i] = tree[ind][i]; return v; } ll mid = (l+r)/2; V(ll) left = query(2*ind, l, mid, qs,qe); V(ll) right = query(2*ind+1,mid+1,r,qs,qe); V(ll) v(3,0); rep(i,0,3) v[i] = left[i] + right[i]; return v; } void solve() { clr(lazy,-1); cin >> n; rep(i,0,n) cin >> a[i]; build(1,0,n-1); ll q; cin >> q; rep(i,0,q){ ll t; cin >> t; if (t == 0){ ll l,r,v; cin >> l >> r >> v; update(1,0,n-1,--l,--r,v); } else{ ll l,r; cin >> l >> r; V(ll) ans = query(1,0,n-1,--l,--r); if (ans[0]){ cout << 1 << endl; } else{ cout << min(ans[1],ans[2]) << 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; }

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

AtCoder Beginner Contest 164

D - Multiple of 2019

Problem Statement: here

Solution: 

We are told to find out the number of pairs such that the base 10 representation of the string gets divisible by 2019. 

The problem could have been asked for any number, nothing special about 2019. Also, the problem could have been asked for any remainder,  like give those pairs which give the remainder of 1. 

So, basically, looking at the limit of N, going up to order 5, we can not create a 2D dp array. 

I claim that you don't need your dp array to the size above 2019. 

My main logic is: Gather the number of pairs up to the index i-1, which gives the remainder as 0,1,2,....2018 when divided by 2019. So, if I store their count in my dp array, then:

dp[i] represents the number of pairs which gives i when the number is modulo by 2019. I don't care what the number is, I just need the modulo. 

But. wait. Why? 

So, let us assume that the number is x up to the index i-1. Then, including the index i, the number will become 10*x + num[i] where num[i] is the digit of index i. To find it's remainder I will simply modulo it by 2019, which becomes (10*(x%2019) + num[i])%2019. So, we see that we don't require the number x, we just need the value of x%2019. 

So, I loop over all the possible values up to 2019, check if the dp[i] > 0, if yes then obtain the remainder when divided by 2019, if the remainder is 0: this means I can create exactly dp[j] answers, because dp[j] is the number of guys ending at index [i-1] giving remainder j, in front of whom, I can add this digit to get my answer. 

I have created another table inside the loop for each particular index, because I want to propagate the count of only those numbers of pairs which ended at current index giving the remainder. So, I copy it after the entire operation is done. 

The way I fill this inner dp table is simply : when I computed the remainder , I just do :

inner dp [ rem ] += dp[j] because I can get dp[j] pairs with this remainder, using similar logic by which we computed answer. 

The code:

void solve() { string s; cin >> s; ll ans = 0; ll dp[2019]; clr(dp,0); dp[s[0] - '0'] = 1; rep(i,1,s.size()){ int d = s[i] - '0'; ll tdp[2019]; clr(tdp,0); tdp[d] = 1; rep(j,0,2019){ if (dp[j] > 0){ ll rem = (10*j + d)%2019; if (rem == 0) ans+=dp[j]; tdp[rem]+=dp[j]; } } rep(i,0,2019){ dp[i] = tdp[i]; } } cout << ans; }

Strings #1 Application of KMP

Shortest Palindrome

Problem Statement: here

Solution: 

So this problem requires us to find the shortest length of palindrome by appending characters in front of the string. Clearly, the fewer characters we append, the shortest is the length. For this purpose, we must be interested in finding the longest palindromic prefix substring of the given string. This allows us to know the minimal characters from behind which when appended to the front will give us the shortest palindrome. 

For example string = "ABCCBADEA", we know the longest palindromic prefix is "ABCCBA" and if we append "AED", to the front, we will get the shortest palindrome.

So, how to find the longest prefix palindrome of a given string?

We will use the help of the KMP failure table to calculate the longest prefix palindrome for our string. We know that the failure table keeps track of the longest prefix which is also the suffix of the given string. Exploiting this fact, we can actually construct a new string T = S*S' where S' is the reverse string of S. Once we do this, let's say S = AB where A is a palindrome of largest size and B is rest, then T = AB*B'A, clearly we see KMP can be used to find out the A here.

The code:

class Solution { public: string shortestPalindrome(string s) { int n = s.size(); string sprime(s); reverse(sprime.begin(), sprime.end()); string stot = s + "*" + sprime; int ntot = stot.size(); vector<int> f(ntot,0); for (int i = 1; i < ntot; i++) { int t = f[i - 1]; while (t > 0 && stot[i] != stot[t]) t = f[t - 1]; if (stot[i] == stot[t]) ++t; f[i] = t; } return sprime.substr(0, n - f[ntot - 1]) + s; } };

What next after learning this application? 

Try your hands on this application here: https://codeforces.com/contest/1326/problem/D2
I will discuss it's solution by tomorrow!

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!!