Category Archives: Light OJ

Light OJ: 1144 – Ray Gun

0
Posted on by
Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1144
Solution Idea:

    • There are many observations to make in order to get to a working solution.
    • For every lattice point (i, j), the ray that intersects it is unique and it’s identified by the pair , where g is the gcd of i and j.
    • The problem is now reduced to counting the number of irreducible fractions such that a ≤ N and b ≤ M. This is the same as counting for every i between 1 and N, the amount of numbers in the range [1, M] that are coprime with i.
    • Consider a certain number x with prime factors p1, p2. How do we know how many numbers in range [1, M] are coprime with it? That’s equal to M minus the amount of multiples of p1 minus the amount of multiples of p2 plus the amount of multiples of p1 * p2. This is inclusion-exclusion, and in general, if the amount of elements is even, we add, otherwise, we subtract.
    • So now we have a working (but slow) solution: Iterate over every i in the range [1, N] and for every i, factorize it, try out all combinations of primes and then, for every combination that results in a number k, add if the amount of primes is even or subtract if the amount of primes is odd.
    • The previous approach is very slow for two reasons: You’ll be factorizing each number every time and you’ll be doing a lot of repeated work. Every combination of primes you try out at each step will result in a certain number k. A crucial observation is that the higher exponent of that number k will be 1, because we’re trying combinations of different primes. Another crucial observation is that this number k will be seen times in total. Finally, each time we see it, it will contribute by to the final answer (or if the amount of primes is odd).
    • Knowing all this, we can precalculate a lot of stuff and then solve each test case in O(N). We should precalculate the amount of prime factors of every number in the range [1, 106] (this can be done with a simple sieve), and we should cross out numbers that have some prime with an exponent higher than 1 (in other words, multiples of some square). Once we have precalculated all that, we simply iterate from 1 to N and for every number x that we didn’t cross out, we add (or subtract) to our answer.
    • Final observations: We should add 2 to our answer (the two borders). If N = 0, the answer is 1, except M = 0 too, in which case the answer is 0.

(This solution idea is from this link )

Light OJ: 1267 – Points in Rectangle (II)

0
Posted on by

Problem Link: http://www.lightoj.com/volume_showproblem.php?problem=1267

Solution Idea:

This problem is similar to Codeforces gym 101484: B. Nicoleta’s Cleaning. We need a line sweep technique and some data structure to solve this problem. We need to convert each rectangle to opening and closing with respect to its x coordinates. Then we need to sort all points and open and close together. then for each opening element we need to count how many points are before opening point let is is X and for each closing, we need to count how many points are before and on the closing point in the range, lower y coordinate to upper y coordinate let it is Y. Then the number of points inside the rectangle is Y-X. For each given point we need to update it when we find it through scan line in x coordinate of it.

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#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<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#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("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<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<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> 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
/*------------------------------------------------*/

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

struct data
{
    int type,x,st,ed,id;
};

vector<int>x,y;
vector<data>v;

bool cmp(data a, data b)
{
    if(a.x<b.x) return true;
    if(a.x==b.x)
        return a.type<b.type;
    return false;
}

#define mx 300005

int tree[mx];

void update(int idx, int val)
{
    for(; idx<mx && idx; idx+=(idx&-idx))
        tree[idx]+=val;
}

int query(int idx)
{
    int ret=0;
    for(; idx; idx-=(idx&-idx))
        ret+=tree[idx];
    return ret;
}

int ans[mx];

int main()
{
//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);
    int t;
    sf(t);
    TEST_CASE(t)
    {
        int n,m;
        sff(n,m);
        for(int i=0; i<n; i++)
        {
            int a,b;
            sff(a,b);
            data temp;
            temp.type=2;
            temp.x=a;
            temp.ed=temp.st=b;
            v.pb(temp);
            x.pb(a);
            y.pb(b);
        }

        for(int i=0; i<m; i++)
        {
            int a,b,c,d;
            sff(a,b);
            sff(c,d);
            x.pb(a);
            x.pb(c);
            y.pb(b);
            y.pb(d);
            data temp;
            temp.type=3;
            temp.x=c;
            temp.st=b;
            temp.ed=d;
            temp.id=i;
            v.pb(temp);
            data temp1;
            temp1.type=1;
            temp1.x=a;
            temp1.st=b;
            temp1.ed=d;
            temp1.id=i;
            v.pb(temp1);
        }

//    sort(all(x));
        sort(all(y));
        sort(all(v),cmp);

        for(int i=0; i<SZ(v); i++)
        {
            data temp=v[i];
            if(temp.type==1)
            {
                int a=lower_bound(all(y),temp.st)-y.begin()+1;
                int b=lower_bound(all(y),temp.ed)-y.begin()+1;
                int xx=query(b);
                int yy=query(a-1);
                ans[temp.id]=xx-yy;
            }
            else if(temp.type==3)
            {
                int a=lower_bound(all(y),temp.st)-y.begin()+1;
                int b=lower_bound(all(y),temp.ed)-y.begin()+1;
                int xx=query(b);
                int yy=query(a-1);
                ans[temp.id]=(xx-yy)-ans[temp.id];
            }
            else
            {
                int a=lower_bound(all(y),temp.st)-y.begin()+1;
                update(a,1);
//            int yy=query(a-1); // Never do this while range update on BIT -_-
//            ans[temp.id]=xx;
            }
        }

        LINE_PRINT_CASE;
        for(int i=0; i<m; i++)
            printf("%d\n",ans[i]);
        ms(tree,0);
        x.clear();
        y.clear();
        v.clear();
    }
    return 0;
}

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

