saisumit's blog

By saisumit, history, 7 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -16
  • Vote: I do not like it

By saisumit, history, 8 years ago, In English
  • Vote: I like it
  • -15
  • Vote: I do not like it

By saisumit, history, 8 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +54
  • Vote: I do not like it

By saisumit, history, 8 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

By saisumit, history, 8 years ago, In English

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

   }



}

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it