# Light OJ: 1401 – No More Tic-tac-toe / UVa 11534 – Say Goodbye to Tic-Tac-Toe

0

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2529

http://www.lightoj.com/volume_showproblem.php?problem=1401

Solutiono Idea: Straight Forward Grundy theory. Think a gap as a nim pile.

```
#include &lt;bits/stdc++.h&gt;
//#include &lt;ext/pb_ds/assoc_container.hpp&gt;
//#include &lt;ext/pb_ds/tree_policy.hpp&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree&lt;int, null_type, less&lt;int&gt;, rb_tree_tag, tree_order_statistics_node_update&gt; ordered_set;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

char str[201];

int dp[102][3][3];

int grundy(int len, int lft, int rgt)
{
if(len&lt;=0) return 0;
if(len==1 &amp;&amp; lft==rgt &amp;&amp; lft!=2) return 1;
if(len==1 &amp;&amp; lft!=rgt &amp;&amp; lft!=2 &amp;&amp; rgt!=2 ) return 0;
int &amp;ret=dp[len][lft][rgt];
if(ret!=-1) return ret;
set&lt;int&gt;st;
for(int i=1; i&lt;=len; i++)
{
int a=0,b=0;
if(i==1)
{
if(lft!=0)
{a=grundy(i-1,lft,0)^grundy(len-i,0,rgt);st.insert(a);}
if(lft!=1)
{b=grundy(i-1,lft,1)^grundy(len-i,1,rgt);st.insert(b);}
}
else if(i==len)
{
if(rgt!=0)
{a=grundy(i-1,lft,0)^grundy(len-i,0,rgt);st.insert(a);}
if(rgt!=1)
{b=grundy(i-1,lft,1)^grundy(len-i,1,rgt);st.insert(b);}
}
else
{
a=grundy(i-1,lft,0)^grundy(len-i,0,rgt);
b=grundy(i-1,lft,1)^grundy(len-i,1,rgt);
st.insert(a);
st.insert(b);
}
}

int x=0;
while(st.find(x)!=st.end()) x++;
return ret=x;
}

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
sf(t);
ms(dp,-1);
TEST_CASE(t)
{
scanf(&quot; %s&quot;,str);
int ans=0;
int len=strlen(str);
int last=-1;
for(int i=0; i&lt;len; i++)
{
if(str[i]!='.')
{
if(str[i]=='O')
{
ans^=grundy(i-last-1,2,0);
}
else
{
ans^=grundy(i-last-1,2,1);
}
last=i;
break;
}
}

for(int i=last+1; i&lt;len; i++)
{
if(str[i]!='.')
{
if(str[i]=='O')
{
ans^=grundy(i-last-1,str[last]=='X',0);
}
else
{
ans^=grundy(i-last-1,str[last]=='X',1);
}
last=i;
}
}
if(last==-1)
ans^=grundy(len-last-1,2,2);
else
ans^=grundy(len-last-1,str[last]=='X',2);

//        PRINT_CASE;

int cnt=0;
for(int i=0; i&lt;len; i++) cnt+=(str[i]!='.');
if(cnt%2==0)
{

if(ans)
printf(&quot;Possible.\n&quot;);
else
printf(&quot;Impossible.\n&quot;);
}
else
{
if(ans==0)
printf(&quot;Possible.\n&quot;);
else
printf(&quot;Impossible.\n&quot;);
}
}

return 0;
}

```

# UVa 10296 – Jogging Trails

0

Solution Idea:
—————–
Light OJ: 1086 – Jogging Trails is a similar problem. The main idea behind this problem is Chinese Postman Problem.

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

int Set(int N,int pos)
{
return N=N | (1&lt;&lt;pos);
}
int reset(int N,int pos)
{
return N= N &amp; ~(1&lt;&lt;pos);
}
bool check(int N,int pos)
{
return (bool)(N &amp; (1&lt;&lt;pos));
}
/*------------------------------------------------*/

