481 - What Goes Up

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

shantanu18
New poster
Posts: 22
Joined: Tue Jul 20, 2010 9:55 pm

Re: 481 - What Goes UP (Run Time Error)

Post by shantanu18 » Wed Jan 19, 2011 11:53 am

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
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 481 - What Goes UP (Run Time Error)

Post by zobayer » Wed Feb 02, 2011 6:41 pm

I think you should remove your code after getting AC, so that the forum will not have much spoilers...
You should not always say what you know, but you should always know what you say.

User avatar
adnim
New poster
Posts: 3
Joined: Fri Jan 13, 2012 4:21 pm

Re: 481-I/O needed

Post by adnim » Mon Jan 16, 2012 7:31 pm

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

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
clock ticks life away

nova
New poster
Posts: 4
Joined: Thu Dec 13, 2012 1:42 pm

Re: 481 - What Goes UP (Run Time Error)

Post by nova » Thu Dec 27, 2012 8:07 pm

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

Code: Select all

removed
Last edited by nova on Sun Dec 30, 2012 5:26 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 481 - What Goes UP (Run Time Error)

Post by brianfry713 » Sat Dec 29, 2012 11:36 pm

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
Check input and AC output for thousands of problems on uDebug!

nova
New poster
Posts: 4
Joined: Thu Dec 13, 2012 1:42 pm

Re: 481 - What Goes UP (Run Time Error)

Post by nova » Sun Dec 30, 2012 5:27 pm

Thank you brianfry713 :)

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

TL

Post by Yusif » Thu Jul 18, 2013 6:26 am

I cant figure out how it could be improved :(

Code: Select all

removed 

Last edited by Yusif on Fri Jul 19, 2013 8:31 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 481 - What Goes UP (Run Time Error)

Post by brianfry713 » Thu Jul 18, 2013 11:27 pm

Check input and AC output for thousands of problems on uDebug!

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

Re: 481 - What Goes UP (Run Time Error)

Post by Yusif » Fri Jul 19, 2013 8:30 am

Thank you! :)

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 481 - What Goes UP (Run Time Error)

Post by mahade hasan » Tue Nov 26, 2013 4:07 pm

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]
we r surrounded by happiness
need eyes to feel it!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 481 - What Goes UP (Run Time Error)

Post by brianfry713 » Tue Nov 26, 2013 11:31 pm

Make mx 1000000, then you'll get TLE.

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

Use binary search.
Check input and AC output for thousands of problems on uDebug!

fire_bot
New poster
Posts: 1
Joined: Wed Apr 02, 2014 10:18 pm

Re: 481 - What Goes UP (Run Time Error)

Post by fire_bot » Wed Apr 02, 2014 10:22 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 481 - What Goes UP (Run Time Error)

Post by brianfry713 » Fri Apr 04, 2014 12:06 am

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.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: 481 - What Goes UP (Run Time Error)

Post by jddantes » Sun May 04, 2014 11:42 am

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
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 481 - What Goes UP (Run Time Error)

Post by lbv » Sun May 04, 2014 7:40 pm

jddantes wrote: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?

Post Reply

Return to “Volume 4 (400-499)”