Page 9 of 10

### Re: Wa 497 Strategic Defense Initiative

Posted: Fri May 04, 2012 12:03 pm
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?

### Re: Wa 497 Strategic Defense Initiative

Posted: Fri May 04, 2012 9:31 pm

### Re: Wa 497 Strategic Defense Initiative

Posted: Sat May 05, 2012 4:29 pm
TKS~
I get AC now!!!!

### Why Wa?? 497 Strategic Defense Initiative

Posted: Tue Feb 12, 2013 10:35 pm
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...............

### Re: Wa 497 Strategic Defense Initiative

Posted: Thu Feb 14, 2013 12:30 am
Don't print a blank line at the start of the output.

### Why WA in 497? Test Cases working fine!

Posted: Fri Apr 05, 2013 2:06 am
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;
}
``````

### Re: Wa 497 Strategic Defense Initiative

Posted: Tue Apr 09, 2013 3:14 am
There should be a newline at the end of the last line.

### 497- Strategic Defense Initiative...Getting WA

Posted: Sat Jun 22, 2013 8:51 pm

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

### Re: 497- Strategic Defense Initiative...Getting WA

Posted: Tue Jun 25, 2013 12:06 am
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``````

### Re: 497- Strategic Defense Initiative...Getting WA

Posted: Tue Nov 26, 2013 3:36 pm
cutt

### Re: 497- Strategic Defense Initiative...Getting WA

Posted: Tue Nov 26, 2013 11:33 pm
Don't print a blank line at the start of the output.

### 497 - Strategic Defense Initiative (Weird WA)

Posted: Tue May 06, 2014 9:14 pm
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
``````

### Re: 497 - Strategic Defense Initiative (Weird WA)

Posted: Wed May 07, 2014 9:11 pm
That code won't compile without the includes.
http://en.wikipedia.org/wiki/Longest_in ... ubsequence

### Re: 497 - Strategic Defense Initiative (Weird WA)

Posted: Thu May 08, 2014 6:11 am
brianfry713 wrote: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.

### Re: 497 - Strategic Defense Initiative (Weird WA)

Posted: Thu May 08, 2014 7:51 am
#include <cstdlib>

input:

Code: Select all

``````1

1
1
2
3
``````
AC output:

Code: Select all

``````Max hits: 3
1
2
3
``````