497 - Strategic Defense Initiative
Moderator: Board moderators
The input set is not fully correct I think. My accepted code ignores blank lines. I think there is no special case. So, you can post your code.
Ami ekhono shopno dekhi...
HomePage
HomePage
fed up with TLE...
I have tried everythin but still i am getting TLE...
wat is the complexity required for this problem
First I coded using O(n2) and got TLE then i chked by submitting O(nlogk) solution from net...again I got TLE....i dont think I/O is a problem coz i have tried a lot of test cases......but still here is my I/O code:
if I/O is not a problem then i'll submit my whole code...can anyone help???
wat is the complexity required for this problem
First I coded using O(n2) and got TLE then i chked by submitting O(nlogk) solution from net...again I got TLE....i dont think I/O is a problem coz i have tried a lot of test cases......but still here is my I/O code:
Code: Select all
int main()
{
int n;
cin>>n;
string s;
getline(cin,s);
for(int kase=0;kase<n;kase++)
{
vector<int> x;
if(kase>0)
cout<<endl;
else
getline(cin,s);
while(getline(cin,s))
{
if(s.length()==0)
break;
const char *cs=s.c_str();
x.push_back(atoi(cs));
}
vector<int> y=lis(x),z;
cout<<"Max hits: "<<y.size()<<endl;
for(int i=0;i<y.size();i++)
cout<<x[y[i]]<<endl;
}
return 0;
}
-
- Learning poster
- Posts: 60
- Joined: Sun Apr 16, 2006 7:59 pm
Code: Select all
// Q497: Strategic Defense Initiative
// LIS(最長遞增子序列)
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#include <ctype.h>
using namespace std;
int main()
{
int n = 0;
vector<int> array, array2;
char str[11];
cin >> n;
getchar();
cin.getline(str, 11, '\n');
for(n--; n >= 0; n--)
{
array.clear();
array2.clear();
while(cin.getline(str, 11, '\n'))
{
if(strlen(str) == 0)
break;
array.push_back(atoi(str));
}
for(int i = 0; i < array.size(); i++)
{
if(array2.size() == 0)
array2.push_back(array[i]);
else
{
if(array2[array2.size()-1] < array[i])
array2.push_back(array[i]);
else if(array2.size() == 1)
array2[0] = array[i];
else if(array2[array2.size()-2] < array[i])
array2[array2.size()-1] = array[i];
}
}
cout << "Max hits: " << array2.size() << endl;
for(int i = 0; i < array2.size(); i++)
cout << array2[i] << endl;
if(n != 0)
cout << endl;
}
return 0;
}
Could somebody check it for me or give me some more I/O please?
Another question: After the last number, is there any '\n' before the EOF?
Your algorithm is not correct. You are checking only previous two elements which is wrong.
The answer is no.WingletE wrote:Another question: After the last number, is there any '\n' before the EOF?
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Experienced poster
- Posts: 162
- Joined: Thu Jul 13, 2006 7:07 am
- Location: Campus Area. Dhaka.Bangladesh
- Contact:
Re: Wa 497 Strategic Defense Initiative
i cant figure out why WA?
please help me.
code:
thanks in advanced.
please help me.
code:
Code: Select all
#include <cstdio>
#include <string>
#include <algorithm>
#define INF 1<<29
#define MAX 100000
using namespace std;
int A[MAX];
int L[MAX];
int P[MAX];
int maxLenth(int array[], int n){
int max = -INF,i;
for(i = 0; i<n; i++)
if(array[i] > max)
max = i;
return max;
}
void printPath(int P[],int p){
if(p == INF)
return;
printPath(P,P[p]);
printf("%d\n",A[p]);
}
void setInitial(int n){
for(int i = 0; i<n; i++){
P[i] = INF;
L[i] = 1;
}
}
int main(){
//freopen("in.txt","rt",stdin);
int input,i,j,max,n;
char str[20];
scanf("%d\n",&input);
while(input--){
i = 0;
while(gets(str) && strcmp(str,"")){
sscanf(str,"%d",&A[i++]);
}
n = i;
setInitial(n);
for(i = 0; i<n; i++){
for(j = i+1; j<n; j++){
if(A[i] < A[j] && L[j] < L[i]+1)
{
L[j] = L[i] + 1;
P[j] = i;
}
}
}
max = maxLenth(L,n);
printf("Max hits: %d\n",L[max]);
printPath(P,max);
printf("\n");
}
return 0;
}
Re: Wa 497 Strategic Defense Initiative
There an ambiguous segment in your code:
I think it's a good habit to avoid this type of things for clarity and precise functionality of functions.
Try out after recode..
You will get PE(I'm not sure if that gives WA) because
I let it be judged by your intelligence! Good luck..
Code: Select all
void printPath(int P[],int p){
// Two array-varialble in the same name P[], (one global, another local)
if(p == INF)
return;
printPath(P,P[p]);
printf("%d\n",A[p]);
}
Try out after recode..
You will get PE(I'm not sure if that gives WA) because
Also this function is absolutely wrong which might reward PE:(In description)
The outputs of two consecutive cases will be separated by a blank line.
Code: Select all
int maxLenth(int array[], int n){
int max = -INF,i;
for(i = 0; i<n; i++)
if(array[i] > max)
max = i;
return max;
}
Solving for fun..
-
- Learning poster
- Posts: 76
- Joined: Mon Jul 21, 2008 8:50 am
- Location: SUST,SYLHET,BANGLADESH.
- Contact:
RUNTIME ERROR 497 Strategic Defense Initiative
got AC. my mistake was the way of taking input......
thnks to mf.
Code: Select all
gets(str);
while(str[0]!=NULL)
{
array[i++]=atoi(str);
gets(str);
}
Last edited by calicratis19 on Thu May 21, 2009 11:47 am, edited 1 time in total.
Heal The World
Re: Wa 497 Strategic Defense Initiative
Well, this part of your code is wrong:
You have to check the return value of gets() to determine that you've reached EOF.
Code: Select all
while(str[0]!=NULL)
{
array[i++]=atoi(str);
gets(str);
}
-
- Learning poster
- Posts: 76
- Joined: Mon Jul 21, 2008 8:50 am
- Location: SUST,SYLHET,BANGLADESH.
- Contact:
Re: Wa 497 Strategic Defense Initiative
many many thanks to mf. this code gave me so much pain
i got ac. infinite thanks to mf

ps: no need to check for empty line . i think there is no input like that.




i got ac. infinite thanks to mf





ps: no need to check for empty line . i think there is no input like that.
Heal The World
Re: Wa 497 Strategic Defense Initiative
what's the reason of runtime error?
#include<iostream>
#include <vector>
#include<cctype>
#include<cstring>
using namespace std;
template<typename T> vector<int> find_lis(vector<T> &a)
{
vector<int> b, p(a.size());
int u, v;
if (a.size() < 1) return b;
b.push_back(0);
for (int i = 1; i < (int)a.size(); i++) {
if (a[b.back()] < a) {
p = b.back();
b.push_back(i);
continue;
}
for (u = 0, v = b.size()-1; u < v;) {
int c = (u + v) / 2;
if (a[b[c]] < a)
u=c+1;
else v=c;
}
if (a < a[b]) {
if (u > 0)
p = b[u-1];
b = i;
}
}
for (u = b.size(), v = b.back(); u--; v = p[v]) b = v;
return b;
}
int main()
{
int a[100000];
char in[100];
int n,ca = 1;
unsigned long i;
int size;
int check = 0;
i = 0;
int t;
cin >> t;
getchar();
getchar();
n = 0;
while(t--)
{
i = 0;
while(1)
{
gets(in);
if( strlen(in) == 0)
break;
n = atoi(in);
a = n;
i++;
}
size = sizeof(a[0])*i;
vector<int> seq(a, a+size/sizeof(a[0]));
vector<int> lis = find_lis(seq);
if(check == 1)
cout << "\n";
else
check = 1;
cout << "Max hits: ";
printf("%d\n",lis.size());
for ( i = 0; i < lis.size(); i++)
printf("%d\n", seq[lis]);
seq.clear();
lis.clear();
}
return 0;
}
#include<iostream>
#include <vector>
#include<cctype>
#include<cstring>
using namespace std;
template<typename T> vector<int> find_lis(vector<T> &a)
{
vector<int> b, p(a.size());
int u, v;
if (a.size() < 1) return b;
b.push_back(0);
for (int i = 1; i < (int)a.size(); i++) {
if (a[b.back()] < a) {
p = b.back();
b.push_back(i);
continue;
}
for (u = 0, v = b.size()-1; u < v;) {
int c = (u + v) / 2;
if (a[b[c]] < a)
u=c+1;
else v=c;
}
if (a < a[b]) {
if (u > 0)
p = b[u-1];
b = i;
}
}
for (u = b.size(), v = b.back(); u--; v = p[v]) b = v;
return b;
}
int main()
{
int a[100000];
char in[100];
int n,ca = 1;
unsigned long i;
int size;
int check = 0;
i = 0;
int t;
cin >> t;
getchar();
getchar();
n = 0;
while(t--)
{
i = 0;
while(1)
{
gets(in);
if( strlen(in) == 0)
break;
n = atoi(in);
a = n;
i++;
}
size = sizeof(a[0])*i;
vector<int> seq(a, a+size/sizeof(a[0]));
vector<int> lis = find_lis(seq);
if(check == 1)
cout << "\n";
else
check = 1;
cout << "Max hits: ";
printf("%d\n",lis.size());
for ( i = 0; i < lis.size(); i++)
printf("%d\n", seq[lis]);
seq.clear();
lis.clear();
}
return 0;
}
-
- New poster
- Posts: 2
- Joined: Sat May 07, 2011 6:39 pm
Re: Wa 497 Strategic Defense Initiative
i don't know why i get RE ......
Code: Select all
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cctype>
using namespace std;
int n,t;
char IN[10];
int s[100];
int dp[100];
int parent[100];
int anw;
void print(int x)
{
if(parent[x]!=-1)print(parent[x]);
cout<<s[x]<<endl;
}
main()
{
while(cin>>t)
{
cin.getline(IN,10);
cin.getline(IN,10);
while(t--)
{
n=-1;
while(cin.getline(IN,10))
{
if(strlen(IN)==0)break;
n++;
s[n]=atoi(IN);
}
n++;
for(int i=0;i<n;i++)dp[i]=1,parent[i]=-1;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
if(s[j]>s[i])
if(dp[i]+1>dp[j])
{
dp[j]=dp[i]+1;
parent[j]=i;
}
anw=0;
for(int i=0;i<n;i++)
anw=max(anw,dp[i]);
cout<<"Max hits: "<<anw<<endl;
for(int i=n-1;i>=0;i--)
if(dp[i]==anw)
{
print(parent[i]);
cout<<s[i]<<endl;
}
}
}
}
-
- New poster
- Posts: 36
- Joined: Fri Dec 02, 2011 1:30 pm
- Location: Kaohsiung, Taiwan
Re: Wa 497 Strategic Defense Initiative
Can anyone help with my WA~
Code: Select all
/*497*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int main ()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int amm;
scanf("%d",&amm);
char ss[100];
gets(ss);
gets(ss);
while (amm--)
{
int s[10000];
int g[10000];
int i=0;
while (1)
{
if(gets(ss)==NULL) break;
if(!strlen(ss)) break;
s[i++]=atoi(ss);
}
int str[10000];
int val[10000];int p=1;
int ans=1;
str[0]=s[0];
val[0]=p;
for (int j=1;j<i;j++)
{
//strengthen
if (s[j]>str[ans-1])
{
str[ans]=s[j];
val[ans]=p++;
ans++;
for (int l=ans-1;(l==ans-1||val[l+1]>val[l])&&l>=0;l--)
{
g[l]=str[l];
//printf("%d ",g[l]);
}
//puts("");
continue;
}
int pt=lower_bound(str,str+ans,s[j])-str;
val[pt]=p++;
str[pt]=s[j];
//printf("xx\n");
}
printf("Max hits: %d\n",ans);
for (int p=0;p<ans;p++)
printf("%d\n",g[p]);
if (amm)puts("");
}
return 0;
}
-
- New poster
- Posts: 36
- Joined: Fri Dec 02, 2011 1:30 pm
- Location: Kaohsiung, Taiwan
Re: Wa 497 Strategic Defense Initiative
I've passed all I/O I could find but still receive WA ,can anyone help??TKS
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: Wa 497 Strategic Defense Initiative
I got AC with this algorithm:
http://www.algorithmist.com/index.php/L ... sequence.c
http://www.algorithmist.com/index.php/L ... sequence.c
Check input and AC output for thousands of problems on uDebug!