## 10131 - Is Bigger Smarter?

Moderator: Board moderators

@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

### Re: 10131 - Is Bigger Smarter?

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");
}
``````
-@ce

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

### Re: 10131 - Is Bigger Smarter?

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

37squared
New poster
Posts: 6
Joined: Sun Sep 16, 2012 4:15 pm

### Re: 10131 - Is Bigger Smarter?

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>max)
{
max=arr;
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=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 && iq[j]>iq)
{
if(max<dp[j])
{
pos=j;
max=dp[j];
}
}
}
dp=max+1;
predecessor=pos;
}

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

cout<<"predecessor:\n";
for(i=1;i<n;i++)
cout<<predecessor<<" ";
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>>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..

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

### Re: 10131 - Is Bigger Smarter?

Don't print a blank line at the start of the output.
Check input and AC output for thousands of problems on uDebug!

37squared
New poster
Posts: 6
Joined: Sun Sep 16, 2012 4:15 pm

### Re: 10131 - Is Bigger Smarter?

thx brainfry...got AC finally.

aczzdx
New poster
Posts: 3
Joined: Thu Jan 17, 2013 12:01 pm

### Re: 10131 - Is Bigger Smarter?

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;
}``````
Just a newbie

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

### Re:

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

aczzdx
New poster
Posts: 3
Joined: Thu Jan 17, 2013 12:01 pm

### Re: 10131 - Is Bigger Smarter?

Thx brianfry713, I've got AC finally.
Just a newbie

hello442
New poster
Posts: 1
Joined: Wed Apr 03, 2013 1:22 pm

### Re: 10131 - Is Bigger Smarter?

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;
}

}
``````

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

### Re: 10131 - Is Bigger Smarter?

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

ljk
New poster
Posts: 2
Joined: Fri Apr 05, 2013 1:51 am

### Re: 10131 - Is Bigger Smarter?

@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``

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

### Re: 10131 - Is Bigger Smarter?

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
``````

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

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

### Re: 10131 - Is Bigger Smarter?

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

300pounddog
New poster
Posts: 4
Joined: Tue Oct 22, 2013 1:57 am

### Re: 10131 - Is Bigger Smarter?

Similar to most of your implementations, I sorted the input based in decreasing IQs. However, I can't figure out why in the event that there is a tie in IQ, the larger weight value should take precedence. My initial thoughts were that it probably didn't matter. So after I got my AC i started tinkering around with the order and hey the code got a WA.

Can someone explain? I'm confused...
Thanks.

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

### Re: 10131 - Is Bigger Smarter?

My AC code sorts to increasing weight and if there is a tie then decreasing IQ, but it depends on your implementation.
Check input and AC output for thousands of problems on uDebug!