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

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

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

Post by jddantes » Mon May 05, 2014 6:18 am

It's RTE with either.

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 » Mon May 05, 2014 11:00 pm

With C++11, you're getting TLE.
http://en.wikipedia.org/wiki/Longest_in ... ubsequence
Use binary search.
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

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

Post by just_yousef » Wed Jul 30, 2014 11:23 pm

brianfry713
can you please give links to other problems that needs to be solved with binary search

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 31, 2014 8:55 pm

http://uhunt.felix-halim.net
Competitive Programming Exercises
Chapter 3. Problem Solving Paradigms
Divide and Conquer
Check input and AC output for thousands of problems on uDebug!

Shahidul.CSE
Experienced poster
Posts: 148
Joined: Sun Jul 13, 2014 4:32 am
Location: Rangpur, Bangladesh

Re: 481 - What Goes Up

Post by Shahidul.CSE » Mon Jan 05, 2015 9:09 pm

I solved it in O(nlogk)
Last edited by Shahidul.CSE on Sat Mar 19, 2016 4:57 pm, edited 1 time in total.
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
My facebook account,
Email me: shahidul.cse.brur@gmail.com

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 » Wed Jan 07, 2015 3:24 am

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

anando_du
New poster
Posts: 10
Joined: Sun Mar 01, 2015 3:11 pm

Re: 481 - What Goes Up

Post by anando_du » Wed Mar 04, 2015 9:46 am

O(n^2) solution will get TLE :P so must use O(nlogk) solution.

cunbidun
New poster
Posts: 3
Joined: Fri Oct 23, 2015 6:35 am

481 run time error

Post by cunbidun » Sat Oct 24, 2015 7:27 am

someone help me with my code plz
i dont understand why it cause run time error

Code: Select all

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


int main() {
  // freopen("lis.inp","r",stdin);
    int pred[1000],i,n,j,max=0,a[1000],s=0,l[1000],dmax,j0,x[1000],k,m,sa;
    i=1;
    while(scanf("%d",&sa)!=EOF)
    {
       a[i]=sa;
       i++;
    }
    n=i-1;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    l[1]=1;
    dmax=1;
    pred[1]=-1;
    pred[0]=-1;
for(i=2;i<=n;i++)
{
    max=0;
    j0=0;

    for(j=i-1;j>=1;j--)
        if(a[i]>a[j] && l[j]>max)
                {
                    max=l[j];
                    j0=j;
                }
        l[i]=max+1;
        pred[i]=j0;
        if(l[i]>=dmax) {dmax=l[i];k=i;}
}

    printf("%d\n",dmax);

       printf("-\n");


    m=0;
    while(k!=-1)
        {
            m++;
            x[m]=a[k];
            k=pred[k];
            if(k==0) break;
        }
    for(i=m;i>1;i--)
        printf("%d\n",x[i]);
        printf("%d\n",x[1]);

}
Last edited by brianfry713 on Tue Oct 27, 2015 3:11 am, edited 1 time in total.
Reason: Added code block

Post Reply

Return to “Volume 4 (400-499)”