online-judge.uva.es

by **@ce** » Sat Jul 21, 2012 12:59 pm

Getting WA....plz help

Code: Select all: #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #include<stack> using namespace std; typedef struct nodex { int v; int z;//index }node; enum xyz {u,d,l}; node wt[10000]; node iq[10000]; int lcs[10000][10000]; xyz dir[10000][10000]; bool iq_sort(node a, node b) {return a.v < b.v; } bool wt_sort(node a, node b) {return a.v > b.v; } main() { int k = 1,mlis = 0,mind = -1; wt[0].v = -1; iq[0].v = -1; wt[0].z = -1; iq[0].z = -1; while(scanf("%d %d", &wt[k].v, &iq[k].v)!=EOF) { wt[k].z = k; iq[k].z = k; k++; } sort(wt+1,wt+k,wt_sort); sort(iq+1,iq+k,iq_sort); for(int i = 0;i<k;i++) { lcs[i][0] = 0; lcs[0][i] = 0; dir[0][i] = u; dir[i][0] = u; //cout<<arr1[i]<<" "<<arr2[i]<<endl; } for(int i = 1;i<k;i++) { for(int j = 1;j<k;j++) { if(wt[i].z == iq[j].z) { lcs[i][j] = lcs[i-1][j-1] + 1; dir[i][j] = d; } else if(lcs[i-1][j] >= lcs[i][j-1]) { lcs[i][j] = lcs[i-1][j]; dir[i][j] = u; } else { lcs[i][j] = lcs[i][j-1]; dir[i][j] = l; } } } /*for(int i = 1;i<k;i++) { for(int j = 1;j<k;j++) cout<<lcs[i][j]<<dir[i][j]<<" "; cout<<endl; }*/ printf("%d\n", lcs[k-1][k-1]); int p = k-1,q = k-1; while(p > 0 && q > 0) { if(dir[p][q] == d) { printf("%d\n", wt[p].z); p--; q--; } else if(dir[p][q] == u) p--; else q--; } //system("pause"); }

by **brianfry713** » Mon Jul 23, 2012 11:57 pm

Doesn't match the sample I/O.

by **37squared** » Sun Sep 16, 2012 5:04 pm

i tried all possible inputs i could on my program and matched with the toolkit... i m getting correct answers... but still getting wrong answer as judgement... i even got all the answers correct posted in this forum...
here is my code:(plz reply asap.. its kinda demoralizing)

#include<cstdio>
#include<iostream>
#include<utility>
#include<algorithm>

using namespace std;

int print_longestlength(int arr[],int n)
{
int max=0,i,pos=1;
for(i=1;i<=n;i++)
{
if(arr[i]>max)
{
max=arr[i];
pos=i;
}
}
cout<<max<<endl;
return(pos);
}

void print_subsequence(int arr[],int pos,int index[])
{
int sequence[1005]={0};
int i=2;
sequence[1]=pos;
while(arr[pos]!=0)
{
sequence[i]=arr[pos];
i++;
pos=arr[pos];
}

for(int j=i-1;j>1;j--)
cout<<index[sequence[j]]<<endl;
cout<<index[sequence[1]];
}

void longest_sequence(int wt[],int iq[],int n,int index[])
{
int dp[1005]={0};
int predecessor[1005]={0};
int i,j,pos=0,max,position;
dp[1]=1;
for(i=2;i<n;i++)
{
max=0,pos=0;
for(j=i-1;j>0;j--)
{
if(wt[j]<wt[i] && iq[j]>iq[i])
{
if(max<dp[j])
{
pos=j;
max=dp[j];
}
}
}
dp[i]=max+1;
predecessor[i]=pos;
}

/*cout<<"dp:\n";
for(i=1;i<n;i++)
cout<<dp[i]<<" ";
cout<<endl;

cout<<"predecessor:\n";
for(i=1;i<n;i++)
cout<<predecessor[i]<<" ";
cout<<endl;*/

position=print_longestlength(dp,n);
print_subsequence(predecessor,position,index);
}

void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}

void insertion_sort(int wt[],int iq[],int index[],int n)
{
int i,j;
for(i=2;i<n;i++)
{
j=i;
while((j>1) && (wt[j]<wt[j-1]))
{
swap(&wt[j],&wt[j-1]);
swap(&iq[j],&iq[j-1]);
swap(&index[j],&index[j-1]);
j-=1;
}
}
}

int main()
{
int i=1,k;
int weight[1005],iq[1005];
pair<int,int>data[1005];
int index[1005]={0};
/*int t;
cin>>t;*/

while(cin>>weight[i]>>iq[i])
{
index[i]=i;
i++;
}
if(i==1)
cout<<"";
else
{
insertion_sort(weight,iq,index,i);
cout<<endl;
/*for(k=1;k<i;k++)
{
cout<<index[k]<<" "<<k<<" "<<weight[k]<<" "<<iq[k]<<endl;
}*/

longest_sequence(weight,iq,i,index);
}
return 0;
}

