Thursday, 30 April 2020

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/

Wednesday, 29 April 2020

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

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?
We will be discussing this problem soon. 

Tuesday, 28 April 2020

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

Monday, 27 April 2020

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

Sunday, 26 April 2020

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!

Saturday, 25 April 2020

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

Friday, 24 April 2020

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.

R \leq 200,000
K\leq 10^{18}
Q \leq 2000

Preprocessing

 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=1min(n,r+1)dp[n1][r(k1)


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

Thursday, 23 April 2020

Segment Trees #3 Segment Trees on strings: Point Updates and Range Queries

Queries on the String


Problem Statement: here


Solution:

Here, we solve another problem on Seg Trees, in which we are asked to find the number of substrings which are divisible by 3. We know the sum of digits has to be divisible by 3, for the number to be divisible by 3. 
So what goes into the node??
  1. Obviously, the answer of that node
  2. We will store the count of substrings that give 0 when summed up and modulo by  3. Similarly for 1 and 2. Suppose we have a string 0123456, then 0123 sum = 6, modulo 3 is 0. So we add 1 to prefix[0] for this string. Similarly, we will be storing the count of number of prefix substrings which gives modulo 0,1,2 upon modulo 3.
  3. In a similar fashion, we will store the count of substrings whose suffix sum is 0,1,2 when modulo by 3.
  4. We will also store the total sum of string in that interval modulo 3.
What are the relations of merging two nodes?
  1. ans = left(ans)  + right(ans). Also, left suffix sums which add up to i and right prefix sums which add up to 3-i are part of answer as well.
  2. prefixsum count for ans is nothing but prefix sum count of left + something. You can look at my code for better understanding of the equation. The thing is, when we take total sum of left, and some prefix sum of right, we need to update those strings as well.
  3. Similarly for suffix sum.
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=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 };
string s; ll n; ll ans[400005]={}; ll suffcount[400005][3]={}; ll prefcount[400005][3]={}; ll tot[400005]={}; void build(ll ind, ll l, ll r){ if (l==r){ ll v = s[l] - '0'; if (v%3 == 0){ ans[ind] = 1; prefcount[ind][0] = 1; suffcount[ind][0] = 1; } else if (v%3 == 1){ suffcount[ind][1] = 1; prefcount[ind][1] = 1; } else{ suffcount[ind][2] = 1; prefcount[ind][2] = 1; } tot[ind] = v%3; return; } ll mid = (l+r)/2; build(2*ind,l,mid); build(2*ind+1,mid+1,r); ans[ind] = ans[2*ind] + ans[2*ind+1]; rep(i,0,3){ ans[ind] += suffcount[2*ind][i]*prefcount[2*ind+1][(3-i)%3]; } rep(i,0,3){ prefcount[ind][i] = prefcount[2*ind][i] + prefcount[2*ind+1][(3 - tot[2*ind] + i)%3]; suffcount[ind][i] = suffcount[2*ind+1][i] + suffcount[2*ind][(3-tot[2*ind+1] + i)%3]; } tot[ind] = (tot[2*ind] + tot[2*ind+1])%3; } void update(ll ind, ll l, ll r, ll val, ll tar){ if (tar < l || tar > r){ return; } if (l == r){ ll q = val; if (q == 0){ ans[ind] = 1; } else ans[ind] = 0; rep(i,0,3){ if(i == q){ prefcount[ind][i] = 1; suffcount[ind][i] = 1; } else{ prefcount[ind][i] = 0; suffcount[ind][i] = 0; } } tot[ind] = q; return; } ll mid = (l+r)/2; update(2*ind,l,mid,val,tar); update(2*ind+1,mid+1,r,val,tar); ans[ind] = ans[2*ind] + ans[2*ind+1]; rep(i,0,3){ ans[ind] += suffcount[2*ind][i]*prefcount[2*ind+1][(3-i)%3]; } rep(i,0,3){ prefcount[ind][i] = prefcount[2*ind][i] + prefcount[2*ind+1][(3 - tot[2*ind] + i)%3]; suffcount[ind][i] = suffcount[2*ind+1][i] + suffcount[2*ind][(3-tot[2*ind+1] + i)%3]; } tot[ind] = (tot[2*ind] + tot[2*ind+1])%3; } pair<pll,pair<V(ll),V(ll)>> query(ll ind, ll l, ll r, ll qs, ll qe){ if (qe < l || qs> r){ V(ll) v; rep(i,0,3) v.PB(0); return mp(mp(0,0),mp(v,v)); } if (qs <= l && qe >= r){ V(ll) p,q; rep(i,0,3){ p.PB(prefcount[ind][i]); q.PB(suffcount[ind][i]); } return mp(mp(ans[ind],tot[ind]),mp(p,q)); } ll mid = (l+r)/2; pair<pll,pair<V(ll),V(ll)>> left = query(2*ind,l,mid,qs,qe); pair<pll,pair<V(ll),V(ll)>> right = query(2*ind+1,mid+1,r,qs,qe); ll a,t; V(ll) p,s; a = left.F.F + right.F.F; rep(i,0,3){ a += (left.S.S)[i]*(right.S.F)[(3-i)%3]; } rep(i,0,3){ p.PB((left.S.F)[i] + (right.S.F)[(3 - tot[2*ind] + i)%3]); s.PB((right.S.S)[i] + (left.S.S)[(3-tot[2*ind+1] + i)%3]); } t = (left.F.S + right.F.S)%3; return mp(mp(a,t),mp(p,s)); } void solve() { ll m; cin >> n >> m; cin >> s; build(1,0,n-1); rep(i,0,m){ ll t,x,y; cin >> t >> x >> y; if (t == 1){ update(1,0,n-1,y%3,--x); } else{ pair<pll,pair<V(ll),V(ll)>> final = query(1,0,n-1,--x,--y); cout << final.F.F << 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; }

Reference to neat code using struct : https://www.codechef.com/viewsolution/32147355