481 - What Goes Up
Moderator: Board moderators
-
- New poster
- Posts: 12
- Joined: Tue Sep 21, 2004 10:08 pm
How do I solve 481 (What goes up)? PLZ HLP!!!
How do I solve the 481 (What goes up) problem more efficently?
I implemented the standard LIS algorithm, but it seems to be too slow.
I've tried implementing it using linked lists and some other things to improve the time, but stil keep on getting TLE.
Can anybody give me an idea to fasten my program up?
How did someone get 0.00.086 on this?
I implemented the standard LIS algorithm, but it seems to be too slow.
I've tried implementing it using linked lists and some other things to improve the time, but stil keep on getting TLE.
Can anybody give me an idea to fasten my program up?
How did someone get 0.00.086 on this?
-
- New poster
- Posts: 43
- Joined: Fri Jun 25, 2004 9:37 pm
481 Why WA?
i used the DP(LIS) which is O(n^2),that algorithm may cause TLE,but why i got WA?
is my algorithm okay?
is my algorithm okay?
Code: Select all
#include <iostream>
using namespace std;
int height[10000];
int len[10000];
int pre[10000];
int limit;
int i,j;
int maxlen;
int tail;
void output(int i)
{
if(pre[i] == -1)
{
cout << height[i] << endl;
}
else
{
output(pre[i]);
cout << height[i] << endl;
}
}
int main()
{
limit = 0;
maxlen = -1;
while(cin >> height[limit])
{
len[limit] = 1;
pre[limit++] = -1;
}
limit--;
for(i = 0;i < limit;i++)
{
for(j = i + 1;j <= limit;j++)
{
if(height[j] > height[i])
{
if(len[i] + 1 >= len[j])
{
len[j] = len[i] + 1;
pre[j] = i;
if(len[j] >= maxlen)
{
maxlen = len[j];
tail = j;
}
}
}
}
}
cout << maxlen << endl << '-' << endl;
output(tail);
return 0;
}
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius
-
- Experienced poster
- Posts: 120
- Joined: Sat Nov 01, 2003 6:16 am
- Location: Dhaka (EWU)
-
- New poster
- Posts: 21
- Joined: Sat Sep 25, 2004 3:35 am
- Location: Oaxaca de Ju
- Contact:
Wrong answer.
I am using the O(n log k) algorithm but I cannot get it accepted. Could you post some test cases?
WA
I am getting WA, in this problem, can anybody post some tested testcases.
I use long long number but, still WA!
my code, answer adrian Testcase correctly, and i don't know where is my bug.
can anybody help me?
I use long long number but, still WA!
my code, answer adrian Testcase correctly, and i don't know where is my bug.
can anybody help me?
481 WHY TLE
#include <fstream.h>
int k,a[1000000],n,cnt,max,d[1000000],p[1000000];
void prs(int aa){
if(p[aa]==-1){
cout << a[aa] << endl;
return;
}
prs(p[aa]);
cout << a[aa] << endl;
}
void main()
{
int i,j;
while(cin >> k){
p[cnt]=-1;
a[cnt++]=k;
}
n=cnt;
d[0]=1;
int max=-999;
for(i=0;i<n;i++){
cnt=0;
for(j=0;j<i;j++){
if(a>a[j]){
if(d<=d[j]){
d=d[j]+1;
p=j;
}
}
}
if(d>max)max=d;
}
for(i=0;i<n;i++){
if(max==d)break;
}
cout << d << endl << "-" << endl;
prs(i);
}
int k,a[1000000],n,cnt,max,d[1000000],p[1000000];
void prs(int aa){
if(p[aa]==-1){
cout << a[aa] << endl;
return;
}
prs(p[aa]);
cout << a[aa] << endl;
}
void main()
{
int i,j;
while(cin >> k){
p[cnt]=-1;
a[cnt++]=k;
}
n=cnt;
d[0]=1;
int max=-999;
for(i=0;i<n;i++){
cnt=0;
for(j=0;j<i;j++){
if(a>a[j]){
if(d<=d[j]){
d=d[j]+1;
p=j;
}
}
}
if(d>max)max=d;
}
for(i=0;i<n;i++){
if(max==d)break;
}
cout << d << endl << "-" << endl;
prs(i);
}
481 Compile Error Help me..
Code: Select all
#include <fstream.h>
#include <memory.h>
#define MAX 200005
typedef long long int LLINT
LLINT a[MAX],x[MAX],t,n,now,p[MAX],*aa[MAX],aacnt[MAX],go[MAX],gocnt,aanow,anum[MAX];
void BoundCheck(int i)
{
int *t;
if (anum[i] == 0) {
anum[i] = 20;
aa[i] = new LLINT[20];
}
else if (anum[i] <= aacnt[i]) {
t = new LLINT[anum[i]*2];
memcpy(t, aa[i], anum[i]*sizeof(int));
delete [] aa[i];
aa[i] = t;
anum[i] <<= 1;
}
}
void main()
{
int i,j,sw=0;
while(cin >> t){
a[n]=-2147483648;
x[n++]=t;
}
for(i=0;i<n;i++){
sw=0;
for(j=0;j<=now;j++){
if(x[i]<=a[j]){
a[j]=x[i];
sw=1;
aacnt[j]++;
BoundCheck(j);
aa[j][aacnt[j]]=x[i];
break;
}
}
if(sw==0){
anum[now] = 8;
aa[now] = new LLINT[8];
if(aacnt[now]==0){
aa[now][0]=x[i];
}
a[now++]=x[i];
}
}
for(i=0;i<now;i++){
aacnt[i]++;
}
cout << now << endl << "-" << endl;
go[gocnt++]=aa[now-1][0];
aanow=aa[now-1][0];
for(i=now-2;i>=0;i--){
for(j=0;j<aacnt[i];j++){
if(aa[i][j]<aanow){
go[gocnt++]=aa[i][j];
aanow=aa[i][j];
break;
}
}
}
for(i=now-1;i>=0;i--){
delete [] aa[i];
cout << go[i] << endl;
}
}
-
- Learning poster
- Posts: 98
- Joined: Sat Jan 21, 2006 12:45 pm
- Location: Busan,Corea(Republic of)
481 CE...
I got CE..
but why?
#include<iostream.h>
int n,cnt;
int a[100000],d[100000],pos[100000],path[100000];
int main(){
int i,j;
int q=0;
while(cin >> a[q]){
if(a[q]==-1) break;
q++;
}
int max=0,idx;
for(i=0;i<q;i++)
pos=-1;
for(i=0;i<q;i++){
d=1;
for(j=0;j<i;j++){
if(a>a[j] && d<d[j]+1){
d=d[j]+1;
pos=j;
}
}
if(max<d){
max=d;
idx=i;
}
}
path[cnt++]=idx;
while(pos[idx]!=-1){
path[cnt++]=pos[idx];
idx=pos[idx];
}
cout << q << endl << "-" << endl;
for(i=cnt-1;i>=0;i---)
cout << a[path] << endl;
n=cnt=0;
for(i=0;i<300;i++)
a=d[i]=pos[i]=path[i]=0;
return 0;
}
but why?
#include<iostream.h>
int n,cnt;
int a[100000],d[100000],pos[100000],path[100000];
int main(){
int i,j;
int q=0;
while(cin >> a[q]){
if(a[q]==-1) break;
q++;
}
int max=0,idx;
for(i=0;i<q;i++)
pos=-1;
for(i=0;i<q;i++){
d=1;
for(j=0;j<i;j++){
if(a>a[j] && d<d[j]+1){
d=d[j]+1;
pos=j;
}
}
if(max<d){
max=d;
idx=i;
}
}
path[cnt++]=idx;
while(pos[idx]!=-1){
path[cnt++]=pos[idx];
idx=pos[idx];
}
cout << q << endl << "-" << endl;
for(i=cnt-1;i>=0;i---)
cout << a[path] << endl;
n=cnt=0;
for(i=0;i<300;i++)
a=d[i]=pos[i]=path[i]=0;
return 0;
}
Archaan
CAN YOU BEAT ME?
http://acm.uva.es/problemset/usersjudge.php?user=19788
AND,
http://acm.uva.es/problemset/submit.php
http://online-judge.uva.es/problemset/submit.php
SUBMIT AND GET AC!!!
CAN YOU BEAT ME?
http://acm.uva.es/problemset/usersjudge.php?user=19788
AND,
http://acm.uva.es/problemset/submit.php
http://online-judge.uva.es/problemset/submit.php
SUBMIT AND GET AC!!!
and another one asking for help - 481"What Goes Up"
Hello everyone!
I read in Halim's website the explanation of O(nlog(k)) algo for LIS,
it seems I have grasped the main idea(for I got AC 231-"Testing the Catcher"), but how to restore the LIS itself and even how to maintain the predecessor array- it is still a mystery for me...
Would you be so kind to explain what is the the crux?
Is this multiple input problem?
If you want to cast a glance on my code (which invariably gives WA, though behaves well for my own I/O
), I'll send it immediately.
Algoritmist website also very good for this problem, I thank them too
Thank you.
I read in Halim's website the explanation of O(nlog(k)) algo for LIS,
it seems I have grasped the main idea(for I got AC 231-"Testing the Catcher"), but how to restore the LIS itself and even how to maintain the predecessor array- it is still a mystery for me...
Would you be so kind to explain what is the the crux?
Is this multiple input problem?
If you want to cast a glance on my code (which invariably gives WA, though behaves well for my own I/O
![:)](./images/smilies/icon_smile.gif)
Algoritmist website also very good for this problem, I thank them too
Thank you.