ll g[16][16];
int degree[16];
ll dp[1&lt;&lt;16];
int n,m;

void floyed_warshal()
{
for(int k=0; k&lt;n; k++)
for(int i=0; i&lt;n; i++)
for(int j=0; j&lt;n; j++)
{
if(g[i][j]&gt;g[i][k]+g[k][j])
g[i][j]=g[i][k]+g[k][j];
}
}

{
if(ret!=-1) return ret;
int pos=0;
for(int i=0; i&lt;n; i++)
{
pos=i;
break;
}
ret=INT_MAX;
for(int i=pos+1;i&lt;n;i++)
{
{
}
}
return ret;
}

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
//    sf(t);
//    TEST_CASE(t)
while(sf(n) &amp;&amp; n)
{
sf(m);
//        sff(n,m);
ll ans=0;
for(int i=0; i&lt;=n; i++) for(int j=0; j&lt;=n; j++) g[i][j]=INT_MAX;
ms(degree,0);
for(int i=0; i&lt;m; i++)
{
ll a,b,c;
sfffl(a,b,c);
a--;
b--;
g[a][b]=min(g[a][b],c);
g[b][a]=min(g[b][a],c);
degree[a]++;
degree[b]++;
ans+=c;
}

floyed_warshal();

for(int i=0; i&lt;n; i++)
if(degree[i]%2)

//        PRINT_CASE;
ms(dp,-1);
}

return 0;
}

```

# UVa 760 – DNA Sequencing

0

Solution Idea:
1. Concatenate two string then build suffix array and LCP array.
1. Now find those position in LCP array where two consecutive suffix is from two
different input string.
3. Now take the maximum of LCP[these indexes]
4. After that generate string from this position with the determined maximum
length value.
5. Print the distinct strings from these strings.

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 1005

int SA[mx],tempSA[mx];
int RA[mx],tempRA[mx];
int c[mx];
int LCP[mx],PLCP[mx],Phi[mx];
char str[mx],str1[mx];
int n;

void counting_sort(int k)
{
int maxi=max(300,n);
ms(c,0);
for(int i=0; i&lt;n; i++)
{
int a=i+k&lt;n?RA[i+k]:0;
c[a]++;
}
for(int i=0,sum=0; i&lt;maxi; i++)
{
int x=c[i];
c[i]=sum;
sum+=x;
}

for(int i=0; i&lt;n; i++)
{
int a=SA[i]+k&lt;n?RA[SA[i]+k]:0;
int b=c[a];
c[a]++;
tempSA[b]=SA[i];
}

for(int i=0; i&lt;n; i++)
SA[i]=tempSA[i];
}

void build_Suffix_Array()
{
for(int i=0; i&lt;n; i++)
{
RA[i]=str[i];
SA[i]=i;
}

for(int k=1; k&lt;n; k*=2)
{
counting_sort(k);
counting_sort(0);
int r=0;
tempRA[SA[0]]=r=0;
for(int i=1; i&lt;n; i++)
{
if(RA[SA[i]]==RA[SA[i-1]] &amp;&amp; RA[SA[i]+k]==RA[SA[i-1]+k])
tempRA[SA[i]]=r;
else
tempRA[SA[i]]=++r;
}
for(int i=0; i&lt;n; i++)
{
RA[i]=tempRA[i];
}
if(RA[SA[n-1]]==n-1) break;
}
}

void build_LCP()
{
Phi[SA[0]]=-1;
for(int i=1; i&lt;n; i++)
Phi[SA[i]]=SA[i-1];
for(int i=0,L=0; i&lt;n; i++)
{
if(Phi[i]==-1)
{
PLCP[i]=0;
continue;
}
while(str[i+L]==str[Phi[i]+L]) L++;
PLCP[i]=L;
L=max(L-1,0);
}

for(int i=0; i&lt;n; i++)
LCP[i]=PLCP[SA[i]];
}

map&lt;string,bool&gt;mp;

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

bool check=0;
while(scanf(&quot;%s&quot;,str)!=EOF)
{
scanf(&quot;%s&quot;,str1);
strcat(str,&quot;\$&quot;);
int l1=strlen(str)-1;
strcat(str,str1);
strcat(str,&quot;#&quot;);
n=strlen(str);
build_Suffix_Array();
build_LCP();
string str2=str;
int ans=0,maxi=0;

if(check)
pf(&quot;\n&quot;);
check=1;

//        for(int i=0;i&lt;n;i++)
//            cout&lt;&lt;SA[i]&lt;&lt;&quot; &quot;;
//        cout&lt;&lt;endl;
//        for(int i=0;i&lt;n;i++)
//            cout&lt;&lt;LCP[i]&lt;&lt;&quot; &quot;;
//        cout&lt;&lt;endl;
//
//        for(int i=0;i&lt;n;i++)
//        {
//            cout&lt;&lt;str2.substr(SA[i])&lt;&lt;endl;
//        }
//        cout&lt;&lt;endl;

for(int i=1; i&lt;n; i++)
{
if((SA[i]&lt;l1 &amp;&amp; SA[i-1]&lt;n &amp;&amp; SA[i-1]&gt;l1) || (SA[i]&gt;l1 &amp;&amp; SA[i]&lt;n &amp;&amp; SA[i-1]&lt;l1))
maxi=max(maxi,LCP[i]);
}

if(maxi==0)
{
pf(&quot;No common sequence.\n&quot;);
continue;
}

mp.clear();

for(int i=1; i&lt;n; i++)
{
if((SA[i]&lt;l1 &amp;&amp; SA[i-1]&lt;n &amp;&amp; SA[i-1]&gt;l1)|| (SA[i]&gt;l1 &amp;&amp; SA[i]&lt;n &amp;&amp; SA[i-1]&lt;l1))
{
if(LCP[i]==maxi)
{
string temp=str2.substr(SA[i],maxi);
if(mp[temp]) continue;
else
mp[temp]=1;
printf(&quot;%s\n&quot;,temp.c_str());
}
}
}
}

return 0;
}

```

