Category Archives: LIS

(timus) 1078. Segments

0
Posted on by 
/*
link: http://acm.timus.ru/problem.aspx?space=1&num=1078
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define MAXX 22

#define MAXX 10002

using namespace std;

struct DATA{

    int id, left, right;
};

bool comp(DATA a, DATA b)
{
    if(a.left < b.left)
    {
        return true;
    }
    else if(a.left == b.left)
    {
        return a.right < b.right;
    }
    else
    {
        return false;
    }
}


int cnt;

DATA ara[MAXX];

int LisLen = 0;
int L[MAXX];

void NlogK()
{
    int temp = cnt+1;
    int I[temp];
    I[0] = INF;

    FOR(i, 1, temp)
    {
        I[i] = -INF;
    }

    int left, u, right, mid;

    loop(i, cnt)
    {
        u = ara[i].right;
        left = 0;
        right = LisLen;


        while( left <= right )
        {
            mid = (left + right)/2;

            if(I[mid] > u)
            {
                left = mid+1;
            }
            else
            {
                right = mid - 1;
            }
        }

        I[left] = u;
        L[i] = left;

        LisLen = max(LisLen, left);
    }


}











int main()
{
    getint(cnt);

    loop(i, cnt)
    {
        ara[i].id = i;
        getint(ara[i].left); getint(ara[i].right);
    }

    sort(ara, ara+cnt, comp);

    NlogK();

    cout<<LisLen<<endl;

    int last_taken = -INF;


    for(int i=cnt-1; i>-1; i--)
    {
        if(L[i] == LisLen && ara[i].right > last_taken)
        {
            pf("%d", ara[i].id + 1);
            LisLen--;
            if(LisLen) pf(" ");
        }
    }
    pf("\n");






}

(UVa) 481 – What Goes Up

0
Posted on by 
/*
user: php
time: 0.040 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=422
*/

//sometimes input can be exact your macro. It may cause RTE along with WA. So use Trick.


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)

#define mod abs
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 100000
int INF = 0;

int cnt;
vector<int>input;
int LisLen = 0;
vector<int>result;