plz give me more test cases if u can..

by **brianfry713** » Tue Sep 18, 2012 9:40 pm

Don't print a blank line at the start of the output.

by **37squared** » Sun Sep 23, 2012 1:07 pm

thx brainfry...got AC finally.

by **aczzdx** » Fri Feb 22, 2013 5:05 am

I'm just using dp to solve this problem, and I have passed the sample imput and some of data.
However I just always got WA,plz hlep,thanks.

Code: Select all: #include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> using namespace std; const int maxn = 100000; int w[maxn],q[maxn],r[maxn]; int d[maxn],maxlen = 1,bef[maxn]; int out[maxn]; int n; int cmp (const void *x,const void *y) { int i = *(int *)x, j = *(int *)y; if(w[i] != w[j]) return w[i] - w[j]; else return q[j] - q[i]; } int main() { #ifndef ONLINE_JUDGE freopen("data.in","r",stdin); freopen("data.out","w",stdout); #endif n = 0; while ( scanf("%d%d",&w[n],&q[n]) != EOF) n++; for(int i = 0; i < n; i++) r[i] = i; qsort(r,n,sizeof(r[0]),cmp); #ifndef ONLINE_JUDGE for(int i = 0 ; i < n; i++) printf("rank %d:(%d,%d)\n",i,w[r[i]],q[r[i]]); #endif memset(d,-1,sizeof(d)); memset(bef,-1,sizeof(bef)); d[0] = -1; d[1] = r[0]; for(int i = 1; i < n; i++) { int p = r[i]; if( w[p] == w[r[i-1]]) continue; if( q[p] < q[d[maxlen]] ) { d[maxlen+1] = p; bef[p] = d[maxlen++]; } else { int L = 1, R = maxlen; while ( L != R) { int M = (L+R) >> 1; if( q[M] < q[p]) R = M ; else L = M + 1; } if(q[L] == q[p]) continue; d[L] = p; bef[p] = d[L-1]; } #ifndef ONLINE_JUDGE printf(" i = %d: ",i); for(int j = 1; j <= maxlen; j++) printf("%d ",q[d[j]]); putchar('\n'); printf("**\n"); #endif } for(int p = d[maxlen],i = maxlen-1; p != -1; p = bef[p],i--) out[i] = p; if( n == 0) maxlen = 0; printf("%d\n",maxlen); for(int i = 0; i < maxlen; i++) { //if( i > 0) putchar('\n'); printf("%d\n",out[i]+1); } return 0; }

by **brianfry713** » Fri Feb 22, 2013 7:47 pm

input from tan_Yui in this thread

Code: Select all: 1 1 1 2 1 9998 1 9999 1 10000 2 1 2 2 2 9998 2 9999 2 10000 9998 1 9998 2 9998 9998 9998 9999 9998 10000 9999 1 9999 2 9999 9998 9999 9999 9999 10000 10000 1 10000 2 10000 9998 10000 9999 10000 10000 1 1 2 1 9998 1 9999 1 10000 1 1 2 2 2 9998 2 9999 2 10000 2 1 9998 2 9998 9998 9998 9999 9998 10000 9998 1 9999 2 9999 9998 9999 9999 9999 10000 9999 1 10000 2 10000 9998 10000 9999 10000 10000 10000

Correct output:

Code: Select all: 5 5 9 13 17 21

by **aczzdx** » Tue Mar 05, 2013 1:32 pm

Thx brianfry713, I've got AC finally.

by **hello442** » Wed Apr 03, 2013 2:33 pm

This is a DP LIS problem. I use nlgn algo but get WA. (n^2 algo works fine). What's wrong with the code? I've checked for several times... Who can show me the mistake or correct nlgn algo code? Thanks for help.