# UVa: 11512 – GATTACA

0

Solution Idea: Build Suffix array and LCP array then answer is the maximum entry in LCP array.

Lesson: Always use a ‘\$’ Symbol in this implementation of Suffix Array. Otherwise you will get nothing but WA -_- .

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 100005

int SA[mx],tempSA[mx];
int RA[mx],tempRA[mx];
int count_sort[mx];
char str[mx],pattern[mx];

int Phi[mx],LCP[mx],PLCP[mx];

int n;

void counting_sort(int k)
{
ms(count_sort,0);
int maxi=max(300,n);
for(int i=0; i&lt;n; i++)
{
int a=i+k&lt;n?RA[i+k]:0;
count_sort[a]++;
}
for(int i=0,sum=0; i&lt;maxi; i++)
{
int x=count_sort[i];
count_sort[i]=sum;
sum+=x;
}

for(int i=0; i&lt;n; i++)
{
int a=SA[i]+k&lt;n?RA[SA[i]+k]:0;
int b=count_sort[a];
count_sort[a]++;
tempSA[b]=SA[i];
}

for(int i=0; i&lt;n; i++)
SA[i]=tempSA[i];

}

void build_Suffix_Array()
{
for(int i=0; i&lt;n; i++)
{
RA[i]=str[i];
SA[i]=i;
}
for(int k=1; k&lt;n; k*=2)
{
counting_sort(k);
counting_sort(0);
int r;
tempRA[SA[0]]=r=0;
for(int i=1; i&lt;n; i++)
{
if(RA[SA[i]]==RA[SA[i-1]] &amp;&amp; RA[SA[i]+k]==RA[SA[i-1]+k])
tempRA[SA[i]]=r;
else
tempRA[SA[i]]=++r;
}
for(int i=0; i&lt;n; i++)
RA[i]=tempRA[i];
if(RA[SA[n-1]]==n-1) break;
}
}