0
Posted on by

Problem Link :

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
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//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;
}

Light OJ 1229 – TREBLECROSS / UVa 10561 – Treblecross

0
Posted on by

Problem Link :

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

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


#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
/*------------------------------------------------*/
 
/*-----------------------Bitmask------------------*/
//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[400];
 
string str;
 
int dp[205];
 
int func(int m)
{
    if(m&lt;=0) return 0;
    int &amp;ret=dp[m];
    if(ret!=-1) return ret;
    set&lt;int&gt;st;
    for(int i=1;i&lt;=m; i++)
    {
        st.insert(func(i-3)^func(m-i-2));
    }
    int x=0;
    while(st.find(x)!=st.end())x++;
    return ret=x;
}
 
bool solve(int idx)
{
    if(str[idx]=='X') return 0;
    string temp=str;
    temp[idx]='X';
    for(int i=0;i&lt;SZ(temp)-2;i++)
    {
        if(temp[i]=='X' &amp;&amp; temp[i+1]=='X' &amp;&amp; temp[i+2]=='X') return 1;
    }
    for(int i=0;i&lt;SZ(temp)-2;i++)
    {
        if(temp[i]=='X' &amp;&amp; temp[i+2]=='X') return 0;
    }
    for(int i=0;i&lt;SZ(temp)-1;i++)
    {
        if(temp[i]=='X' &amp;&amp; temp[i+1]=='X') return 0;
    }
 
    int ans=0,last=-1;
    for(int i=0;i&lt;SZ(temp);i++)
    {
        if(temp[i]=='X')
        {
            if(last==-1)
                ans^=func(i-last-3);
            else
                ans^=func(i-last-5);
            last=i;
        }
    }
    ans^=func(SZ(temp)-last-3);
    return ans==0;
}
 
int main()
{
    CIN;
//    freopen(&quot;in.txt&quot;,&quot;r&quot;,stdin);
//    freopen(&quot;out.txt&quot;,&quot;w&quot;,stdout);
 
    int t;
//    sf(t);
    cin&gt;&gt;t;
    ms(dp,-1);
    TEST_CASE(t)
    {
        cin&gt;&gt;str;
        vector&lt;int&gt;pos;
        for(int i=0;i&lt;SZ(str);i++)
        {
            if(solve(i))
            {
                pos.pb(i+1);
            }
        }
        CASE_PRINT;
        if(SZ(pos)==0)
            cout&lt;&lt;0&lt;&lt;endl;
        else
        {
            cout&lt;&lt;pos[0];
            for(int i=1;i&lt;SZ(pos);i++)
                cout&lt;&lt;&quot; &quot;&lt;&lt;pos[i];
            cout&lt;&lt;endl;
        }
    }
 
    return 0;
}

UVa 10296 – Jogging Trails

0
Posted on by

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


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

For details about this theorem is described in book Competitive programming 3 by Steven Halim.


#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
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
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];
            }
}

ll func(int mask)
{
    if(mask==0) return 0;
    ll &amp;ret=dp[mask];
    if(ret!=-1) return ret;
    int pos=0;
    for(int i=0; i&lt;n; i++)
        if(check(mask,i))
        {
            pos=i;
            break;
        }
    ret=INT_MAX;
    for(int i=pos+1;i&lt;n;i++)
    {
        if(check(mask,i))
        {
            int temp_mask=mask;
            temp_mask=reset(temp_mask,pos);
            temp_mask=reset(temp_mask,i);
            ret=min(ret,g[pos][i]+func(temp_mask));
        }
    }
    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();

        int mask=0;

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


//        PRINT_CASE;
        ms(dp,-1);
        printf(&quot;%lld\n&quot;,ans+func(mask));
    }

    return 0;
}

Light OJ: 1347 – Aladdin and the Magical Lamp

0
Posted on by

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1347