Code: Select all: #include<iostream> #include<algorithm> #include <cstring> #define MAX 1010 using namespace std; typedef struct { int weight; int IQ; int id; // the origin order }elephant; elephant data[MAX]; int D[MAX]; // D[k], the INDEX of largest last element in k-long sequence int pre[MAX]; // prior element of data[k] in sequence int res[MAX]; //For Output bool cmp(const elephant &a,const elephant &b){ if(a.weight != b.weight) return a.weight < b.weight; else return a.IQ < b.IQ; } void output(int pos,int size); void update(int l,int r,int pos); int N; int main(){ int w,iq,cnt=0; while(cin>>w>>iq){ data[cnt].weight = w; data[cnt].IQ = iq; data[cnt].id = cnt+1; cnt++; } memset(D,0,sizeof(D)); memset(pre,0,sizeof(pre)); N = cnt; sort(data,data+N,cmp); int size = 1; D[1]=0, pre[0] = -1; for(int i=1;i<N;i++){ if(data[i].IQ< data[D[size]].IQ){ pre[i] = D[size]; size++; D[size] = i; }else{ update(1,size,i); // update D via binsearch } } cout<<size<<endl; output(D[size],size); return 0; } void update(int l,int r,int pos){ int mid,value = data[pos].IQ; while(l<r){ mid = (l+r)/2; if(value>data[ D[mid] ].IQ){ r = mid; }else if(value < data[D[mid]].IQ){ l = mid + 1; }else{ return; } } if(l==r){ if(value==data[D[l]].IQ) return; pre[pos] = pre[D[l]]; D[l] = pos; } } void output(int pos,int size){ for(int i=0;i<size;i++){ res[i] = data[pos].id; pos = pre[pos]; } for(int i=size-1;i>=0;i--){ cout<<res[i]<<endl; } }

by **brianfry713** » Wed Apr 03, 2013 10:47 pm

http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

by **ljk** » Fri Apr 05, 2013 3:23 am

@brianfry:

I tested the i/p you gave and answer was perfect, but still getting WA. [Have used simple LIS with one change: I have also checked list of elephants from both ends because the output may not be a subsequence necessarily. [eg most intelligent and thinnest elephant may be at list end.]

Code:

Code: Select all: http://ideone.com/cTpjSt

by **brianfry713** » Wed Apr 10, 2013 12:33 am

hello442, try input:

Code: Select all: 4160 1859 9740 2446 7049 198 4536 5614 5227 1104 6810 3389 8133 515 7852 6960 9106 3294 7170 9973 5813 1512 9513 1079 6581 318 2811 7861 1091 1391 3249 5540 7986 1602 1799 9340 4954 1386 2489 2687 2427 6532 7046 5651 2610 560 3853 1249 7574 8067 5930 7374 8453 3386 55 5442 9654 1385 2776 2865 8405 744 2346 2376 1716 2742 4127 4144 6830 3021 9552 2968 8618 9257 6168 2950 550 7579 5645 6372 3745 8123 7861 1574 3368 8549 6286 7915 7132 3021 117 5413 7788 5536 4629 2462 2957 5855 8875 5107 8074 6139 1747 4779 7728 6691 621 4266 637 4629 2752 2617 4191 733 9282 6964 4878 3910 3282 1919 7331 8361 248 3398 2211 1470 7325 4876 9983 1520 4010 2551 7329 4408 7451 5756 21 1408 6037 8071 688 7009 7741 5140 2103 1230 5139 3374 5292 3332 1693 4772 4522 2622 4092 1940 3168 3084 4603 7768 318 3150 7557 4964 719 3999 1758 5007 9430 7091 4099 4146 9285 117 1346 8192 1565 7739 7423 2836 3959 6857 9478 9115 7406 8480 1564 3569 1336 573 74 2518 7482 8006 8356 3983 5341 4552 7995 113 4259 4770 4886 8445 6636 9895 3986 2583 1770 8201 5057 1408 522 5729 560 886 807 4279 4852 8475 7345 2142 6499 1277 5259 4826 5729 4854 4967 600 5369 3723 2168 5577 1823 6607 5541 5155 3355 5808 7215 7311 9391 4763 5649 4088 4719 6302 4777 2807 1300 9570 846 2121 3298 7799 9004 2457

AC output:

Code: Select all: 17 28 46 54 83 94 33 20 56 104 66 78 1 57 115 13 3 100

Your output

Code: Select all: 17 28 46 62 81 127 15 20 56 60 66 78 1 19 112 13 3 65

15 followed by 20 is wrong:
15: 1091 1391
20: 2489 2687
IQ's are not decreasing.

by **brianfry713** » Wed Apr 10, 2013 12:38 am

ljk, try the input I just posted. In order for the answer to be correct, n should be as large as possible. Your code prints n=11, it should be n=17.

online-judge.uva.es

10131 - Is Bigger Smarter?

Re: 10131 - Is Bigger Smarter?

Re: 10131 - Is Bigger Smarter?

Re: 10131 - Is Bigger Smarter?

Re: 10131 - Is Bigger Smarter?

Re: 10131 - Is Bigger Smarter?

Re: 10131 - Is Bigger Smarter?

Re:

Re: 10131 - Is Bigger Smarter?

Re: 10131 - Is Bigger Smarter?

Re: 10131 - Is Bigger Smarter?

Re: 10131 - Is Bigger Smarter?

Re: 10131 - Is Bigger Smarter?

Re: 10131 - Is Bigger Smarter?

Who is online