void compute_LCP()
{
int l=0;
Phi[SA[0]]=-1;
for(int i=1; i&lt;n; i++)
Phi[SA[i]]=SA[i-1];
for(int i=0,L=0; i&lt;n; i++)
{
if(Phi[i]==-1)
{
PLCP[i]=0;
continue;
}
while(str[i+L]==str[Phi[i]+L])
{
//            D(str[i+L]);
//            D(str[Phi[i]+L]);
L++;
}
PLCP[i]=L;
L=max(L-1,0);
}

for(int i=0; i&lt;n; i++)
LCP[i]=PLCP[SA[i]];

}

int find_pattern(int len)
{
int lo=0,hi=n-1;
while(lo&lt;hi)
{
int mid=(lo+hi)/2;
int res=strncmp(str+SA[mid],pattern,len);
if(res&gt;=0) hi=mid;
else
lo=mid+1;
}
ll ret=lo;
if(strncmp(str+SA[ret],pattern,len)!=0) return 0;
lo=0,hi=n-1;
while(lo&lt;hi)
{
int mid=(lo+hi)/2;
int res=strncmp(str+SA[mid],pattern,len);
if(res&gt;0) hi=mid;
else
lo=mid+1;
}

if(strncmp(str+SA[hi],pattern,len)!=0) hi--;
return hi-ret+1;
}

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
sf(t);
TEST_CASE(t)
{
scanf(&quot;%s&quot;,str);
strcat(str,&quot;\$&quot;);
n=strlen(str);
string str1=str;
build_Suffix_Array();
//        for(int i=0; i&lt;n; i++)
//            pf(&quot;%d\n&quot;,SA[i]);
compute_LCP();

//        for(int i=0; i&lt;n; i++)
//            cout&lt;&lt;SA[i]&lt;&lt;&quot; &quot;;
//        cout&lt;&lt;endl;
//        for(int i=0; i&lt;n; i++)
//            cout&lt;&lt;LCP[i]&lt;&lt;&quot; &quot;;
//        cout&lt;&lt;endl;

int ans=0;
for(int i=0; i&lt;n; i++)
ans=max(ans,LCP[i]);
if(ans&lt;=0)
{
pf(&quot;No repetitions found!\n&quot;);
continue;
}
int cnt=0,pos=0;
for(int i=0; i&lt;n; i++)
{
if(LCP[i]==ans)
{
pos=i;
break;
}
}

strncpy(pattern,str+SA[pos],ans);

cnt=find_pattern(ans);

printf(&quot;%s %d\n&quot;,str1.substr(SA[pos],ans).c_str(),cnt);

}

return 0;
}

```

# UVa 10679 – I Love Strings!!

0

Solution Idea: Build Suffix Array then binary search on the sorted sequence.

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 100005

int suffix_array[mx],position[mx];

struct data
{
pii rank;
int pos;
};

bool cmp(data a, data b)
{
return a.rank&lt;b.rank;
}

char str[mx],query[mx];

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
sf(t);
TEST_CASE(t)
{
scanf(&quot;%s&quot;,str);

int n=strlen(str);

for(int i=0;i&lt;n;i++) position[i]=str[i];

for(int k=1;k&lt;n;k*=2)
{
vector&lt;data&gt;v(n);
for(int i=0;i&lt;n;i++)
{
int a=position[i];
int b;
if(i+k&gt;=n)
b=-1;
else
b=position[i+k];
v[i].rank=pii(a,b);
v[i].pos=i;
}

sort(all(v),cmp);

position[v[0].pos]=0;
suffix_array[0]=v[0].pos;
for(int i=1;i&lt;n;i++)
{
suffix_array[i]=v[i].pos;
if(v[i].rank==v[i-1].rank)
position[v[i].pos]=position[v[i-1].pos];
else
position[v[i].pos]=i;
}
}

int q;
sf(q);
while(q--)
{
scanf(&quot;%s&quot;,query);
int l=strlen(query);
int lo=0,hi=n-1;
bool ans=0;
while(lo&lt;=hi)
{
int mid=(lo+hi)/2;
int x=strncmp(str+suffix_array[mid],query,l);
if(x==0)
{
ans=1;
break;
}
else if(x&gt;0)
hi=mid-1;
else
lo=mid+1;
}
if(ans)
pf(&quot;y\n&quot;);
else
pf(&quot;n\n&quot;);
}
}

return 0;
}

```

