PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Ildar Gainullin
Tester: Alexander Morozov
Editorialist: Taranpreet Singh
DIFFICULTY
Hard/Super-hard
PREREQUISITES
Patience, Chordal Graphs, Clique trees, Dynamic Programming and Combinatorics.
PROBLEM
Given a string S of length N, count the number of subsets of set S \sub \{1, 2, 3 \ldots N\} such that there exists a string T similar to S having T_x = c for all x \in S.
Two strings are considered similar if and only if both are of same length, and all corresponding substrings both are either palindrome, or non-palindrome.
QUICK EXPLANATION
- Merge pairs of nodes definitely same and add edges between pairs of nodes definitely not same, the resulting graph is a chordal graph, and we need something like number of independent subsets.
- Construct clique tree of above chordal graph, maintaining set of nodes of chordal graph represented by each node in clique tree.
- To count the number of independent subsets, we need to run dynamic programming on this tree, either choosing a specific chordal node of current clique, or not selecting at all.
- We also need to consider each chordal node representing a set of positions in original string.
EXPLANATION
This editorial has a lot to cover, so it may be hard to read, due to several corner cases.
The brute force approach is to enumerate all subsets, and checking each subset individually. Let’s see how similar condition restricts us from choosing any string T.
Considering our string S, let’s assume substring S_{l, r} is a palindrome, but S_{l-1, r+1} is not. This implies that in string T, character at position l and r should match, while characters at positions l-1 and r+1 definitely shouldn’t match. This is all we need, find all non-equal pairs for S and for each subset, if it contains any pair, it is not a valid subset, getting 10 points.
Let’s find all pairs which should be definitely equal (like (l, r), (l+1, r-1) and so on, which appear as part of palindrome, and merge them into a single node.
Now find all pairs which should be definitely non-equal (like (l-1, r+1)) and add an edge between nodes representing position l-1 and r+1.
Now, the required number of subsets is as follows:
- consider all independent subsets of this graph.
- For each merged node present in independent subset, say x positions of string were merged at this node, so there are 2^x-1 ways to choose a subset, so we need to consider product of these over all nodes in current independent subset.
So generalizing, we need to solve problem similar to counting number of independent sets in this graph. For general graph, this is an unsolved problem, but our graph is special.
Lemma: The generated graph is Chordal Graphs.
Proof
It is sufficient to prove that for every cycle of length greater than 3, there exists an edge not part of cycle, connecting two vertices of cycle.
Let’s assume string S_{l+1, r-1} is palindrome but S_{l,r} is not. So we know, there’s an edge between position l and r. Assuming r-l-1 > 2, this implies positions l+1 and r-1 are definitely equal, thus merged into one node.
There are three cases
- Characters at position l and l+1 match: In this case, positions l and l+1 are merged, leaving only two nodes connected by a single edge.
- Characters at position r and r-1 match: In this case, positions r and r-1 are merged, leaving only two nodes connected by a single edge.
- Neither l match with l+1 position, not r with r-1. In this case, considering string S_{l, l+1}, there’s edge (l, l+1), similarly, there’s edge (r-1, r). But l+1 and r-1 are merged, say into node x, so we have edges (l, x), (x, r) and (l, r), leading to a cycle of length 3.
Hence, the generated graph is chordal.
Now, counting number of independent sets is done by building clique graph for given chordal graph, and running a dynamic programming.
The construction of clique graph is described in this paper. I found This and this paper quite useful for understanding.
The gist of above papers (it’s required to read first paper carefully, as it’s page 10 contains algorithm to build clique tree). Som epointers which might be useful
- For each non-adjacent pair of nodes, the minimal separator is a clique.
- The maximal cliques over all separators represent the nodes of clique tree.
- For three cliques S_1, S_2 and S_3, such that edges connecting them are (S_1, S_2) and (S_2, S_3), there cannot exist any node of chordal graph, which was included in cliques S_1 and S_3, but not in S_2
- For two adjacent cliques S_1 and S_2, the intersection of the cliques is a minimal separator for all paths with one endpoint at each side.
I’d not cover the exact construction part, as it is explained in paper, and solutions attached uses same variable notations for ease of understanding.
Now, let’s define some notation.
I’d refer nodes of chordal graph as chordal node and nodes of clique tree as clique nodes
- K: Number of clique nodes in clique tree T
- M: Number of nodes in chordal graph
- C_i: The set of chordal nodes present in i-th clique
- T_u: The set of clique nodes adjacent to clique node u.
- cnt_u: The number of positions of string merged into chordal node u
Now, we have several cliques, some adjacent cliques sharing vertices, and we need to compute number of independent sets of chordal graph.
Let’s first deal with merged positions. Say x nodes are merged to form a chordal node. Assuming we find an independent subset of chordal graph, which contains this node. Including this node is equivalent to including any one of the non-empty subsets of x positions, thus giving 2^x-1 choices. These would be multiplied over each node present in independent set. Let us create f(u) to automatically handle ways of including node u in independent set. So whenever we consider including node u into independent set, there are f(u) ways.
It is important to notice that we can choose at most one node from each clique, but some cliques may share vertices, so that’s why we are doing the following struggle
Let us try counting the number of independent subsets in subtree of clique node u, such that we select node x from current clique, denoting by \text{chosen}(u, x), and number of independent subsets where we select no node from current clique by \text{none}(u).
Considering adjacent cliques S_1 and S_2 such that S_1 is parent of S_2 (we can root the tree at any node), we can partition chordal nodes in C_{S_1} \cup C_{S_{2}} into three disjoint classes:
- C_{S_1} \cap C_{S_2}: Appearing in both
- C_{S_1} - C_{S_2}: Appearing only in parent
- C_{S_2} - C_{S_1}: Appearing only in child
Assuming we select a node from C_{S_1} \cap C_{S_2}, we cannot select any other node from S_1 or S_2.
For computing \text{none}(u), we need to consider all clique children v, and either we keep no node from clique node v, or some node from C_v-C_u, the third class in above classification. We can take sum of \text{none}(v) and \displaystyle \sum_{x \in C_v-C_u} \text{chosen}(v, x), leading to \text{none}(v) + \displaystyle \sum_{x \in C_v-C_u} \text{chosen}(v, x) ways to chose independent subsets in subtree of child v, and we can take product over all children, getting following expression for \text{none}(u)
\text{none}(u) = \prod_{v \in T_u} \bigg[ none(v) + \sum_{x \in C_v - C_u} \text{chosen}(v, x)\bigg]
Generalizing to multiple children of clique node u, consider all chordal nodes x in clique of clique node u, add x to P if no child clique contains node x, otherwise add it to Q
Mathematically, P = C_u - \bigcup_{v \in T_u} C_u and Q = C_u \cap \big[\bigcup_{v \in T_u} C_u \big]
Now considering nodes in set P, we can effectively think of these as selecting no chordal nodes from clique u, and then select a node from P as it is independent from children cliques, giving us a simple way of computing \text{chosen}(u, x) = \text{none}(u) \times f(x)
Now, we need to deal with x \in Q, which may appear in one or more children cliques.
Let’s consider each chordal node x \in Q one by one and compute \text{chosen}(u, x). For x, let’s consider all clique children of node u. Two cases arise:
- If clique node v contains chordal node x, We must have counted ways to include it as \text{chosen}(v, x), so we take it’s product. But It also includes f(x), so we consider \displaystyle\frac{\text{chosen}(v, x)}{f(v)} ways.
- Otherwise, We either select no node from clique node v, or select some node of category 3, given by \displaystyle none(v) + \sum_{y \in C_v - C_u} \text{chosen}(v, y), already computed.
Lastly, we must multiply by f(x) ways.
So we get recurrence \displaystyle \text{chosen}(u, x) = f(x) * \prod_{v \in T_u, x \in C_v} \frac{\text{chosen}(v, x)}{f(x)} * \prod_{v \in T_u, x \notin C_v} \bigg[ \text{none}(v) + \sum_{y \in C_v-C_u} \text{chosen}(v, y)\bigg]
This is all. The final answer would be given by \displaystyle \text{none(root)} + \sum_{x \in C_{\text{root}}} \text{chosen}(\text{root}, x). It is easier to add an empty clique node as root and attach it to one node, so answer would be \text{none(root)}.
I hope this editorial, albeit most unreadable one I wrote, helps. Feel free to comment to ask doubts.
TIME COMPLEXITY
The number of edges in chordal graph cannot exceed 2*N as we can think of it as fixing positions as center and extending palindromes till we get a non-equal pair, each centre contributing atmost 1 non-equal pair.
The computation for chosen function requires us to iterate over direct children of clique node and all chordal nodes of those children, leading to complexity to be of the order of O(N^2) with/without a log factor, depending upon implementation.
SOLUTIONS
Setter's Solution
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
bool dp[2000][2000];
int dsu[2000];
int get(int v) {
if (v == dsu[v]) {
return v;
} else {
return dsu[v] = get(dsu[v]);
}
}
void uni(int u, int v) {
dsu[get(u)] = get(v);
}
const int M = 998244353;
void add(int &a, int b) {
a += b;
if (a >= M) a -= M;
if (a < 0) a += M;
}
int mul(int a, int b) {
return (a * (ll) b) % M;
}
int pw(int a, int n) {
int res = 1;
while (n) {
if (n % 2 == 0) {
a = mul(a, a);
n /= 2;
} else {
res = mul(res, a);
n--;
}
}
return res;
}
int inv(int x) {
return pw(x, M - 2);
}
int solve_chordal(vector<vector<int>> e, vector <int> cnt) {
int n = e.size();
vector<int> mark(n);
set<pair<int, int> > st;
for (int i = 0; i < n; i++) st.insert({-mark[i], i});
vector<int> vct(n);
vector<pair<int, int> > ted;
vector<vector<int> > who(n);
vector<vector<int> > verts(1);
vector<int> cliq(n, -1);
cliq.push_back(0);
vector<int> last(n + 1, n);
int prev = n + 1;
for (int i = n - 1; i >= 0; i--) {
int x = st.begin()->second;
st.erase(st.begin());
if (mark[x] <= prev) {
vector<int> cur = who[x];
cur.push_back(x);
verts.push_back(cur);
ted.push_back({cliq[last[x]], (int)verts.size() - 1});
} else {
verts.back().push_back(x);
}
for (int y : e[x]) {
if (cliq[y] != -1) continue;
who[y].push_back(x);
st.erase({-mark[y], y});
mark[y]++;
st.insert({-mark[y], y});
last[y] = x;
}
prev = mark[x];
vct[i] = x;
cliq[x] = (int)verts.size() - 1;
}
int k = verts.size();
vector<int> pr(k);
vector<vector<int> > g(k);
for (auto o : ted) {
pr[o.second] = o.first;
g[o.first].push_back(o.second);
}
vector <vector <int> > ok(k);
for (int i = 0; i < k; i++) ok[i].resize(verts[i].size());
vector <map <int, int> > ss(k);
for (int i = 0; i < k; i++) {
for (int j= 0; j < (int) verts[i].size(); j++) {
ss[i][verts[i][j]] = j;
}
}
vector <int> none(k);
int s = 0;
for (int i = 0; i < n; i++) s += cnt[i];
vector <int> pw(s + 1);
vector <int> iw(s + 1);
pw[0] = 1;
for (int i = 1; i <= s; i++) pw[i] = mul(pw[i - 1], 2);
for (int i = 1; i <= s; i++) {
pw[i]--;
iw[i] = inv(pw[i]);
}
function<void(int,int)> solve = [&] (int v, int pr) {
set <int> here;
set <int> now;
map <int, int> iid;
int lul = 0;
for (int z : verts[v]) {
here.insert(z);
now.insert(z);
iid[z] = lul;
lul++;
}
int none_he = 1;
map <int, int> zz;
vector <int> ch;
for (int x : g[v]) {
if (x != pr) {
ch.push_back(x);
solve(x, v);
int sum = none[x];
int id = 0;
for (int z : verts[x]) {
if (!here.count(z)) {
add(sum, ok[x][id]);
} else {
now.erase(z);
}
id++;
}
zz[x] = sum;
none_he = mul(none_he, sum);
}
}
none[v] = none_he;
for (int x : now) {
ok[v][iid[x]] = mul(none_he, pw[cnt[x]]);
}
for (int z : verts[v]) {
if (now.count(z)) continue;
int me = 1;
int bruh = 0;
for (int x : ch) {
if (ss[x].count(z)) {
bruh++;
me = mul(me, ok[x][ss[x][z]]);
} else {
me = mul(me, zz[x]);
}
}
for (int i = 0; i < bruh - 1; i++) {
me = mul(me, iw[cnt[z]]);
}
ok[v][iid[z]] = me;
}
none[v] = none_he;
};
solve(0, -1);
int sum = none[0];
for (auto c : ok[0]) {
add(sum, c);
}
return sum;
}
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
string s;
cin >> s;
int n = (int) s.size();
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
dp[i][j] = false;
}
}
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
if (i + 1 < n && s[i] == s[i + 1]) dp[i][i + 1] = true;
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1];
} else {
dp[i][j] = false;
}
}
}
for (int i = 0; i < n; i++) dsu[i] = i;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (dp[i][j]) {
uni(i, j);
}
}
}
vector <int> id(n);
vector <int> st;
for (int i = 0; i < n; i++) {
id[i] = get(i);
st.push_back(id[i]);
}
sort(st.begin(), st.end());
st.resize(unique(st.begin(), st.end()) - st.begin());
int m = (int) st.size();
vector <vector <int> > g(m);
vector <int> cnt(m);
auto add_edge = [&] (int a, int b) {
g[a].push_back(b);
g[b].push_back(a);
};
for (int i = 0; i < n; i++) {
id[i] = lower_bound(st.begin(), st.end(), id[i]) - st.begin();
cnt[id[i]]++;
}
for (int i = 0; i + 1 < n; i++) {
if (s[i] != s[i + 1]) {
add_edge(id[i], id[i + 1]);
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
if (dp[i + 1][j - 1]) {
if (s[i] != s[j]) {
add_edge(id[i], id[j]);
}
}
}
}
for (int i = 0; i < m; i++) {
sort(g[i].begin(), g[i].end());
g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin());
}
cout << solve_chordal(g, cnt) << '\n';
}
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class PALINDEQ{
//SOLUTION BEGIN
int max = 2002;
int[] pw, ipw;//pw[i] => 2^i-1, ipw[i] = 1/(2^i-1)
void pre() throws Exception{
pw = new int[max];
ipw = new int[max];
pw[0] = ipw[0] = 1;
for(int i = 1; i< max; i++)pw[i] = mul(pw[i-1], 2);
for(int i = 1; i< max; i++){
pw[i]--;
ipw[i] = pow(pw[i], MOD-2);
}
}
void solve(int TC) throws Exception{
String S = n();
int N = S.length();
int[] set = java.util.stream.IntStream.range(0, N).toArray();
String T = pad(S);
int[][] edge = new int[2*N+1][];
int edgeCount = 0;
//Building chordal graph
for(int center = 0; center < T.length(); center++){
for(int le = center, ri = center; le >= 0 && ri < T.length(); le--, ri++){
if(T.charAt(le) != T.charAt(ri)){
edge[edgeCount++] = new int[]{le/2, ri/2};//edges of chordal graph, Adjusting indices from position in T to position in S
break;
}else{
if(T.charAt(le) == sp)continue;
set[find(set, le/2)] = find(set, ri/2);//merging
}
}
}
int[] map = new int[N];
int node = 0;
for(int i = 0; i< N; i++)if(find(set, i) == i)map[i] = node++;
for(int i = 0; i< N; i++)if(find(set, i) != i)map[i] = map[find(set, i)];
boolean[][] adjMat = new boolean[node][node];
for(int i = 0; i< edgeCount; i++)adjMat[map[edge[i][0]]][map[edge[i][1]]] = true;
edgeCount = 0;
int[] from = new int[node*node], to = new int[node*node];
for(int i = 0; i< node; i++)
for(int j = i+1; j< node; j++)
if(adjMat[i][j]){
from[edgeCount] = i;
to[edgeCount] = j;
edgeCount++;
}
int[] cnt = new int[node];
for(int i = 0; i< N; i++)cnt[map[find(set, i)]]++;//counting number of positions represented by each position in chordal graph
int[][] g = make(node, edgeCount, from, to, true);
pn(calc(g, cnt));
}
//Returns number of independent sets, where ith node represent cnt[i] positions in original string
long calc(int[][] e, int[] cnt){
//assert e is chordal
int n = e.length;
//Construction of clique tree begins, as explained in paper
int[] mark = new int[n];
TreeSet<int[]> set = new TreeSet<>((int[] i1, int[] i2) -> {
if(i1[0] != i2[0])return Integer.compare(i1[0], i2[0]);
return Integer.compare(i1[1], i2[1]);
});
for(int i = 0; i< n; i++)set.add(new int[]{-mark[i], i});
ArrayList<int[]> cliqueTreeEdges = new ArrayList<>();
ArrayList<Integer>[] who = new ArrayList[n];
for(int i = 0; i< n; i++)who[i] = new ArrayList<>();
ArrayList<Integer>[] cliqueNodeSet = new ArrayList[1+n];
int K = 0;//Number of nodes in clique tree
cliqueNodeSet[K++] = new ArrayList<>();//Adding an empty clique, for ease of computation at the end, we only need to think about empty
int[] cliq = new int[1+n];
Arrays.fill(cliq, -1);
cliq[n] = 0;
int[] last = new int[1+n];
Arrays.fill(last, n);
int prev = n + 1;
for (int i = n - 1; i >= 0; i--) {
int x = set.pollFirst()[1];
if (mark[x] <= prev) {
ArrayList<Integer> cur = new ArrayList<>();
for(int y:who[x])cur.add(y);
cur.add(x);
cliqueNodeSet[K++] = cur;
cliqueTreeEdges.add(new int[]{cliq[last[x]], K-1});
} else {
cliqueNodeSet[K-1].add(x);
}
for (int y : e[x]) {
if (cliq[y] != -1) continue;
who[y].add(x);
set.remove(new int[]{-mark[y], y});
mark[y]++;
set.add(new int[]{-mark[y], y});
last[y] = x;
}
prev = mark[x];
cliq[x] = K-1;
}
cliqueNodeSet = Arrays.copyOf(cliqueNodeSet, K);
int[] par = new int[K];
ArrayList<Integer>[] cliqueTree = new ArrayList[K];
for(int i = 0; i< K; i++)cliqueTree[i] = new ArrayList<>();
for(int[] edge:cliqueTreeEdges){
par[edge[1]] = edge[0];
cliqueTree[edge[0]].add(edge[1]);
}
//Clique Tree ready, cliques stored in CliqueNodeSet
int[] none = new int[K];//none[i] -> Number of independent subsets if no vertex in clique of ith clique is chosen
int[][] chosen = new int[K][];//chosen[i][j] -> Number of independent subsets if j-th vertex in clique of ith clique is chosen4
for(int i = 0; i< K; i++)chosen[i] = new int[cliqueNodeSet[i].size()];
HashMap<Integer, Integer>[] map = new HashMap[K];//map[i] -> to quickly find position of a node in a cliqueNodeSet[i]
for(int i = 0; i< K; i++)map[i] = new HashMap<>();
for(int i = 0; i< K; i++)
for(int j = 0; j< cliqueNodeSet[i].size(); j++)
map[i].put(cliqueNodeSet[i].get(j), j);
int[] class3 = new int[K];//class3[u] = Number of ways to select independent subsets in subtree of clique node u, such that no node shared between node u and its parent are present in subtree
compute(cliqueTree, cliqueNodeSet, map, cnt, none, chosen, class3, 0, -1);
return none[0];
}
void compute(ArrayList<Integer>[] cliqueTree, ArrayList<Integer>[] cliqueNodeSet, HashMap<Integer, Integer>[] map, int[] chordalWeights, int[] none, int[][] chosen, int[] class3, int u, int p){
//computing for children
for(int v:cliqueTree[u])if(v != p)compute(cliqueTree, cliqueNodeSet, map, chordalWeights, none, chosen, class3, v, u);
boolean[] unique = new boolean[cliqueNodeSet[u].size()];
Arrays.fill(unique, true);
none[u] = 1;
for(int v:cliqueTree[u]){
if(v == p)continue;
int sum = none[v];
int ptr = 0;
for(int node:cliqueNodeSet[v]){
int ind = map[u].getOrDefault(node, -1);
if(ind != -1)unique[ind] = false;
else
sum = add(sum, chosen[v][ptr]);//equivalent to chosen[v][map[v].get(node)]
ptr++;
}
class3[v] = sum;
none[u] = mul(none[u], class3[v]);
}
for(int i = 0; i< cliqueNodeSet[u].size(); i++) {
int node = cliqueNodeSet[u].get(i);
if (unique[i]) {
//Chordal graph node not shared with any children, class
chosen[u][i] = mul(none[u], pw[chordalWeights[node]]);
} else {
int ways = 1;
int numDumplicated = 0;
//Chordal graph node appearing in atleast one child too.
for (int v : cliqueTree[u]) {
if(v == p)continue;
int ind = map[v].getOrDefault(node, -1);
if(ind == -1){
//child v clique doesn't contain node
ways = mul(ways, class3[v]);
}else{
numDumplicated++;
ways = mul(ways, chosen[v][ind]);
}
}
while (numDumplicated-- > 1)ways = mul(ways, ipw[chordalWeights[node]]);
chosen[u][i] = ways;
}
}
}
final int MOD = 998244353;
int pow(int a, int p){
int ans = 1;
for(; p>0; p>>=1){
if((p&1) == 1)ans = mul(ans, a);
a = mul(a, a);
}
return ans;
}
int mul(int... o){
long ans = 1;
for(int v:o)ans = ans*v%MOD;
return (int)ans;
}
int add(int... o){
int ans = 0;
for(int v:o)ans = (ans+v >= MOD)?(ans+v-MOD):(ans+v);
return ans;
}
char sp = '$';
String pad(String s){
StringBuilder st = new StringBuilder(sp);
for(int i = 0; i< s.length(); i++){
st.append(sp);
st.append(s.charAt(i));
}
return st.toString();
}
int[][] make(int n, int e, int[] from, int[] to, boolean f){
int[][] g = new int[n][];int[]cnt = new int[n];
for(int i = 0; i< e; i++){
cnt[from[i]]++;
if(f)cnt[to[i]]++;
}
for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
for(int i = 0; i< e; i++){
g[from[i]][--cnt[from[i]]] = to[i];
if(f)g[to[i]][--cnt[to[i]]] = from[i];
}
return g;
}
int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new PALINDEQ().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
VIDEO EDITORIAL:
Feel free to share your approach. Suggestions are welcomed as always. 
