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

How to approach this problem http://www.spoj.com/problems/AIRLINES/

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

Can anyone please write a nice tutorial on suffix automaton , i tried my best to learn it from e-maxx and http://codeforces.net/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 ...

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

   }



}