# UVa 1314 – Hidden Password

0

Solution Idea: Concatenate the input string with itself and find the suffix array. Answer will be the smallest string in suffix array which lie between index 0 to n-1 and which index is smaller.

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

char ara[100005];

struct data
{
pii rank;
int pos;
};

bool cmp(data a, data b)
{
return a.rank&lt;b.rank;
}

int suffix_ara[200005];

int position[200005];

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
sf(t);
TEST_CASE(t)
{
int n;
sf(n);
getchar();
gets(ara);
string str=ara;
str+=str;
n*=2;
for(int i=0;i&lt;n;i++)
{
position[i]=str[i]-'a';
}

for(int steep=1;steep&lt;n;steep*=2)
{
vector&lt;data&gt;v(n);
for(int i=0;i&lt;n;i++)
{
int a=position[i];
int b;
if(i+steep&gt;=n)
b=100000000;
else
b=position[i+steep];
v[i].rank=pii(a,b);
v[i].pos=i;
}

sort(all(v),cmp);

position[v[0].pos]=0;
suffix_ara[0]=v[0].pos;

for(int i=1;i&lt;n;i++)
{
suffix_ara[i]=v[i].pos;
if(v[i].rank==v[i-1].rank)
position[v[i].pos]=position[v[i-1].pos];
else
position[v[i].pos]=i;
}
}

for(int i=0;i&lt;n;i++)
{
if(suffix_ara[i]&lt;n/2)
{
pf(&quot;%d\n&quot;,suffix_ara[i]);
//                pf(&quot;%s\n&quot;,str.substr(suffix_ara[i]).c_str());
break;
}
}
}

return 0;
}

```

# UVa 11246 – K-Multiple Free set

0

Solution Idea:

``` int MFS(int N,int K) { int ret=0; for(int i=1;N;i=-i) { ret+=N*i; N/=K; } return ret; } ```

So how does this work? Let us start with the full set {1…N}. We need to remove some numbers from this so that it is a K-multiple free set. For this, let us remove every multiple of K from the set. These are the numbers K,2K… and there are N/K of them. Removing them gives us a K-multiple free set. But we have removed some numbers unnecessarily. Since we already removed K, removing K² was unnecessary. Thus we can put back K²,2K²…, which would be N/K² numbers in total. But this ends up putting both K² and K³ into the set and we need to remove all multiples of K³ now. Proceeding in this fashion, it is easy to see that the cardinality of the final set is N – N/K + N/K² – N/K³…

In general, an input size of N=10⁹ in a mathematical problem should give you the idea that neither the time or space complexity of the solution can be O(N) and you have to come up with some sort of a closed form solution.

This solutino idea is from this link.

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//	  freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

int t;
sf(t);
TEST_CASE(t)
{
ll n,k;
sffl(n,k);
if(k==0)
pf(&quot;0\n&quot;);
else
{
ll ans=n;
ll kk=k;
int cnt=1;
while(kk&lt;=n)
{
if(cnt%2)
ans-=(n/kk);
else
ans+=(n/kk);
kk*=k;
cnt++;
}
pf(&quot;%lld\n&quot;,ans);
}
}

return 0;
}

```

# UVa 1152 – 4 Values whose Sum is 0