void Nlogk_LIS()
{
    int temp = cnt + 2;

    int pos[temp], L[temp];


    FOR(i, 1, temp)
    {
        pos[i] = INF;
    }
    pos[0] = -INF;



    loop(i, cnt)
    {
        int low = 0, high = LisLen, mid;
        while(low <= high)
        {
            mid = (low + high) / 2;

            if(pos[mid] < input[i])
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
        pos[low] = input[i];
        L[i] = low;
        LisLen = max(LisLen, low);
    }

    int last_taken = INF;
    result.pb(cnt);

    for(int i=LisLen; i>0; i--)
    {
        for(int j=result[LisLen - i] - 1; j>-1; j--)
        {
            if(L[j] == i && input[j] < last_taken)
            {
                result.pb(j);
                last_taken = input[j];
                break;
            }
        }
    }
}




int main()
{


    int n;
    while(getint(n)!= EOF)
    {
        input.pb(n);
        INF = max(INF, abs(n) );
    }

    INF += 2;

    cnt = SZ(input);
    Nlogk_LIS();
    pf("%d\n-\n", LisLen);

    for(int i=LisLen; i>0; i--)
    {
        pf("%d\n", input[ result[i] ]);
    }

}

(UVa) 10635 – Prince and Princess

0
Posted on by 
/*
user: php
time: 0.040 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1576
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf

using namespace std;

#define MAXX 251

int tmp, sc[MAXX*MAXX];
int n, p, q;
int pos[MAXX*MAXX];

int LIS()
{
    int I[MAXX*MAXX + 1];
    I[0] = -INF;

    FOR(i, 1, q)
    {
        I[i] = INF;
    }

    int LisLength = 0;
    loop(i, q)
    {
        int low, high, mid;
        low = 0;
        high = LisLength;

        while(low <= high)
        {
            mid = (low+high)/2;
            if(I[mid] < sc[i])
            {
                low = mid + 1;
            }
            else
            {
                high = mid - 1;
            }
        }
        I[low] = sc[i];
        if(LisLength < low)
        {
            LisLength = low;
        }
    }
    return LisLength;

}

int main()
{
    int kases, kaseno = 0;
    getint(kases);
    while(kases--)
    {
        getint(n); getint(p); getint(q);
        p++;
        q++;

        mem(pos, -1);

        loop(i, p)
        {
            getint(tmp);
            pos[tmp] = i+1;
        }

        loop(i, q)
        {
            getint(tmp);
            sc[i] = pos[tmp] - 1;

        }

        pf("Case %d: %d\n", ++kaseno, LIS() );

    }

    return 0;
}

(UVa) 10051 – Tower of Cubes

0
Posted on by 
/*
user: php
time: 0.108 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=992
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf


using namespace std;


int s(int c)
{
    if(c%2 == 0)
    {
        c++;
    }
    else
    {
        c--;
    }
    return c;
}



struct DATA{
    int pos, col;
    void set(int p, int c)
    {
        pos = p;
        col = c;
    }
};


DATA dir[502][7];
int numberofcubes;
int color[502][7];
int dp[502][7];

string name[] = {"front", "back", "left", "right", "top", "bottom"};

int longest(int pos, int c)
{
    int &ret = dp[pos][c];
    if(ret != -1) return ret;


    int nc;

    if(c % 2 == 0)
        nc = c + 1;
    else
        nc = c - 1;

    // c is the top color last;
    // nc is to be new color

    ret = 0;
    FOR(i, pos+1, numberofcubes)
    {
        loop(j, 6)
        {
            if(color[i][j] == color[pos][nc])
            {
                if( ret < longest(i, j) )
                {
                    ret = dp[i][j];
                    dir[pos][c].set(i, j);
                }
            }
        }
    }
    return ++ret;


}



int main()
{
    int maxcubes;
    int kaseno = 0;
    DATA it;
    bool blank = false;

    while(true)
    {
        getint(numberofcubes);
        if(numberofcubes == 0) break;
        loop(i, numberofcubes)
        {
            loop(j, 6)
            {
                getint(color[i][j]);
            }
        }

        mem(dp, -1);

        maxcubes = 0;

        loop(i, numberofcubes)
        {
            loop(j, 6)
            {
                if(maxcubes < longest(i, j) )
                {
                    it.set(i, j);
                    maxcubes = dp[i][j];
                }
            }
        }

        if(blank) pf("\n");
        blank = true;


        pf("Case #%d\n", ++kaseno);
        pf("%d\n", maxcubes);

        while(dp[it.pos][it.col] != 1)
        {
            pf("%d %s\n", it.pos+1, name[it.col].c_str());
            it.set(dir[it.pos][it.col].pos, dir[it.pos][it.col].col);
        }

        pf("%d %s\n", it.pos+1, name[it.col].c_str());




    }

    return 0;
}

(UVa) 10131 – Is Bigger Smarter?

0
Posted on by 
/*
user: php
time: 0.016 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1072
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf

using namespace std;


#define MAXX 1002

struct DATA{
    int weight, buddhi;
    int id;
};



int cnt;
DATA elephant[MAXX];
int dp[MAXX];
int dir[MAXX];

bool comp(DATA a, DATA b)
{
    return a.weight < b.weight;
}

int longest(int u)
{
    int &ret = dp[u];
    if(ret != -1) return ret;

    ret = 1;

    FOR(i, u+1, cnt)
    {
        if(elephant[u].weight < elephant[i].weight && elephant[u].buddhi > elephant[i].buddhi )
        {
            if(longest(i)+1 > ret)
            {
                dir[u] = i;
                ret = longest(i) + 1;
            }
        }
    }
    return ret;
}




int main()
{
    int w, s;
    cnt = 0;

    while(sf("%d%d", &elephant[cnt].weight, &elephant[cnt].buddhi) == 2)
    {
        cnt++;
    }
    loop(i, cnt)
    {
        elephant[i].id = i;
    }

    mem(dp, -1);
    mem(dir, -1);

    sort(elephant, elephant+cnt, comp);

    int n = -INF;
    int start;

    loop(i, cnt)
    {
        if(longest(i) > n)
        {
            start = i;
            n = longest(i);
        }
    }

    pf("%d\n", n);
    while(dir[start] != -1)
    {
        pf("%d\n", elephant[start].id + 1);
        start = dir[start];
    }
    pf("%d\n", elephant[start].id + 1);







    return 0;
}

(UVa) 111 – History Grading

0
Posted on by 
/*
user: php
time: 0.028 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=47
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf

using namespace std;

int currect[22];
int indx[22];
int dp[22];
int cnt;

int reclongest(int u)
{
    int &ret = dp[u];

    if(ret != -1) return ret;

    ret = 1;

    FOR(i, u+1, cnt)
    {
        if(currect[indx[u]] < currect[indx[i]])
        {
            ret = max(ret, reclongest(i)+1);
        }
    }

    return ret;

}



int main()
{


    cin>>cnt;
    int t;

    loop(i, cnt)
    {
        cin>>currect[i];
    }

    while(cin>>t)
    {

        mem(dp, -1);

        indx[t-1] = 0;

        FOR(i, 1, cnt)
        {
            cin>>t;
            indx[t-1] = i;
        }

        t = -1;

        loop(i, cnt)
        {
            t = max(t, reclongest(i));
        }

        cout<<t<<endl;
    }







    return 0;
}

(UVa) 437 – The Tower of Babylon

0
Posted on by 
/*
user: php
time: 0.016 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=378
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)

#define MAXX 187

using namespace std;

struct DATA{
    int sides[3];
    void get(int i, int j, int k)
    {
        sides[2] = i;
        sides[1] = j;
        sides[0] = k;

    }


};

DATA box[MAXX];
int dp[MAXX];
int len;



bool comp(DATA a, DATA b)
{
    return a.sides[0] < b.sides[0];
}


bool fcomp(DATA a, DATA b)
{
    return a.sides[0] < b.sides[0] && a.sides[1] < b.sides[1];
}




int longest(int u)
{
    int &ret = dp[u];
    if(ret != -1) return ret;

    ret = 0;

    for(int v=u+1; v<len; v++)
    {
        if( fcomp(box[u], box[v]) )
        {
            ret = max(ret, longest(v) );
        }
    }

    ret += box[u].sides[2];
    return ret;

}














int main()
{
    //read();
    int number_of_boxes;
    int ss[3];
    int j;
    int result;
    int kaseno = 0;

    while(true)
    {
        getint(number_of_boxes);
        if(number_of_boxes == 0) break;

        loop(i, number_of_boxes)
        {
            getint(ss[0]); getint(ss[1]); getint(ss[2]);




            j = 6*i;

            box[j].get(ss[0], ss[1], ss[2]);

            box[j+1].get(ss[0], ss[2], ss[1]);

            box[j+2].get(ss[1], ss[0], ss[2]);

            box[j+3].get(ss[2], ss[0], ss[1]);

            box[j+4].get(ss[1], ss[2], ss[0]);

            box[j+5].get(ss[2], ss[1], ss[0]);





        }


        len = number_of_boxes * 6;

        sort(box, box + len, comp );

        mem(dp, -1);

        result = -INF;

        loop(i, len)
        {
            result = max(result, longest(i) );
        }

        printf("Case %d: maximum height = %d\n", ++kaseno, result);
    }

    return 0;
}

(UVa) 231 – Testing the CATCHER

0
Posted on by 
/*
user: php
time: 0.024 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=167
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>

#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>



#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ size()
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)

#define MAXX 1000000

using namespace std;


int ara[MAXX];
int dp[MAXX];
int len;



int longest(int u)
{
    int &ret = dp[u];
    if(ret != -1) return ret;


    ret = 0;


    for(int v=u+1; v<len; v++)
    {
        if( ara[u] >= ara[v] )
        {
            ret = max(ret, longest(v));
        }
    }

    ret++;
    return ret;
}







int main()
{
    int inp;
    int kaseno = 0;
    bool blank = false;

    while(true)
    {

        getint(inp);
        if(inp == -1)
        {
            break;
        }

        ara[0] = inp;
        len = 1;

        while(true)
        {
            getint(inp);
            if(inp == -1)
            {
                break;
            }

            ara[len++] = inp;
        }


        mem(dp, -1);

        inp = -INF;

        loop(i, len)
        {
            inp = max(inp, longest(i));
        }


        if(blank) printf("\n");
        blank = true;

        printf("Test #%d:\n", ++kaseno);
        printf("  maximum possible interceptions: %d\n", inp);







    }

    return 0;
}