497 - Strategic Defense Initiative

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
kiha
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Mon Jan 12, 2004 6:18 pm

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 ;]
kiha

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Post by pavelph » Mon Jan 12, 2004 7:40 pm

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
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Wed Jan 14, 2004 12:07 am

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 :P [/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
Last edited by kiha on Mon Feb 09, 2004 9:24 pm, edited 1 time in total.
kiha

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Multiple input

Post by pavelph » Wed Jan 14, 2004 7:17 pm

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
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Wed Jan 14, 2004 9:38 pm

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 !
kiha

ccpz
New poster
Posts: 3
Joined: Sun Mar 02, 2003 5:25 am

497 runtime error?

Post by ccpz » Sun Feb 29, 2004 2:40 pm

[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
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky » Mon Mar 08, 2004 2:05 pm

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
New poster
Posts: 16
Joined: Mon Mar 01, 2004 4:00 pm
Location: Dhaka

497......RTE(SIGSEGV)

Post by rlatif119 » Fri Apr 23, 2004 7:35 pm

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 :cry: :roll: :x
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
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

497 Strategic Defense Initiative --- WA WHY???????????

Post by minskcity » Fri Jun 25, 2004 6:27 pm

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
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am

O(n * lg(m)) got AC in 0.002 sec.

Post by jackie » Wed Jul 21, 2004 9:18 am

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
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

497 Strategic Defense Initiative wrong answer ???????

Post by TISARKER » Mon Nov 01, 2004 8:21 pm

Thank u very much Finally I got accepted
Last edited by TISARKER on Tue Nov 02, 2004 8:09 pm, edited 1 time in total.
Mr. Arithmetic logic Unit

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Nov 02, 2004 8:13 am

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. :wink:
Good Luck..

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Tue Nov 02, 2004 10:33 am

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
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

Wa 497 Testing the catcher?

Post by Salman » Mon Aug 29, 2005 11:30 am

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
New poster
Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

497 - Strategic Defense Initiative

Post by Salman » Mon Aug 29, 2005 11:31 am

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;
}


Post Reply

Return to “Volume 4 (400-499)”