0
```
/*
User ID: turing_13
*/

#include &lt;bits/stdc++.h&gt;

#define pii pair &lt;int,int&gt;
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1&lt;&lt;29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 100
#define SZ(a) (int)a.size()
#define getint(a) scanf(&quot;%d&quot;,&amp;a)
#define loop(i,n) for(int i=0;i&lt;n;i++)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;

ll ara[4010][4];
vector&lt;ll&gt;ab;

int main()
{
///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);
int n,t;
sc(&quot;%d&quot;,&amp;t);
while(t--)
{
ll ans=0;
sc(&quot;%d&quot;,&amp;n);
for(int i=0; i&lt;n; i++)
{
sc(&quot;%lld %lld %lld %lld&quot;,&amp;ara[i][0],&amp;ara[i][1],&amp;ara[i][2],&amp;ara[i][3]);
}
for(int i=0; i&lt;n; i++)
for(int j=0; j&lt;n; j++)
{
ab.pb(ara[i][0]+ara[j][1]);
}
sort(all(ab));
for(int i=0; i&lt;n; i++)
for(int j=0; j&lt;n; j++)
{
int val= -(ara[i][2]+ara[j][3]);
ans+= upper_bound(all(ab),val)-lower_bound(all(ab),val);
}
pf(&quot;%lld\n&quot;,ans);
if(t)
pf(&quot;\n&quot;);
ab.clear();
}
return 0;
}

```

# UVa 438 – The Circumference of the Circle

0

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

double dist(double x1, double y1, double x2, double y2)
{
return sqrt(sqr(x1-x2)+sqr(y1-y2));
}

int main()
{

///freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
///freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

double x1,y1,x2,y2,x3,y3;
while(cin&gt;&gt;x1&gt;&gt;y1&gt;&gt;x2&gt;&gt;y2&gt;&gt;x3&gt;&gt;y3)
{
double a,b,c;

//calculating the three side of the triangle

a=dist(x1,y1,x2,y2);
b=dist(x2,y2,x3,y3);
c=dist(x1,y1,x3,y3);

// calculating the sub perimeter

double s=(a+b+c)/2.0;

// calculating the area of the triangle.

double area=sqrt(s*(s-a)*(s-b)*(s-c));

// calculating radius using formula area= (a*b*c)/(2*R) ; here R = diameter

double r=(a*b*c)/(4.0*area);

cout&lt;&lt;setprecision(2)&lt;&lt;fixed&lt;&lt;Pi*2.0*r&lt;&lt;endl;

}

return 0;
}

```

# UVa : 10938 – Flea circus

0

Solution Idea: Find the LCA. Then find the middle node and middle+1 node on the path connection two nodes which are given in the query. Here I use an extra DFS to find the path on a reverse graph g2.

```
#include &lt;bits/stdc++.h&gt;

#define pii              pair &lt;int,int&gt;
#define pll              pair &lt;long long,long long&gt;
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout&lt;&lt;#x &quot; = &quot;&lt;&lt;(x)&lt;&lt;endl
#define VI               vector &lt;int&gt;
#define DBG              pf(&quot;Hi\n&quot;)
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf(&quot;%d&quot;,&amp;a)
#define sfl(a)           scanf(&quot;%lld&quot;,&amp;a)
#define sff(a,b)         scanf(&quot;%d %d&quot;,&amp;a,&amp;b)
#define sffl(a,b)        scanf(&quot;%lld %lld&quot;,&amp;a,&amp;b)
#define sfff(a,b,c)      scanf(&quot;%d %d %d&quot;,&amp;a,&amp;b,&amp;c)
#define sfffl(a,b,c)     scanf(&quot;%lld %lld %lld&quot;,&amp;a,&amp;b,&amp;c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i&lt;n;i++)
#define loop1(i,n)       for(int i=1;i&lt;=n;i++)
#define REP(i,a,b)       for(int i=a;i&lt;b;i++)
#define RREP(i,a,b)      for(int i=a;i&gt;=b;i--)
#define TEST_CASE(t)     for(int z=1;z&lt;=t;z++)
#define PRINT_CASE       printf(&quot;Case %d: &quot;,z)
#define LINE_PRINT_CASE  printf(&quot;Case %d:\n&quot;,z)
#define CASE_PRINT       cout&lt;&lt;&quot;Case &quot;&lt;&lt;z&lt;&lt;&quot;: &quot;
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1&lt;&lt;28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1&lt;&lt;pos);}
//int reset(int N,int pos){return N= N &amp; ~(1&lt;&lt;pos);}
//bool check(int N,int pos){return (bool)(N &amp; (1&lt;&lt;pos));}
/*------------------------------------------------*/

