481 - What Goes Up

[shantanu18]

Why WA! please help...

Code: Select all

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
#define MAX 1000000
#define inf 0x3f3f3f3f
using namespace std;
vector <int> arr;
int prev[MAX];
map <int,int> mp;
void print(int n)
{
	if(n==-inf) return;
	else
	{
		print(prev[mp[n]]);
		printf("%d\n",n);
	}
}
int main()
{
	//freopen("481.txt","r",stdin);
	int n;
	arr.push_back(-inf);
	vector <int> vec;
	vector<int>::iterator low;
	while(cin>>n)
	{
		vec.push_back(n);
		arr.push_back(inf);
	}
	
	int length = vec.size();
	int count=0;
	int k=0;
	for(int i=0;i<length;i++)
	{
		low = lower_bound(arr.begin(),arr.end(),vec[i]);
		arr[low-arr.begin()]=vec[i];
		
		if(mp.find(vec[i])==mp.end()) mp[vec[i]]=k++;
		
		prev[mp[vec[i]]] = arr[low-arr.begin()-1];
	}
	
	for(int i=1;arr[i]<inf;i++) count++;
	cout<<count<<endl<<"-"<<endl;
	print(arr[count]);
	return 0;
}

[zobayer]

I think you should remove your code after getting AC, so that the forum will not have much spoilers...

[adnim]

be careful the fist test case is a blank line.
hope helps.

input

Code: Select all

13


9
1
8
2
7
3
6
4
5
5
4
6
3
7
2
8
1
9

3
2
2
3

1

1
1

1
2

2
1

1
2
1

2
1
2

1
2
1
2

1
2
1
3

2
3
1
2
3

1
-2
0
-1
1

output

Code: Select all

Max hits: 0

Max hits: 9
1
2
3
4
5
6
7
8
9

Max hits: 2
2
3

Max hits: 1
1

Max hits: 1
1

Max hits: 2
1
2

Max hits: 1
1

Max hits: 2
1
2

Max hits: 2
1
2

Max hits: 2
1
2

Max hits: 3
1
2
3

Max hits: 3
1
2
3

Max hits: 3
-2
-1
1

[nova]

anybody please tell me what's wrong with my code? im gettin WA

Code: Select all

removed

[brianfry713]

Input:

Code: Select all

1825198813
703574781
1357013548
882614101
91123810
693635462
509962994
13091984
476503935
692987701
845877457
484660669
2118992354
1583536068
1830890927
125909470
389054618
61633602
1167630334
1245222478
1653407157
1539092241
1260848996
1092105640
1343321214
1337792438
743752911
895144236
644021011
306984050
206209071
1968038758
694647582
627044827
1228453736
923849393
994690063
1935458528
351391203
1747161030
1759120300
1040627854
1076069512
1110842238
2104791827
326007565
159295061
522217290
1564248899
459709341
368308305
510183713
1141726537
2069288597
94198657
557718943
1355469954
1075065596
1830809408
660014489
1515539776
750393546
518211796
692879112
1918631132
533634230
1974805736
1999632389
616397282
1170189545
315109278
834252002
1161967889
103216749
1534876392
998665307
1795057301
1251226459
900157290
1509113371
1092226810
1988172767
2128641328
1107418067
48984604
1391219046
1763691983
435334167
1137289136
78170531
1100176263
795618180
2087635596
893474920
1313562613
1238129761
314970551
566882611
2043820790
1354652240

AC output:

Code: Select all

17
-
13091984
125909470
389054618
644021011
694647582
923849393
994690063
1040627854
1076069512
1110842238
1141726537
1355469954
1515539776
1534876392
1795057301
1988172767
2043820790

[nova]

Thank you brianfry713

[Yusif]

I cant figure out how it could be improved

Code: Select all

removed 

[brianfry713]

http://en.wikipedia.org/wiki/Longest_in ... ubsequence

Use binary search.

[Yusif]

Thank you!

[mahade hasan]

getting WAAAA
help need

Code: Select all

#include<stdio.h>
#include<string.h>
#define mx 100000
long n=0;
long value[mx];
long dp[mx]={0},dir[mx]={0};