Solution Idea:
###############
Solution idea for this problem is following-
1. Concatenate 3 input string one after another and make one single string.
2. Build Suffix array and store every step rank.
3. Run sliding window or two pointer on sorted suffix array and find the range in which 3 string presents. and determine the LCP of beginning and ending string of that range segment.
4. Largest LCP value find during step 3 is the answer.


#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
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//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 30005

int SA[mx],tempSA[mx];
int RA[mx],tempRA[mx];
int c[mx];
//int LCP[mx],PLCP[mx],Phi[mx];
int P[18][mx],stp;
string str;
char s1[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()
{
    stp=0;
    for(int i=0; i&lt;n; i++)
    {
        RA[i]=str[i];
        SA[i]=i;
        P[stp][i]=RA[i];
    }

    stp++;

    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];
            P[stp][i]=RA[i];
        }
        stp++;
        if(RA[SA[n-1]]==n-1) break;
    }
    stp--;
}


int find_lcp(int x, int y)
{
    int ret=0;
    if(x==y) return n-x;
    for(int k=stp; k&gt;=0 &amp;&amp; x&lt;n &amp;&amp; y&lt;n; k--)
    {
        if(P[k][x]==P[k][y])
        {
            x+=(1&lt;&lt;k);
            y+=(1&lt;&lt;k);
            ret+=(1&lt;&lt;k);
        }
    }
    return ret;
}


int vis[5];

int getRange(int idx, int pos1, int pos2)
{
    if(idx&lt;pos1) return 1;
    if(idx&lt;pos2) return 2;
    return 3;
}



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)
    {
        str.clear();
        scanf(&quot;%s&quot;,s1);
        str+=string(s1);
        str+=&quot;@&quot;;
        int pos1=SZ(str)-1;
        scanf(&quot;%s&quot;,s1);
        str+=string(s1);
        str+=&quot;$&quot;;
        int pos2=SZ(str)-1;
        scanf(&quot;%s&quot;,s1);
        str+=string(s1);
        str+=&quot;#&quot;;
        n=SZ(str);
//        cout&lt;&lt;str&lt;&lt;endl;
        build_Suffix_Array();

//        for(int i=0; i&lt;n; i++)
//            cout&lt;&lt;str.substr(SA[i])&lt;&lt;endl;

        int ans=0;

        int i=3,j=3;
        ms(vis,0);
        int cnt=0;
        while(j&lt;n)
        {
            int a=getRange(SA[j],pos1,pos2);
            if(vis[a]==0)
            {
                cnt++;
            }
            vis[a]++;
            if(cnt==3)
            {
                int temp=find_lcp(SA[i],SA[j]);
                ans=max(ans,temp);
            }
            while(cnt&gt;=3)
            {
                a=getRange(SA[i],pos1,pos2);
                vis[a]--;
                i++;
                if(vis[a]==0)
                    cnt--;
                if(cnt==3)
                {
                    int temp=find_lcp(SA[i],SA[j]);
                    ans=max(ans,temp);
                }
            }
            j++;
        }
        PRINT_CASE;
        pf(&quot;%d\n&quot;,ans);
    }


    return 0;
}

Light OJ: 1314 – Names for Babies

0
Posted on by

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1314


Solution Idea:

Build Suffix array and LCP array. Then find the distinct substring using LCP arrray by the formula (Length of the suffix – LCP of this and the previous suffix). But in this problem we need to calculate the length which lie in the given range. Think about it. 


#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
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//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 c[mx];
int LCP[mx],PLCP[mx],Phi[mx];
//int P[18][mx];
char str[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]];
}



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);
        build_Suffix_Array();
        build_LCP();


//        string ss=str;
//        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;ss.substr(SA[i])&lt;&lt;endl;

        int a,b;
        sff(a,b);

        int ans=0;
        for(int i=1;i&lt;n;i++)
        {
            int len=n-SA[i]-1;
            int temp=len-LCP[i];
            if(len&gt;b)
                temp-=(len-b);
            if(LCP[i]&lt;a)
                temp-=(a-LCP[i]-1);
            temp=max(temp,0);
            ans+=temp;
        }

        PRINT_CASE;
        pf(&quot;%d\n&quot;,ans);

    }

    return 0;
}

Light OJ: 1424 – New Land

0
Posted on by

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1424

Solution Idea: I think this problem can be solved with a 2D Segment Tree. But here I use the histogram technique to solve this problem. You can try Spoj – HISTOGRA – Largest Rectangle in a Histogram and Light OJ – 1083 – Histogram . Both are same problem on different website. This problems can be using a niche technique called histogram which can be implemented using a stack. the algorithm determine the index of the bar before the current bar which is smaller than the current bar also determine the index of the bar after the current bar which is smaller than the current bar. Here the function func is the answer of the above two problem.

