497 - Strategic Defense Initiative

[kiha]

Hmmm ... thanks pavelph , now I understand ...

Hey , did you try to use readln instead of val ? Because when you use val on the empty string ( '' ) it may give you some value , and readln reads until it finds the integer value .

And please explain this algorithm to me ;]

[pavelph]

Hi, kiha.
You can't use only readln becouse this problem have multiple input! and if you don't check that s<>'' then program reads all input file as one case and of course you will have WA.

About algo of this problem you can read here: http://www.comp.nus.edu.sg/~stevenha/pr ... g_dp1.html chapter 2.4. Longest Inc/Decreasing Subsequence (LIS/LDS).

Hope it can help you.[/i]

[kiha]

Hi,

thanks for the source of this algorithm I read this , understood , but my program doesn't work

I hate putting here unworking codes , but now - no matter what I change I always get WA

[pascal] I deleted the code [/pascal]

Can somebody help me ? Maybe you can give me some test cases on which my program doesn't work . I tested it on many tests and it gives the right answer ! Maybe I read the input data wrongly . Please help


-------
Some things that may help you understanding my code:
t - array where I store the heights of the missiles [or sth]
pre - array of precedessors
wyn - array of utput data
tmp - array of maximum LIS length

[pavelph]

I have already siad that this problem have multiple input. If you didn't know what it meens you can see it at http://acm.uva.es/problemset/minput.html

[kiha]

Oh ... :/

Thanks, I've got Accepted it now ;]

I didn't read this description of Multiple Input problems. However , when I read raymond's program I understood that the first number is the number of the test cases . But I didn't know that after this number there is a blank line - one simple readln and AC .

Thanks one more time !

[ccpz]

[cpp]
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
using namespace std;

int data[50];
int temp[50]={-1};
int length[50]={1};

void show(int i)
{
if(temp!=-1)
show(temp);
cout<<data<<endl;
}

void reset()
{
for(int i=0;i<50;i++)
{
data=0;
temp=-1;
length=1;
}
}

int main()
{
char tmp[10];
int t;
int n=0;
int max_j;
cin>>t;
fflush(stdin);
gets(tmp);
for(int a=1;a<=t;a++)
{
n=0;
max_j=0;
reset();
while(1)
{
fflush(stdin);
gets(tmp);
if(strcmp(tmp,"")==0) break;
data[n]=atoi(tmp);
n++;
}
n--;
for(int i=0;i<n;i++)
for(int j=i+1;j<=n;j++)
{
if(data[j]>data && length+1>length[j])
{
length[j]=length+1;
max_j=j;
temp[j]=i;
}
}

cout<<"Max hits: "<<length[max_j]<<endl;
show(max_j);
}
//system("pause");
return 0;
}
[/cpp]
here is my code,and I always got runtime error
can anyone help me find where the problem is?

[sidky]

i didn't check your code thoroughly, but possibly you should make your data array bigger. my AC prog is capable of handling 1000 heights.

[rlatif119]

My code generates Run Time Error (SIGSEGV). Very common error for this problem, i know. I think i've used sufficiently large array. Can someone please help me to get rid of this problem? I am just fadeup
Here is my code
[c]

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void Longest_sequence(long *height,long *length,long *predecessor);
void display(long i,long *predecessor, long *height);

long total;
char str[100];


main()
{
long i,j,n;
long height[10000],length[10000],predecessor[10000];

scanf("%ld",&n);
fflush(stdin);
gets(str);

while(n>0)
{
i=0;
while(1)
{
fflush(stdin);
gets(str);
if(strcmp(str,"")==0) break;
height = atoi(str);
length = 1;
predecessor = -1;
i++;
}
total = i;
Longest_sequence(height,length,predecessor);
--n;

}


}


void Longest_sequence(long *height,long *length,long *predecessor)
{
int i,j,x;

for (i=0; i<total-1;++i)
{
for (j=i+1;j<total;++j)
{
if (height[j] > height)
{
if (length + 1 > length[j])
{
length[j] = length + 1;
x=j;
predecessor[j] = i;
}
}
}
}

printf("Max hits: %ld\n",length[x]);
display(x,predecessor,height);
printf("\n");
}

void display(long i,long *predecessor, long *height)
{
if(predecessor!=-1)
{
display(predecessor,predecessor,height);
}

printf("%ld\n",height);
}
[/c]

[minskcity]

I've read all post on this problem. I get correct output for every input I tried... What's wrong with the code??????? [cpp]#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

vector < long long > data, help;
long long temp;
long t;
string s;

int main(){
cin >> t;
getline(cin, s);
getline(cin, s);

while(t--){
data.clear();
while(getline(cin, s) && s.size()){
istringstream sin(s);
sin >> temp;
data.push_back(temp);
}

help.clear();
help.resize(data.size() + 5, 999999999);
help[0] = -999999999;

for(unsigned long i = 0; i < data.size(); i++){
long long u = data.size();
long long d = 0;
while(u - d > 1)
if(help[(u + d)/2] >= data) u = (u + d)/2;
else d = (u + d)/2;
help[d + 1] <?= data;
}

long ans = 0;
while(help[ans + 1] != 999999999) ans++;

cout << "Max hits: " << ans << endl;
for(long i = 1; i <= ans; i++)
cout << help << endl;

if(t) cout << endl;

}

return 0;
}
[/cpp]

[jackie]

After getting many many WA, finally I got AC in 0.002 sec.

I use DP (LIS) algorithm and it's O(n*lg(m)) (m is the length of subsequece)

