### saisumit's blog

By saisumit, history, 4 years ago, Hello people , I am stuck at this problem SITTING ARRANGEMENTS , i read the editorial but couldn't figure why the solution works, if anyone can provide an explanation/proof for the solution , it would be great. Thanks in advance :)

This is the author's solution

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll solve(ll n,ll m)
{
if(n==0||m==0)
return 0;
else if(n%2==0&&m%2==0)
return solve(n/2,m/2); // Halving both dimensions doesn't change the number of tiles
else if(n%2==0&&m%2==1)
return (n+solve(n/ 2,m/ 2));// Use a row of 1x1 tiles
else if(n%2==1&&m%2==0)
return (m+solve(n/ 2,m/ 2));// Use a column of 1x1 tiles
else
return (n+m-1+solve(n/2,m/2)); //ROW OR COLUMN (WHICHEVER OVERLAP)
}
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n,m,i,j,p,q,r;
cin>>n>>m;
cout<<solve(n,m)<<endl;
}
} By saisumit, history, 5 years ago,  dp,
By saisumit, history, 5 years ago, from past week , i was looking for a good source for reading suffix- automaton in english but couldnt find even one good post, so i ultimately decided to read e-maxx translation and after continuous reading and taking examples , i was able to figure out the algorithm .

So now i have compiled the article , added codes which were not there and finally came up with this blog

https://saisumit.wordpress.com/2016/01/26/suffix-automaton/

Do read the above blog , I know there will be certain mistakes in the article but i want you to let me know of my mistakes, hope you enjoy the article and do comment By saisumit, history, 6 years ago, Can anyone please write a nice tutorial on suffix automaton , i tried my best to learn it from e-maxx and http://codeforces.com/blog/entry/20861 , but couldn't understand it completely, it will be great for many if anyone could write a good tutorial on this topic. If u are too tired to write a tutorial please explain the construction done in the example taken by emaxx or any example u find suitable ... By saisumit, history, 6 years ago, I am not able to figure out where i am getting wrong on this problem ...

https://www.codechef.com/problems/TACHEMIS

Your code here...

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ff first
#define ss second
typedef long long ll;

// Transform S into T.
// For example, S = "abba", T = "^#a#b#b#a#$". // ^ and$ signs are sentinels appended to each end to avoid bounds checking
vector<pair<char , long long >  > preProcess(  vector<pair<char , long long >  >& narr) {
long long n = narr.size();
vector<pair<char,long long > > arr ;
// if (n == 0) return "^$"; arr.pb(make_pair('^',0)); for (long long i = 0; i < n; i++) { arr.pb(make_pair('#',0)); arr.pb(make_pair(narr[i].ff , narr[i].ss)); } arr.pb(make_pair('#', 0)); arr.pb(make_pair('$', 0));

return arr;
}
void longestPalindrome(   vector<pair<char , long long >  > & arr ) {

vector<pair<char , long long >  > T = preProcess(arr);

long long n = T.size();
long long *P = new long long [n];

vector<ll>sum(n);

long long C = 0, R = 0;
for (long long i = 1; i < n-1; i++) {

long long i_mirror = 2*C-i; // equals to i' = C - (i-C)

P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;

if( P[i] == R-i && R > i )
for( int k = i + 1 ; k<= R - i ; k++ )
sum[i]+=T[k].ss;

else if(P[i] == P[i_mirror] && R > i )
sum[i] = sum[i_mirror];

// Attempt to expand palindrome centered at i
while (T[i + 1 + P[i]].ff == T[i - 1 - P[i]].ff && T[i + 1 + P[i]].ss == T[i - 1 - P[i]].ss )
{ sum[i] +=  T[i - 1 - P[i]].ss ;
P[i]++ ; }

if((T[i + 1 + P[i]].ff == T[i - 1 - P[i]].ff ))
{ sum[i] +=  min( T[i + 1 + P[i]].ss , T[i - 1 - P[i]].ss ) ;
P[i]++ ;
}

// If palindrome centered at i expand past R,
// adjust center based on expanded palindrome.
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
long long ans = 0 ;

for( long long i=0 ; i  < n ; i ++)
{  if ( T[i].ff - 'A' >= 0 && T[i].ff - 'A' <=25)
sum[i] += (T[i].ss) * (T[i].ss + 1) / 2 ;

ans+=sum[i];
// cout<< T[i].ff<<"  "<<T[i].ss<< " P[i]  "<< P[i] <<" Sum[i]  "<<sum[i]<<endl;

}
cout<<ans<<endl;

delete[] P;

}

int  main()
{  cin.tie(0) ;
long long t;
string s;
cin>> t;
while(t--)
{ long long n ;
cin >> n;
string s;
vector<pair<char , long long >  >arr(n) ;
for(long long i = 0 ; i <n; i++)
cin >> arr[i].ff >> arr[i].ss ;

longestPalindrome(arr);

}

}