void solution(long start)
{  
    while(start!=0)
    {
        printf("%ld\n",value[start]);
        start=dir[start];
    }
    //printf("%d\n",value[start]);
}


long longest(long u)
{
    if(dp[u]!=0) return dp[u];
    long maxi=0;
    //printf("now u=%d  max=%d\n",u,maxi);
    for(long v=u+1;v<=n;v++) //1? ????,v>u
    {
        if(value[v]>value[u]) //2? ????, value[v]>value[u]
        {
            if(longest(v)>=maxi) //????????? ????? ?????
            {
                maxi=longest(v);
                //printf("maxi=%d\n",maxi);
                                dir[u]=v;
 
            }
        }
        //getchar();
    }
    dp[u]=1+maxi; //1 ???? ??? ???? u ????? ??????? ????? ????? ???
    return dp[u];
}
int main()
{
    char Input[1000];
    //READ("in");
    //memset(dp,-1,sizeof dp);
        //memset(dir,-1,sizeof dir);
    
    while(gets(Input)){
        //if(strlen(Input)==0) break;
        long M=0;
        long L=0;
        bool Flag=0;
        while(Input[L]){
           if(Input[L]=='-') Flag=1;
           else if(Input[L]>='0'&&Input[L]<='9')
           M=M*10+Input[L]-'0';
           L++;
        }
        value[++n]=M;
        if(Flag) value[n]*=-1;
        //printf("-->%ld\n",value[n]);
    }
    //sort(value+1,value+n+1);
    //--n;
    //printf("n=%d\n",n);
    
    long LIS=0,start;
    for(long i=1;i<=n;i++)
    {
        //printf("longest path from %d: %d\n",i,longest(i));
        if(longest(i)>=LIS)
        {
            LIS=longest(i);
            start=i;
        }
    }
    printf("%ld\n-\n",LIS);
    if(LIS>0)
    solution(start);
    
    
    //printf("LIS = %d Starting point %d\n",LIS,start);
    
     //getchar();getchar();
    return 0;  
}

[/color]

[brianfry713]

Make mx 1000000, then you'll get TLE.

http://en.wikipedia.org/wiki/Longest_in ... ubsequence

Use binary search.

[fire_bot]

My AC yielded abit different ending result for brianfry713 input.
Here is my AC output:

Code: Select all

17
-
13091984
125909470
389054618
644021011
694647582
923849393
994690063
1040627854
1076069512
1110842238
1141726537
1355469954
1515539776
1534876392
1795057301
1988172767
2128641328

[brianfry713]

If the input contains more than one longest subsequence, the output file should print the one that occurs last in the input file.
Our AC outputs only differ in the last number printed.
The last number my code prints is 2043820790, which occurs later in the input file than the last number your code prints 2128641328.

[jddantes]

Why is mine RTE?

Code: Select all

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){

    vector<int> arr;

    int d;
    while(scanf("%d",&d)!=EOF){
        //if(d==-1000)
            //break;
        arr.push_back(d);
    }

    int i, j;
    int n = arr.size();

    //for(i=0; i<n; i++)
       // printf("%d\n",arr[i]);

    int len[n];

    int max_len = 0;
    int max_i = 0;

    vector< vector<int> > v;

    for(i=0; i<n; i++){
        len[i] = 1;

        v.push_back(vector<int> {arr[i]});

        for(j=0; j<i; j++){
            if(arr[j] < arr[i] && len[j] + 1 > len[i]){
                len[i] = len[j] + 1;

                v[i] = v[j];
                v[i].push_back(arr[i]);
            }

            if(len[i] >= max_len) {
                max_len = len[i];
                max_i = i;
            }
        }
    }

    printf("%d\n-\n",max_len);
    for(i=0; i<v[max_i].size(); i++){
        printf("%d\n",v[max_i][i]);
    }


    return 0;
}

[lbv]

Why is mine RTE?

This is what I see when I try to compile your code with g++ and no special flags:

Code: Select all

p.cpp: In function ‘int main()’:
p.cpp:36:15: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]
   v.push_back(vector < int > {
               ^

And then, immediately after I run it:

Code: Select all

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
Aborted

If I pass the -std=c++11 flag, it seems to compile and run fine. Did you make your submission as regular C++, or as C++11?