In this problem for each row we consider a histogram from current row and the rows which are above the current row with continuous 0. Then determine the maximum answer.


#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
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//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 2002

char grid[mx][mx];

int dp[mx][mx];

int func(int ara[], int n)
{
    int left[mx];

    stack&lt;int&gt;st;

    for(int i=0; i&lt;n; i++)
    {
        while(!st.empty() &amp;&amp; ara[st.top()]&gt;=ara[i]) st.pop();
        left[i]=(st.empty()?-1:st.top());
        st.push(i);
    }

    while(!st.empty()) st.pop();

    int ret=0;
    int right;
    for(int i=n-1; i&gt;=0; i--)
    {
        while(!st.empty() &amp;&amp; ara[st.top()]&gt;=ara[i]) st.pop();
        right=(st.empty()?n:st.top());
        ret=max((right-left[i]-1)*ara[i],ret);
        st.push(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)
    {
        int n,m;
        sff(n,m);
        getchar();
        for(int i=0; i&lt;n; i++)
            sc(&quot;%s&quot;,grid[i]);

        for(int j=0; j&lt;m; j++)
        {
            dp[0][j]=(grid[0][j]=='0')?1:0;
        }

        int ans=func(dp[0],m);

        for(int i=1; i&lt;n; i++)
        {
            for(int j=0; j&lt;m; j++)
            {
                dp[i][j]=dp[i-1][j]+((grid[i][j]=='0')?1:-dp[i-1][j]);
            }
            ans=max(ans,func(dp[i],m));
        }
        PRINT_CASE;
        pf(&quot;%d\n&quot;,ans);

    }


    return 0;
}

1217 – Neighbor House (II)

0
Posted on by

Problem Link : http://lightoj.com:81/volume/problem/1217


#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
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//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 n;
int ara[1001];

int    dp[1001][1001][3];
bool xxxxx[1001][1001][3];
int yy=1;

int func(int idx, int last, int state)
{

    if(idx&gt;n)
    {
        if(state==0 &amp;&amp; last!=n)
            return ara[1];
        return 0;
    }

    int &amp;ret=dp[idx][last][state];
    bool &amp;cas=xxxxx[idx][last][state];
    if(cas) return ret;
    cas=1;

////    if(ret!=-1) return ret;

    int p=0,q=0;

    if(idx==1)
    {
        p=ara[1]+func(idx+2,idx,1);
        q=func(idx+1,last,state);
    }
    else if(idx==2)
    {
        p=ara[2]+func(idx+2,idx,2);
        q=func(idx+1,0,state);
    }
    else if(idx==n)
    {
        if(last!=n-1 &amp;&amp; state!=1)
            p=ara[n]+func(idx+2,idx,state);
        q=func(idx+1,last,state);
    }
    else
    {
        p=ara[idx]+func(idx+2,idx,state);
        q=func(idx+1,last,state);
    }

    return ret=max(p,q);


}

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)
    {
        sf(n);
        for(int i=1; i&lt;=n; i++) sf(ara[i]);
//        ms(dp,-1);
//        yy++;
        ms(xxxxx,0);
        PRINT_CASE;
        printf(&quot;%d\n&quot;,func(1,0,0));

    }

    return 0;
}

Light OJ: 1326 – Race

0
Posted on by

Problem Link : http://lightoj.com:81/volume/problem/1326

Solution Idea:

Let’s define dp(i) as the number of ways in which a race with “i” horses can finish.

Suppose we have “i” horses at the race and we will choose k of them for the first place, leaving “i – k” for the second (or higher) place. The process to count the number of ways to choose horses for the second place is equals to the original problem. This is the reason why we use dp.

(This Solution idea is from Manuel Pinda)


#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              10056
#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
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//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 dp[1003][1003];
ll ans[1003];

ll nCr(int n, int r)
{
    if(r==1) return n;
    if(n==r) return 1;

    ll &amp;ret=dp[n][r];

    if(ret!=-1) return ret;

    return ret=(nCr(n-1,r-1)%MOD+nCr(n-1,r)%MOD)%MOD;
}

ll func(int n)
{
    if(n==0) return 1;
    if(ans[n]!=-1) return ans[n];

    ll ret=0;

    for(int i=1;i&lt;=n;i++)
    {
        ret+=(nCr(n,i)*func(n-i))%MOD;
        ret%=MOD;
    }

    return ans[n]=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);

    ms(dp,-1);
    ms(ans,-1);

    TEST_CASE(t)
    {
        int n;
        sf(n);
        PRINT_CASE;

        printf(&quot;%lld\n&quot;,func(n));

    }

    return 0;
}