497 - Strategic Defense Initiative

[robinpahwa]

#include <cstdlib>

input:

Code: Select all

1

1
1
2
3

AC output:

Code: Select all

Max hits: 3
1
2
3

I have changed the code to handle this test case. I have already handled this before but got the WA so thought of handling 2 missiles at the same altitude, now I know it is wrong after reading this from the problem statement "once you hit a target, the next target can only be among the ones that are flying at higher altitudes than the one you just hit.".

But still it is a WA

Thanks for catching the #include <cstdlib> mistake, I removed that while pasting it here, I don't know why but the code works fine without it as well on my machine with C++11.

[brianfry713]

Input:

Code: Select all

1

935
323
314
59
484
455
939
783
567
159
176
633
327
755
236
375
743
804
916
192
771
547
311
966
370
876
100
584
337
617
571
623
940
236
33
775
43
972
557
961
130
84
593
808
838
181
535
932
984
450
124
107
996
786
424
717
661
524
300
350
492
222
972
431
810
5
557
204
328
113
164
809
548
108
968
386
288
502
317
624
951
792
82
298
577
505
15
590
380
666
939
872
240
262
654
49
266
563
252
593
675
767
753
223
874
721
960
514
222
628
489
525
420
570
822
348
74
188
289
806
854
227
29
445
489
682
493
106
244
96
51
271
214
803
845
439
523
156
952
97
783
440
621
554
9
794
254
435
334
542
592
187
121
620
983
609
653
475
66
249
922
116
871
135
271
67
573
793
222
877
241
356
316
213
910
677
7
163
463
340
56
54
878
176
25
860
136
677

My AC output:

Code: Select all

Max hits: 21
33
43
84
107
113
164
288
317
380
420
445
489
493
523
554
592
620
653
871
877
910

There may be other valid outputs for this input, but your code is only printing 19 values.

[robinpahwa]

There may be other valid outputs for this input, but your code is only printing 19 values.

I am getting this on my machine. Please see here https://ideone.com/sbz6py

My output:

Code: Select all

Max hits: 21
33
43
84
107
113
164
288
317
380
420
445
489
493
523
554
592
620
653
871
877
910

[brianfry713]

Look at the output at https://ideone.com/sbz6py
There are only 19 values.

[robinpahwa]

Look at the output at https://ideone.com/sbz6py
There are only 19 values.

How did you see that
Many thanks, it is now accepted

[brianfry713]

I used the diff command to compare the output of your code and my AC code.

[terry646623]

Why did I get wrong answer?

Code: Select all

#include<stdio.h>

int* seqlen;
int* address;
int* templisarray;
int* lisarray;   
                                      
void printarray(int array[],int len){
  int i;
  for(i=0;i<len;i++)
    printf("%d\n",array[i]);    }   

void lis(int array[],int len){
  int i,j,templis,maxlis=1,tempaddress,maxaddress=-1;  
  seqlen=(int*)malloc(sizeof(int)*1000000); 
  address=(int*)malloc(sizeof(int)*1000000);    
  seqlen[0]=1;
  address[0]=-1;
  for(i=1;i<len;i++){
     for(j=0;j<i;j++){
        if(array[i]>array[j]){               
           templis=seqlen[j];
           templis++;
           tempaddress=j;
           if(templis>maxlis){
              maxlis=templis;
              maxaddress=tempaddress; }
                                        } 
                                          }
     seqlen[i]=maxlis;
     address[i]=maxaddress;
     maxlis=1; 
     maxaddress=-1;                                   
                                       }  
                                        }
                                        
int highestaddress(int array[],int len){
  int i,max=0;   
  for(i=1;i<len;i++){
     if(array[i]>array[max])
        max=i;      } 
  return max;                   }                                                                            

int genlis(int array[],int len){
  int i=0,max;   
  templisarray=(int*)malloc(sizeof(int)*1000000);  
  max=highestaddress(seqlen,len);
  while(max!=-1){
     templisarray[i]=array[max];                  
     max=address[max];                 
     i++;                 }   
  return i;                             }
                               
void reverse(int len){
  int i=0,j;   
  lisarray=(int*)malloc(sizeof(int)*1000000);  
  for(j=len-1;j>=0;j--){
     lisarray[i]=templisarray[j];
     i++; } 
                                   }                               

int main(){
  int acase,i,number=0,highestlis,lisnumber;
  int *altitude;
  char temp;
  if(scanf("%d",&acase)!=1)
     return 0;
  scanf("%c",&temp);
  for(i=0;i<acase;i++){
     altitude=(int*)malloc(sizeof(int)*1000000);      
     while(1){
        if(scanf("%d",&altitude[number])!=1)
           break;
        else
           number++;    }   
     lis(altitude,number);
     lisnumber=genlis(altitude,number);
     reverse(lisnumber);
     highestlis=seqlen[highestaddress(seqlen,number)];
     printf("Max hits: %d\n",highestlis);
     printarray(lisarray,highestlis);
     number=0; 
     scanf("%c",&temp);      
     free(altitude); 
     free(seqlen);  
     free(address);
     free(templisarray); 
     free(lisarray);              }
  return 0;  }

[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

[richatibrewal]

I am continuously getting WA for this problem. I am using the algorithm of time complexity O(nlogk). Following is my code:

Code: Select all

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int m[100000],m_id[100000],p[100000],a[100000];
char str[10];
void print(int end)
{
    if(end<0)
        return;
    print(p[end]);
    printf("%d\n",a[end]);
}
int main()
{
    int n,l,l_end,i=0,pos,num;
    scanf("%d",&n);
    getchar();
    getchar();
  //  printf("hii");
    while(n--)
    {
        i=l=l_end=0;
        memset(m,0,sizeof(m));
        while(1)
        {
            if(n==0)
            {
                if(fgets(str,10,stdin));
                else
                    break;

            }
            else if(n!=0)
            {
                fgets(str,10,stdin);
                if(strlen(str)-1==0)
                    break;
            }
           // printf("dfjfhj %s  %d\n",str,strlen(str));
            num=atoi(str);
            a[i]=num;
            pos=lower_bound(m,m+l,num)-m;
            m[pos]=num;
            m_id[pos]=i;
            p[i]=pos>0?m_id[pos-1]:-1;
            if(pos==l)
            {
                l++;
                l_end=i;
            }
            i++;
        }
        printf("Max hits: %d\n",l);
        print(l_end);
        if(n)
            printf("\n");
    }
    return 0;
}

Others are giving inputs which have multiple outputs. But it is clearly written that :

Russian war tactics are fairly strange; their generals are stickers for mathematical precision. Their missles will always be fired in a sequence such that there will only be one solution to the problem posed above.

.

So I have ignored those test cases.

lastly as mentioned in the forum, I have used end of file marker to detect the end of input of the last case.

[brianfry713]

PM Sent