I don't think there is any zero input case, because i use assert to verify it.

I don't think it's a multiple right answer problem either. I just print the one i got.

Here is my input and output.
Hope it will help.

[cpp]//DP O(n * lg(m))
#include <cstdio>
#include <algorithm>
#include <cassert>
using namespace std;
int main()
{
// freopen("497.out", "w", stdout);
// freopen("497.in", "r", stdin);
int cnt, print[10001];
char buf[15];
scanf("%d", &cases);
getchar();
getchar();
for (NULL; cases--; NULL)
{
cnt = 0;
while (gets(buf) && buf[0])
input[cnt++] = atol(buf);
assert(cnt != 0);
//DP LIS

printf("Max hits: %d\n", r);

for (i = index - 1; i >= 0; --i)
printf("%d\n", print);

if (cases)
printf("\n");
}
return 0;
}[/cpp]

[TISARKER]

Thank u very much Finally I got accepted

[shamim]

The way you are taking input is not correct.

The first line has the number of test cases.
Then each test case has sevral lines, each with one number.

You should actually first read each number using gets(), and then use strlen() to check if this is simply a blank line. If it is not, use sscanf() to extract the number.
Good Luck..

[Raiyan Kamal]

Try these cases :

INPUT

Code: Select all

6

1
2
3
4
5

5
4
3
2
1

1



1
3
4
2
5
6

OUTPUT:

Code: Select all

Max hits: 5
1
2
3
4
5

Max hits: 1
1

Max hits: 1
1

Max hits: 0

Max hits: 0

Max hits: 5
1
3
4
5
6

[Salman]

WA Why?Need some LIS expert? Have some prolem to discuss with?

Code: Select all

/*
Name: Testing the catcher
Number: 497
Type : lis  
Process : ON
Author :Salman Zaman
Email : zamansalman@gmail.com
Date : 26/08/05 23:31





*/



#include<stdio.h>
#include<string.h>



//#include<conio.h>

#define SIZE 10000


int height[SIZE];
int length[SIZE];
int predecessor[SIZE];

void lis(int n){
 
    int i,j,k;
    for(i=1;i<=n;i++){
        length[i]=1;
        predecessor[i]=0;
    }    
    
    for(i=1;i<=n-1;i++){
        for(j=i+1;j<=n;j++){
            if(height[j]>height[i]){
                if(length[i]+1 >length[j]){
                    length[j]=length[i]+1;
                    predecessor[j]=i;
                                        
                }    
            }    
        }    
    }    
          
    
    
}

void print_lis(int total,int max,int startpoint){
    int i,j;
    
    for(i=startpoint,j=0;i>=0;j++){
        length[j]=height[i];
        if(j==max-1){
            break;
            
        }   
        i=predecessor[i]; 
    }    
    
    for(i=j;i>=0;i--){
        printf("%d\n",length[i]);
    }    
    
}    
int main(){

       char ch;
 
       char input[1000];
       int i,a,j,k,n,temp;
 
  //     freopen("497.txt","r",stdin);
  
       gets(input);
        sscanf(input,"%d",&n);
        gets(input);
        for(i=0;i<n;i++,printf("\n")){
            j=1;
            while(gets(input)&& strcmp(input,"")!=0){
                
                sscanf(input,"%d",&height[j]);
                j++;
                
            }    
            lis(j-1); 


           printf("Max hits: %d\n",length[j-1]);
            temp=length[j-1];
           print_lis(j-1,temp,j-1);

     }     
     
//   getch();
   return 0;
}

[Salman]

WA Why?Need some LIS expert? Have some prolem to discuss with?

Code: Select all

/*
Name:  Strategic Defense Initiative  
Number: 497
Type : lis  
Process : ON
Author :Salman Zaman
Email : zamansalman@gmail.com
Date : 26/08/05 23:31





*/



#include<stdio.h>
#include<string.h>



//#include<conio.h>

#define SIZE 10000


int height[SIZE];
int length[SIZE];
int predecessor[SIZE];

void lis(int n){
 
    int i,j,k;
    for(i=1;i<=n;i++){
        length[i]=1;
        predecessor[i]=0;
    }    
    
    for(i=1;i<=n-1;i++){
        for(j=i+1;j<=n;j++){
            if(height[j]>height[i]){
                if(length[i]+1 >length[j]){
                    length[j]=length[i]+1;
                    predecessor[j]=i;
                                        
                }    
            }    
        }    
    }    
          
    
    
}

void print_lis(int total,int max,int startpoint){
    int i,j;
    
    for(i=startpoint,j=0;i>=0;j++){
        length[j]=height[i];
        if(j==max-1){
            break;
            
        }   
        i=predecessor[i]; 
    }    
    
    for(i=j;i>=0;i--){
        printf("%d\n",length[i]);
    }    
    
}    
int main(){

       char ch;
 
       char input[1000];
       int i,a,j,k,n,temp;
 
  //     freopen("497.txt","r",stdin);
  
       gets(input);
        sscanf(input,"%d",&n);
        gets(input);
        for(i=0;i<n;i++,printf("\n")){
            j=1;
            while(gets(input)&& strcmp(input,"")!=0){
                
                sscanf(input,"%d",&height[j]);
                j++;
                
            }    
            lis(j-1); 


           printf("Max hits: %d\n",length[j-1]);
            temp=length[j-1];
           print_lis(j-1,temp,j-1);

     }     
     
//   getch();
   return 0;
}