497 - Strategic Defense Initiative

[tzupengwang]

I got AC with this algorithm:
http://www.algorithmist.com/index.php/L ... sequence.c

Thanks a lot~
However,I know this O(n^2) algorithm
and I'm now trying a O(n*log n) algorithm, can anyone help?

[brianfry713]

http://www.algorithmist.com/index.php/L ... quence.cpp

[tzupengwang]

TKS~
I get AC now!!!!

[sonjbond]

My Code is giving me correct Output for sample Input & some other input from this forum .............. But I am getting WA ... Plz help me out ...........

My Code is here:

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
using namespace std;
vector<int>a;

void LIS_seq (int len)
{
    int lis [len + 10];
    int index_lis [len + 10];
    for ( int i = 0; i < len+10; i++ )
    {
        lis [i] = 1;
        index_lis [i] = -1;
    }

    for ( int i = 1; i < len; i++ )
    {
        for ( int j = 0; j < i; j++ )
        {
            if ( a [i] > a [j]&& lis [i] < lis [j] + 1 )
            {
                lis [i] = lis [j] + 1;
                index_lis [i] = j;
            }
        }
    }

    int max = 0;
    int indexNum=0;
    for ( int i = 0; i < len; i++ )
    {
        if ( lis [i] > max )
        {
            max = lis [i];
            indexNum = i;
        }
    }

    vector <int> final_list;
    final_list.clear ();
    while ( index_lis [indexNum] != -1 )
    {
        final_list.push_back (a [indexNum]);
        indexNum = index_lis [indexNum];
    }

    final_list.push_back (a [indexNum]);

    reverse (final_list.begin (), final_list.end ());

    printf ("Max hits: %d\n", final_list.size ());
    if(final_list.size()==1)
    {
        printf ("%d\n", a[len-1]);
        return;
    }
    for ( int i = 0; i < final_list.size (); i++ )
        printf ("%d\n", final_list [i]);
}

int main ()
{
    int length = 0;
    int kase;
    cin>>kase;
    getchar();
    getchar();
    puts("");
    int cas;
    for(cas=1; cas<=kase; cas++)
    {
        if(cas>1)
            printf("\n");
        length=0;
        char array[19];
        while ( gets(array) )
        {
            int len=strlen(array);
            if(array==NULL)break;
            if(len==0||array[0]=='\0')break;
            a.push_back(atoi(array));
            length++;
        }
        if(length==0)
        {
            printf ("Max hits: %d\n", length);
            continue;
        }
        LIS_seq(a.size());
        a.clear();
    }
    return 0;
}

Plz help me...............

[brianfry713]

Don't print a blank line at the start of the output.

[ljk]

I tested for the inputs in this thread, which work perfectly. Why WA? Thanks in advance.
Here's the code (simple LIS) [http://ideone.com/hihvoU] :

Code: Select all

#include<iostream>
#include<fstream>
#include<sstream>
#include<cstdio>
#include<stdlib.h>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<iomanip>

using namespace std;

typedef long long ll;
typedef string str;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef vector<ll> vin;
typedef vector<string> vs;
typedef vector<vector<ll> > vvin;

#define REP(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define BREP(i,a,b) for(ll i=a-1;i>=b;i--)
#define brep(i,n) BREP(i,n,0)
#define pb push_back
#define inf 999999999
#define SIZE 10000
#define mp make_pair
#define sz size()
#define NIL 0
#define DEBUG 0
#define all(vec) (vec).begin(),(vec).end()
#define NEG -1

vin heights(SIZE,NIL),ret(SIZE,NIL),predecessors(SIZE,NEG);
int last_boss;

void init() {
	rep(i,SIZE) {
		ret[i]=1;
		predecessors[i]=NEG;
	}
	last_boss=NEG;
}

void solve(int syze) {
	int max_len=NIL;
	vin temp;
	rep(i,syze)
		rep(j,i) {
			if(ret[j]+1>ret[i] && heights[j]<heights[i]) {
				ret[i]=ret[j]+1;
				predecessors[i]=j;
				if(max_len<ret[i]) {
					last_boss=i;
					max_len=ret[i];
				}
			}
		}
	cout<<max_len;
	while(last_boss!=-1) {
		temp.pb(heights[last_boss]);
		last_boss=predecessors[last_boss];
	}
	brep(i,temp.sz)
		cout<<"\n"<<temp[i];
}