#define mx 5005
int n,q;

vector&lt;int&gt;g1[mx],g2[mx];

int sparse_par[mx][14],sparse_dis[mx][14];

int level[mx],par[mx];

void dfs(int u, int cnt, int from)
{
par[u]=from;
level[u]=cnt;
g2[u].pb(from);

for(int i=0;i&lt;SZ(g1[u]);i++)
{
int v=g1[u][i];
if(v!=from)
{
dfs(v,cnt+1,u);
}
}
}

void build_talbe()
{
for(int i=1;i&lt;=n;i++)
{
sparse_par[i][0]=par[i];
sparse_dis[i][0]=1;
}
sparse_dis[1][0]=0;

for(int j=1; 1&lt;&lt;j&lt;=n;j++)
{
for(int i=1;i&lt;=n;i++)
{
sparse_par[i][j]=sparse_par[sparse_par[i][j-1]][j-1];
sparse_dis[i][j]=sparse_dis[i][j-1]+sparse_dis[sparse_par[i][j-1]][j-1];
}
}
}

int LCA;

int query(int p, int q)
{
if(level[p]&lt;=level[q]) swap(p,q);

int log=log2(level[p]);

int ret=0;

for(int i=log;i&gt;=0;i--)
{
if(level[p]-(1&lt;&lt;i)&gt;=level[q])
{
ret+=sparse_dis[p][i];
p=sparse_par[p][i];
}
}

if(p==q){LCA=p; return ret;}

for(int i=log;i&gt;=0;i--)
{
if(sparse_par[p][i]!=sparse_par[q][i])
{
ret+=sparse_dis[p][i];
ret+=sparse_dis[q][i];
p=sparse_par[p][i];
q=sparse_par[q][i];
}
}
ret+=2;
LCA=par[p];
return ret;
}

vector&lt;int&gt;temp;

int dfs1(int u, int cnt)
{
if(u==LCA) return u;
temp.pb(u);
if(cnt==0) return u;
for(int i=0;i&lt;SZ(g2[u]);i++)
return dfs1(g2[u][i],cnt-1);
}

int main()
{

//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//    freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);

while(sf(n) &amp;&amp; n)
{
loop(i,n-1)
{
int a,b;
sff(a,b);
g1[a].pb(b);
g1[b].pb(a);
}

dfs(1,0,1);

build_talbe();

sf(q);

while(q--)
{
int a,b;
sff(a,b);

int dis=query(a,b)+1;

if(dis%2==0)
{
temp.clear();
dfs1(a,n);
temp.pb(LCA);
int x=SZ(temp);
dfs1(b,n);
reverse(temp.begin()+x,temp.end());
int aa=temp[(dis/2)-1];
int bb=temp[dis/2];
pf(&quot;The fleas jump forever between %d and %d.\n&quot;,min(aa,bb),max(aa,bb));

}
else
{
int p;
if(level[a]&gt;level[b])
p=a;
else
p=b;
pf(&quot;The fleas meet at %d.\n&quot;,dfs1(p,dis/2));
}
}

for(int i=0;i&lt;=n;i++)
{
g1[i].clear();
g2[i].clear();
}

}

return 0;
}

```