PROBLEM LINK:
Setter: Nishant Shah
Tester: Kirill Gulin and Taranpreet Singh
Editorialist: Taranpreet Singh
DIFFICULTY
Medium
PREREQUISITES
String Data Structures
PROBLEM
Given a list of N distinct strings, each string representing a chapter in a book. Nishant has to read all chapters. For each chapter, one of the following things can happen.
- Current chapter S_i can be written as A+S_j+B+S_k + C where S_j and S_k are the chapters Nishant has already read. Nishant has to read only |A|+|B|+|C| characters.
- Current chapter S_i can be written as A+S_j+B where S_j is a chapter Nishant has already read. Nishant has to read only |A|+|B| characters.
- Current chapter S_i is read completely, reading |S_i| characters.
Nishant wants to read all chapters while minimizing the number of characters read. Find the minimum number of characters to be read.
QUICK EXPLANATION
- Minimizing the total characters to be read is the same as maximizing |S_j|+|S_k| in the first case and |S_j| in the second case.
- For each string S_i, we need to find maximum value of |S_j|+|S_k| where S_i can be written as A+S_j+B+S_k+C (and similarly for second case).
- Since two strings S_j and S_k must not overlap, we can divide S_i into two parts where prefix part of S_i contains S_j and suffix part of S_i contains S_k.
- We need to compute the maximum length of S_j for each prefix of S_i and the maximum length of S_k for each suffix of S_i (which is a similar problem after reversing strings)
- Aho corasick can be used to compute the maximum length of S_j present in each prefix of S_i
EXPLANATION
First of all, let’s add an empty string into S, calling it S_0. Now, the second case can be written as A+S_j+B+S_0+C where S_0 and C are empty strings. The third case can be written as A + S_0+B+S_0+C where all strings except A are empty.
Hence, after adding an empty string into S, we can always write a string S_i as A+S_j+B+S_k+C where A, B, C can be empty or non-empty strings.
How to minimize the number of characters?
We see that when dividing S_i into A+S_j+B+S_k+C, we have to read |A|+|B|+|C| characters. We need to minimize it. But |S_i| is fixed. So minimizing |A|+|B|+|C| is equivalent to maximizing |S_i| - (|A|+|B|+|C|) = |S_j|+|S_k|.
Hence, for each string S_i, if we can find a pair of string (S_j, S_k) such that both of them appear as non-overlapping substrings of S_i, then we can skip reading |S_j|+|S_k| characters. Let’s call this quantity the overlap for string S_i
Why Non-overlapping is important?
In the previous section, we saw that S_j and S_k are non-overlapping substrings of S_i. The fact that they are non-overlapping, implies that we can divide S_i into two parts X+Y such that X contains S_j and Y contains S_k.
We note that X must be a prefix of S_i and Y must be the suffix of S_i having length |S_i|-|X|.
Hence, We need to consider each prefix X of S_i and compute the maximum length of S_j present in X and compute the maximum length of S_k present in the suffix of S_i.
We can see that computing the length of longest string from S present in each suffix of S_i is equivalent to computing the length of longest string from S present in each prefix of S_i after reversing all strings.
Hence, we can compute the maximum length of strings appearing in suffices in the same way as prefixes.
Reduced Problem
Given a set of strings S and a string T, considering each prefix of T, find the length of the longest string present in S which appears in the current prefix of T.
This is a well-known problem. In Aho corasick tree, let’s store another value L_x for each node x, denoting the length of the longest string in S, which appears as a suffix of the string represented by the current node.
We first insert all strings into aho corasick. After inserting a string, we update L_x for the node after processing all characters of the current string. Now, while building suffix links, we update L_x = max(L_x, L_{link_x}).
Now, while processing each character of T from left to right one by one, L_x for current node x denote the length of the largest string present in S which ends at T.
Since transitions in aho corasick tree are amortized constant time, this does not take more than O(\sum |S_i|*A + |T|) time.
Applying reduced problem to our problem
Let’s add all strings in aho corasick tree and build suffix links and compute for each node the length of the longest string in S appearing in the suffix of string represented by the node.
Now, process string S_i character by character from left to right. If the current node after c characters is node x, then L_x denotes the length of the longest string in S which appears in the prefix of length c of S_i.
Footnote
- Ideally, we only wanted to insert strings strictly smaller in length into aho corasick tree before processing S_i and then add S_i, but Aho corasick is an offline algorithm. We need to add all strings before building suffix links. Hence, we added all strings beforehand
- This doesn’t affect us for a string with a length larger than S_i do not affect nodes reachable when processing S_i
- Only issue is that when we consider the largest prefix of S_i, which is the whole string, we get |S_i| instead. Hence, we take L_{link_x} instead of L_x to correct this issue.
- In case you are facing difficulty understanding this (assuming you understand Aho corasick as explained here), feel free to refer to my solution, where I have added comments.
- There also exists a Suffix Automation solution, which you may refer to in Tester’s solution section.
- There also exists a Suffix Array plus DSU trick solution for this problem, which you may refer to in Setter’s solution
TIME COMPLEXITY
The time complexity of above solution is O(\sum |S_i| * A) per test case.
SOLUTIONS
Setter's Solution
//SA with dsu trick
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
/*
* Time Complexity: Suffix Array: O(N + Character_Set_Size) time and space //
128 --- ASCII
* LCP: O(N) time and space
* Usage:
* 1. Suffix Array (returns s.size() elements, NOT considering
0-length/empty suffix)
* auto sa = suffix_array(s); // s is the input string with ASCII
characters
* auto sa_wide_char = suffix_array(s, LIM); // LIM = max(s[i]) + 2,
s is the string with arbitary big characters.
* 2. LCP:
* auto lcp = LCP(s, suffix_array(s)); // returns s.size() elements,
where lcp[i]=LCP(sa[i], sa[i+1])
* Status: Tested (DMOJ: ccc03s4, SPOJ: SARRAY (100pts), Yosupo's: Suffix Array
& Number of Substrings, CodeForces EDU
*/
// Based on: Rickypon, https://judge.yosupo.jp/submission/10105
void induced_sort(const std::vector<int>& vec, int val_range,
std::vector<int>& SA, const std::vector<bool>& sl,
const std::vector<int>& lms_idx) {
std::vector<int> l(val_range, 0), r(val_range, 0);
for (int c : vec) {
if (c + 1 < val_range) ++l[c + 1];
++r[c];
}
std::partial_sum(l.begin(), l.end(), l.begin());
std::partial_sum(r.begin(), r.end(), r.begin());
std::fill(SA.begin(), SA.end(), -1);
for (int i = (int)lms_idx.size() - 1; i >= 0; --i)
SA[--r[vec[lms_idx[i]]]] = lms_idx[i];
for (int i : SA)
if (i >= 1 && sl[i - 1]) SA[l[vec[i - 1]]++] = i - 1;
std::fill(r.begin(), r.end(), 0);
for (int c : vec) ++r[c];
std::partial_sum(r.begin(), r.end(), r.begin());
for (int k = (int)SA.size() - 1, i = SA[k]; k >= 1; --k, i = SA[k])
if (i >= 1 && !sl[i - 1]) {
SA[--r[vec[i - 1]]] = i - 1;
}
}
std::vector<int> SA_IS(const std::vector<int>& vec, int val_range) {
const int n = vec.size();
std::vector<int> SA(n), lms_idx;
std::vector<bool> sl(n);
sl[n - 1] = false;
for (int i = n - 2; i >= 0; --i) {
sl[i] = (vec[i] > vec[i + 1] || (vec[i] == vec[i + 1] && sl[i + 1]));
if (sl[i] && !sl[i + 1]) lms_idx.push_back(i + 1);
}
std::reverse(lms_idx.begin(), lms_idx.end());
induced_sort(vec, val_range, SA, sl, lms_idx);
std::vector<int> new_lms_idx(lms_idx.size()), lms_vec(lms_idx.size());
for (int i = 0, k = 0; i < n; ++i)
if (!sl[SA[i]] && SA[i] >= 1 && sl[SA[i] - 1]) {
new_lms_idx[k++] = SA[i];
}
int cur = 0;
SA[n - 1] = cur;
for (size_t k = 1; k < new_lms_idx.size(); ++k) {
int i = new_lms_idx[k - 1], j = new_lms_idx[k];
if (vec[i] != vec[j]) {
SA[j] = ++cur;
continue;
}
bool flag = false;
for (int a = i + 1, b = j + 1;; ++a, ++b) {
if (vec[a] != vec[b]) {
flag = true;
break;
}
if ((!sl[a] && sl[a - 1]) || (!sl[b] && sl[b - 1])) {
flag = !((!sl[a] && sl[a - 1]) && (!sl[b] && sl[b - 1]));
break;
}
}
SA[j] = (flag ? ++cur : cur);
}
for (size_t i = 0; i < lms_idx.size(); ++i) lms_vec[i] = SA[lms_idx[i]];
if (cur + 1 < (int)lms_idx.size()) {
auto lms_SA = SA_IS(lms_vec, cur + 1);
for (size_t i = 0; i < lms_idx.size(); ++i) {
new_lms_idx[i] = lms_idx[lms_SA[i]];
}
}
induced_sort(vec, val_range, SA, sl, new_lms_idx);
return SA;
}
std::vector<int> suffix_array(const std::string& s, const char first = 'a',
const char last = 'z') {
std::vector<int> vec(s.size() + 1);
std::copy(std::begin(s), std::end(s), std::begin(vec));
for (auto& x : vec) x -= (int)first - 1;
vec.back() = 0;
auto ret = SA_IS(vec, (int)last - (int)first + 2);
ret.erase(ret.begin());
return ret;
}
// Author: https://codeforces.com/blog/entry/12796?#comment-175287
// Uses kasai's algorithm linear in time and space
std::vector<int> LCP(const std::string& s, const std::vector<int>& sa) {
int n = s.size(), k = 0;
std::vector<int> lcp(n), rank(n);
for (int i = 0; i < n; i++) rank[sa[i]] = i;
for (int i = 0; i < n; i++, k ? k-- : 0) {
if (rank[i] == n - 1) {
k = 0;
continue;
}
int j = sa[rank[i] + 1];
while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
lcp[rank[i]] = k;
}
lcp[n - 1] = 0;
return lcp;
}
class DSU {
public :
int n;
vector <int> root, sz , L;
DSU(int _n) : n(_n) {
root.resize(n);
sz.resize(n);
L.resize(n);
for (int i = 0; i < n; i++) {
root[i] = i;
sz[i] = 1;
L[i] = i;
}
}
int get_root(int u) {
return (u == root[u]? u: (root[u] = get_root(root[u])));
}
bool connected(int u, int v) {
if (get_root(u) == get_root(v))
return true;
return false;
}
void merge(int u, int v) {
if (connected(u, v))
return ;
u = get_root(u);
v = get_root(v);
if (sz[v] > sz[u])
swap(u, v);
root[v] = u;
sz[u] += sz[v];
L[u] = min(L[u],L[v]);
}
int comp_size(int u) {
u = get_root(u);
return sz[u];
}
int get_L(int u) {
u = get_root(u);
return L[u];
}
int get_R(int u) {
u = get_root(u);
return L[u] + sz[u] - 1;
}
};
const int N = 3e6 + 10; //(Length + n)
vector<int> len_index[N];
vector<pii> connect[N];
vector<int> get_max_suffix(vector<string> & s, vector<vi> & str_to_sa_index)
{
int n = s.size();
string S;
f(i,n)
{
S += '_';
S += s[i];
}
auto sa = suffix_array(S,'_','z');
auto lcp = LCP(S,sa);
int nn = S.length();
//sa_ind_to_str[i] denotes ith index in string S corresponds to which string and its index
pair<int,int> S_to_str[nn];
int ptr = 0;
f(i,n)
{
ptr++;
f(j,s[i].length()) S_to_str[ptr++] = {i,j};
}
f(i,nn) str_to_sa_index[S_to_str[sa[i]].F][S_to_str[sa[i]].S] = i;
//suf[i] = maximum length string starting from index i
vector<int> suf(nn,0);
DSU open_to_move(nn) , updated(nn);
f(i,n) len_index[(int)s[i].length()].pb(i);
f(i,nn - 1) connect[lcp[i]].pb({i,i+1});
for(int i=nn;i>=1;i--)
{
for(auto x : connect[i])
open_to_move.merge(x.F,x.S);
for(auto x : len_index[i])
{
int ind = str_to_sa_index[x][0];
int L = open_to_move.get_L(ind);
int R = open_to_move.get_R(ind);
int ii = ind + 1;
//we can update non-updated entries in [L,ind-1] and [ind+1,R] by i
while(ii <= R)
{
if(suf[ii] > 0)
{
ii = updated.get_R(ii) + 1;
}
else
{
suf[ii] = i;
if(ii > 0 && suf[ii - 1] > 0) updated.merge(ii - 1,ii);
if(ii < nn - 1 && suf[ii + 1] > 0) updated.merge(ii,ii + 1);
}
}
ii = ind - 1;
while(ii >= L)
{
if(suf[ii] > 0)
{
ii = updated.get_L(ii) - 1;
}
else
{
suf[ii] = i;
if(ii > 0 && suf[ii - 1] > 0) updated.merge(ii - 1,ii);
if(ii < nn - 1 && suf[ii + 1] > 0) updated.merge(ii,ii + 1);
}
}
}
connect[i].clear();
len_index[i].clear();
}
return suf;
}
void solve()
{
int n;
cin >> n;
vector<string> s(n);
f(i,n) cin >> s[i];
vector<vi> str_to_sa_index(n);
f(i,n) f(j,s[i].length()) str_to_sa_index[i].pb(-1);
auto suf = get_max_suffix(s , str_to_sa_index);
vector<vi> str_to_sa_index_rev = str_to_sa_index;
f(i,n) reverse(all(s[i]));
auto pref = get_max_suffix(s , str_to_sa_index_rev);
int res = 0;
f(i,n)
{
int len = s[i].length();
//suffix[i] = string starting at ith index
//prefix[i] = string ending at ith index
vi prefix(len,0),suffix(len,0);
//update prefix and suffix to their correct values
for(int j=0;j<len;j++)
prefix[j] = pref[str_to_sa_index_rev[i][len - 1 - j]];
for(int j=1;j<len;j++)
prefix[j] = max(prefix[j] , prefix[j-1]);
for(int j=0;j<len;j++)
suffix[j] = suf[str_to_sa_index[i][j]];
for(int j=len-2;j>=0;j--)
suffix[j] = max(suffix[j], suffix[j+1]);
int left = len;
left = min(left,len - suffix[0]);
left = min(left,len - prefix[len - 1]);
for(int i=0;i<len-1;i++)
left = min(left,len - prefix[i] - suffix[i + 1]);
res += left;
}
cout << res << '\n';
}
signed main()
{
fast;
int t = 1;
cin >> t;
while(t--)
solve();
}
Tester's Solution
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#ifndef DEBUG
const int maxN = 4 * (int)1e6 + 2e5 + 228;
#else
const int maxN = 2e5;
#endif
int to[maxN][27];
int link[maxN];
int len[maxN];
int last = 0;
int sz = 1;
void add_letter(int c) {
int p = last;
last = sz++;
len[last] = len[p] + 1;
for(; to[p][c] == 0; p = link[p]) {
to[p][c] = last;
}
if (to[p][c] == last) {
link[last] = 0;
return;
}
int q = to[p][c];
if (len[q] == len[p] + 1) {
link[last] = q;
return;
}
int cl = sz++;
memcpy(to[cl], to[q], sizeof(to[q]));
link[cl] = link[q];
len[cl] = len[p] + 1;
link[last] = link[q] = cl;
for (; to[p][c] == q; p = link[p]) {
to[p][c] = cl;
}
}
int n;
vector<int> edge[maxN];
int max_len[maxN];
int Q[maxN];
void solve() {
cin >> n;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
sort(s.begin(), s.end(), [&](string& a, string& b) {
if (a.size() != b.size()) return (int)a.size() < (int)b.size();
return a < b;
});
s.erase(unique(s.begin(), s.end()), s.end());
vector<vector<int>> max_suf(s.size());
vector<vector<int>> max_pref(s.size());
for (int i = 0; i < s.size(); i++) {
max_suf[i].resize(s[i].size());
max_pref[i].resize(s[i].size());
}
for (int z = 0; z < 2; z++) {
for (int i = 0; i < sz; i++) {
memset(to[i], 0, sizeof to[i]);
max_len[i] = 0;
len[i] = link[i] = 0;
}
sz = 1;
last = 0;
for (string& t : s) {
for (char& c : t) {
add_letter(c - 'a');
}
add_letter(26);
}
for (int i = 0; i < sz; i++) {
edge[i].clear();
}
for (int i = 0; i < sz; i++) {
if (i != 0) {
edge[link[i]].emplace_back(i);
}
}
for (string& t : s) {
int cur = 0;
for (char& c : t) {
cur = to[cur][c - 'a'];
}
max_len[cur] = max(max_len[cur], (int)t.size());
}
int topQ = 0;
Q[topQ++] = 0;
for (int i = 0; i < topQ; i++) {
int v = Q[i];
for (int to : edge[v]) {
max_len[to] = max(max_len[to], max_len[v]);
Q[topQ++] = to;
}
}
for (int i = 0; i < s.size(); i++) {
int cur = 0;
for (int t = 0; t < s[i].size(); t++) {
cur = to[cur][s[i][t] - 'a'];
if (t == (int)s[i].size() - 1) {
cur = link[cur];
}
if (z == 0) {
max_suf[i][t] = max_len[cur];
}
else {
max_pref[i][s[i].size() - 1 - t] = max_len[cur];
}
}
}
for (string& t : s) {
reverse(t.begin(), t.end());
}
}
ll ans = 0;
for (int i = 0; i < s.size(); i++) {
int mn = (int)s[i].size();
int max_take = 0;
for (int d = s[i].size() - 1; d >= 0; d--) {
mn = min(mn, (int)s[i].size() - max_take - max_suf[i][d]);
max_take = max(max_take, max_pref[i][d]);
}
ans += mn;
}
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("input.txt", "r", stdin);
int tst;
cin >> tst;
while (tst--) {
solve();
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class HLPUTKRSH{
//SOLUTION BEGIN
int MAX = (int)2000000;
AhoCorasick aho = new AhoCorasick(26, MAX), ahorev = new AhoCorasick(26, MAX);
void pre() throws Exception{}
void solve(int TC) throws Exception{
//Reading input
int N = ni();
char[][] S = new char[N][];
for(int i = 0; i< N; i++)S[i] = n().toCharArray();
//Emptying aho corasick trees since I'm using trees as global variables
//aho is aho corasick tree for given strings, while ahorev is aho corasick tree for reversed strings
// Do refer findMax function in Aho corasick tree, rest is template stuff
aho.reset();
ahorev.reset();
//Adding strings in aho trees.
for(int i = 0; i< N; i++){
aho.addString(S[i]);
_reverse(S[i]);
ahorev.addString(S[i]);
_reverse(S[i]);//Reversing to obtain original string
}
//Building suffix links, do pay attention to line 129 and 165
aho.buildSuffixLinks();
ahorev.buildSuffixLinks();
long ans = 0;
for(int i = 0; i< N; i++){
//Finding length of longest strings in S ending at each prefix of string S_i
int[] f1 = aho.findMax(S[i]);
_reverse(S[i]);
//Finding length of longest strings in S ending at each suffix of string S_i
int[] f2 = ahorev.findMax(S[i]);
_reverse(S[i]);
//Reversing actually lead to this array being reversed.
_reverse(f2);
//Taking prefix max, since largest string in prefix[j-1] is also present in prefix[j]
for(int j = 1; j< S[i].length; j++)f1[j] = Math.max(f1[j], f1[j-1]);
//Taking suffix max, since largest string in suffix[j+1] is also present in suffix[j]
for(int j = S[i].length-2; j >= 0; j--)f2[j] = Math.max(f2[j], f2[j+1]);
//Computing the maximum overlap
int max = 0;
for(int j = 0; j< S[i].length; j++){
max = Math.max(max, f1[j]);
max = Math.max(max, f2[j]);
//Considering to split S_i into prefix of length j+1
if(j+1 < S[i].length)max = Math.max(max, f1[j]+f2[j+1]);
}
//Adding characters to be read.
ans += S[i].length-max;
}
pn(ans);
}
void dbg(Object... o){System.out.println(Arrays.deepToString(o));}
//Function to reverse the string.
void _reverse(char[] c){
for(int i = 0, j = c.length-1; i< j; i++, j--){
char tmp = c[i];
c[i] = c[j];
c[j] = tmp;
}
}
void _reverse(int[] c){
for(int i = 0, j = c.length-1; i< j; i++, j--){
int tmp = c[i];
c[i] = c[j];
c[j] = tmp;
}
}
class AhoCorasick{
int root, sentinal, ID, A, maxSize;
int[] next, fail, hit;
public AhoCorasick(int A, int maxSize){
this.A = A;
this.maxSize = maxSize+2;
next = new int[A*this.maxSize];
fail = new int[this.maxSize];
hit = new int[this.maxSize];
reset();
}
int newNode(){
fail[ID] = -1;
for(int a = 0; a< A; a++)next[A*ID+a] = -1;
hit[ID] = 0;
return ID++;
}
void reset(){
ID = 0;
sentinal = newNode();
root = newNode();
fail[root] = sentinal;
for(int i = 0; i< this.A; i++)next[sentinal*this.A+i] = root;
}
int f(char ch){return ch-'a';}
void addString(char[] pat){
int node = root;
for(char ch:pat){
int c = f(ch);
if(next[node*A+c] == -1)next[node*A+c] = newNode();
node = next[node*A+c];
}
//hit[node] denotes the length of largest string ending at node
hit[node] = Math.max(hit[node], pat.length);
}
void buildSuffixLinks(){
int[] Q = new int[ID];
int c = 0;
Q[c++] = root;
for(int r = 0; r< c; r++){
int node = Q[r];
for(int i = 0; i< A; i++){
int nxt = next[node*A+i];
if(nxt == -1)continue;
Q[c++] = nxt;
for(int to = fail[node]; true; to = fail[to]){
int fch = next[to*A+i];
if(fch != -1){
fail[nxt] = fch;
hit[nxt] = Math.max(hit[nxt], hit[fch]);// Equivalent to L[x] = max(L[x], L[link[x]]) in editorial
break;
}
}
}
}
}
int[][] suffixLinkTree(){
//call buildSuffixLinks() first
int cnt = 0;
int[][] e = new int[ID][];
for(int i = 0; i< ID; i++)if(fail[i] != -1)e[cnt++] = new int[]{fail[i], i};
return Arrays.copyOf(e, cnt);
}
void precomputeNextMoves(){
for(int i = 0; i < ID; i++)
for(int a = 0; a < A; a++)
if(next[i*A+a] == -1)next[i*A+a] = next[fail[i]*A+a];
}
int move(int node, char ch){
int c = ch-'a';
while(next[node*A+c] == -1)node = fail[node];
return next[node*A+c];
}
// Function, to consider string represented by text character array and compute maximum lengths for each prefix of text
int[] findMax(char[] text){
int[] hits = new int[text.length];
int node = root;
for(int i = 0; i< text.length; i++){
int ch = f(text[i]);
for(int to = node; true; to = fail[to]){
int fch = next[to*A+ch];
if(fch != -1){
node = fch;
hits[i] = hit[node];
if(hits[i] == text.length)hits[i] = hit[fail[node]];//Special case as mentioned in footnotes
break;
}
}
}
return hits;
}
}
//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 HLPUTKRSH().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;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 