int main() {
	int test_cases,height,index;
	stringstream ss;
	str str1;
	getline(cin,str1);
	ss<<str1;
	ss>>test_cases;
	getline(cin,str1); //for blank line
	rep(i,test_cases) {
		init();
		index=0;
		if(i!=0)
			cout<<"\n\n";
		while(getline(cin,str1)) {
			if(str1=="")
				break;
			stringstream converter;
			converter<<str1;
			converter>>height;
			heights[index++]=height;
		}
		cout<<"Max hits: ";
		solve(index);
	}
	return 0;
}

[brianfry713]

There should be a newline at the end of the last line.

[sun_kuet]

Code: Select all

#include <iostream>
#include<cmath>
#include<cstdio>
#include<vector>
using namespace std;
int lis_seqence[300000];
int L[300000];
int LIS(int n)
{
    for(int i=0;i<=n;i++)
        L[i]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(lis_seqence[i]<lis_seqence[j])
            {
                if(L[j]<L[i]+1)
                L[j]=L[i]+1;
            }
        }
    }
    int maxLength=0;
    for(int i=0;i<n;i++)
        if(maxLength<L[i])
            maxLength=L[i];
    cout<<"Max hits: "<<maxLength<<endl;
    return maxLength;
}
void LIS_find_sequence(int maxLength,int n)
{
    vector<int>v;
    int i;
    for(i=0;i<n;i++)
        if(maxLength==L[i])
            break;

    v.push_back(lis_seqence[i]);
    for(int j=i-1;j>=0;j--)
    {
        if((L[i]-L[j])==1 && lis_seqence[j]<lis_seqence[i])
        {
            int a = j;
            int b =j;
            int c = i;
            while(a!=-1)
            {
                if((L[i]-L[a])==1 && lis_seqence[a]<lis_seqence[i])
                {
                    c=a;
                    b=a;
                }
                a--;
            }
            i=c;
            j=b;
            v.push_back(lis_seqence[j]);
            i=j;
        }
    }
    for(i=v.size()-1;i>=0;i--)
        cout<<v[i]<<endl;
    v.clear();

}
int main()
{
    int b;

    cin>>b;
    getchar();
    getchar();
    string s;
    for(int j=1;j<=b;j++)
    {
        int k =0;
        while(1)
        {
            int a = 0;
            getline(cin,s);
            if(s=="")
                break;
            for(int i=0;i<s.size();i++)
                a = a +(s[i]-48);
            lis_seqence[k++] = a;
        }
            int maximum=LIS(k);
            LIS_find_sequence(maximum,k);
            if(j!=b)
                cout<<endl;
    }
    return 0;
}

Now where is the Wrong Brainfry after changing the code

[brianfry713]

Input:

Code: Select all

2

1
6
2
3
5

1
6
2
3
5

AC output:

Code: Select all

Max hits: 4
1
2
3
5

Max hits: 4
1
2
3
5

[mahade hasan]

cutt

[brianfry713]

Don't print a blank line at the start of the output.

[robinpahwa]

I am getting a weird WA in this problem and I don't know what could be wrong. Can somebody please verify my 2 assumptions and look to my code below:
1. altitudes could have same values in the input set.
2. There could be blank lines in the input set

Please suggest what could be wrong in this solution below:

Code: Select all

 Removed after getting accepted

[brianfry713]

That code won't compile without the includes.
http://en.wikipedia.org/wiki/Longest_in ... ubsequence

[robinpahwa]

That code won't compile without the includes.
http://en.wikipedia.org/wiki/Longest_in ... ubsequence

Thanks for replying brianfry713, please see the updated code with includes in my original post.

[brianfry713]

#include <cstdlib>

input:

Code: Select all

1

1
1
2
3

AC output:

Code: Select all

Max hits: 3
1
2
3