## 10131 - Is Bigger Smarter?

Moderator: Board moderators

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

### Re: 10131 - Is Bigger Smarter?

Do you think you can explain to me why return
left.weight > right.weight;
is the only way to go for my code? Thanks
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;

struct elephant{
int id;
int weight;
int iq;
};

int cnt;
vector<elephant> elephants;
vector<int> dp, startof;
struct sort_pred {
bool operator()(const elephant &left, const elephant &right) {
if(left.iq == right.iq) return left.weight > right.weight;
return left.iq > right.iq;
}
};
int maxx, LIS=0;
int main(){

elephant temp;
maxx=1;
for(cnt=0;~scanf("%d %d",&temp.weight,&temp.iq);temp.id=cnt+1,elephants.push_back(temp),cnt++);

sort(elephants.begin(), elephants.end(), sort_pred());

dp.assign(cnt, 1);
startof.assign(cnt,-1);

for(int q=1;q<cnt;q++){
for(int w=0;w<q;w++){
if(elephants[q].weight > elephants[w].weight && elephants[q].iq < elephants[w].iq ){
dp[q] = max(dp[q],dp[w]+1);
startof[q]=w;
if(LIS<dp[q]){
LIS = dp[q];
}
}
}
}
for(int q=0;q<cnt;q++){
printf("%d.\t%d\t%d\n",elephants[q].id,elephants[q].weight,elephants[q].iq);
}
int lis2=LIS;
printf("%d\n",LIS);
stack<elephant> champions;
for(int q=cnt-1;q>=0;q--){
if(LIS == dp[q]){
printf("%d.\t%d\t%d\n",elephants[q].id,elephants[q].weight,elephants[q].iq);
champions.push(elephants[q]);
LIS--;
}
}
for(int q=0;q<lis2;q++){
printf("%d\n",champions.top().id);
champions.pop();
}
return 0;
}

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

### Re: 10131 - Is Bigger Smarter?

Try input:

Code: Select all

``````1000 4000
1100 3000
2000 1900
2002 1900
2001 1899
``````
You code is correct if you remove the debug info it prints:

Code: Select all

``````4
1
2
3
5
``````
However if you change to left.weight < right.weight it incorrectly prints:

Code: Select all

``````4
1
2
4
5
``````
Check input and AC output for thousands of problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 10131 - Is Bigger Smarter?

Getting WA.

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>

using namespace std;

/*------- Constants---- */
#define MX 10399
#define ll long long
#define ull unsigned long long
#define mod 1000000007

/* -------Global Variables ------ */
ll x,y;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))

int ara[MX][2],size,ara2[MX];

struct name{
int x;
vector<int > seq;
}dp[1000];
int func(int n)
{
int ret=1,tmp;
for (int i=1; i<n; i++) {
if(ara[i][0]<ara[n][0] && ara[i][1]>ara[n][1]){
tmp=1+dp[i].x;
if(tmp>ret) {
ret=tmp;
dp[n].seq= dp[i].seq;
}
}
}
dp[n].seq.push_back(n);
return ret;
}
int main()
{
int n,i=1,track,ans,index;
while (scanf("%d %d",&ara[i][0],&ara[i][1])==2) {

ara2[i]=i;
i++;
}
size=i;
ans=-1;
for (i=1; i<size; i++) {
n=ara[i][0];
index=i;
for (int j=i+1; j<size; j++) {
if(ara[j][0]<n) {
n=ara[j][0];
index=j;
}
if(ara[j][0]==n && ara[j][1]>ara[i][1]){
n=ara[j][0];
index=j;
}
}
int a=ara[i][0],b=ara[i][1];
ara[i][0]=ara[index][0];
ara[i][1]=ara[index][1];
ara[index][0]=a;ara[index][1]=b;
a=ara2[index];
ara2[index]=i;
ara2[i]=a;
}
for (i=1; i<=size; i++) {
dp[i].x=func(i);
if(dp[i].x>ans) {ans=dp[i].x;track=i;}
}
printf("%d\n",ans);
for (i=0; i<dp[track].seq.size(); i++) {
printf("%d\n",ara2[dp[track].seq[i]]);
}
return 0;
}

``````

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10131 - Is Bigger Smarter?

Repon kumar Roy wrote:Getting WA.
(1) Where are you initializing the variable named "track"? Don't count on the compiler doing it for you.

(2) Your code fails on the test case shared by biranfry713 / tan_Yui earlier in this thread

http://acm.uva.es/board/viewtopic.php?f ... ca49d138d8
Check input and AC output for over 7,500 problems on uDebug!

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

### Re: 10131 - Is Bigger Smarter?

Got AC . Thanks After All... Just a silly mistake in sorting process,,,,

(1) Where are you initializing the variable named "track"? Don't count on the compiler doing it for you.

(2) Your code fails on the test case shared by biranfry713 / tan_Yui earlier in this thread

http://acm.uva.es/board/viewtopic.php?f ... 1&start=60

My accepted output for this program is

Code: Select all

``````17
28
46
54
83
94
33
20
56
104
66
78
1
19
5
13
3
100
``````
As the answer can be many but only one needed to be found.....

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10131 - Is Bigger Smarter?

Repon kumar Roy wrote:Got AC . Thanks After All... Just a silly mistake in sorting process,,,,
Great! Well done!
Check input and AC output for over 7,500 problems on uDebug!

mgavin2
New poster
Posts: 43
Joined: Sat Jul 28, 2012 6:29 pm

### Re: 10131 - Is Bigger Smarter?

brianfry713 wrote:Try input:

Code: Select all

``````1000 4000
1100 3000
2000 1900
2002 1900
2001 1899
``````
You code is correct if you remove the debug info it prints:

Code: Select all

``````4
1
2
3
5
``````
However if you change to left.weight < right.weight it incorrectly prints:

Code: Select all

``````4
1
2
4
5
``````
shouldn't

Code: Select all

``````4
1
2
3
4
``````

I've been getting WA from the judge, doing what the "Competitive Programming 3" book says (sort on decreasing IQ, LIS on increasing weight), and still can't figure things out with this problem. Halp

Code: Select all

``````#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <limits>

using namespace std;

//#define DEBUG  //comment this line to pull out print statements
#ifdef DEBUG
#define TAB '\t'
#define debug(a, end) cout << #a << ": " << a << end
#define dbg(end) end
#else
#define debug(a, end)
#define dbg(end)
#endif

typedef pair<int, int> point;
typedef vector<int> vi;
typedef vector<point> vp;

#define UN(v) SORT(v),v.erase(unique(v.begin(),v.end()),v.end())
#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for (int  i=(a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
#define CL(a,b) memset(a,b,sizeof(a))
#define CL2d(a,b,x,y) memset(a, b, sizeof(a[0][0])*x*y)

/*global variables*/
struct triple
{
int first;
int second;
int third;
};
typedef vector<triple> vt;
vt elephants, e2;

struct srt
{
bool operator() (const triple& a, const triple& b)
{
return a.second > b.second;
}
};

struct srt2
{
bool operator() (const triple& a, const triple& b)
{
return a.first > b.first;
}
};
/*global variables*/

void dump()
{
//dump data
REP(i, (int)elephants.size())
{
debug(elephants[i].first, TAB);
debug(elephants[i].second, TAB);
debug(elephants[i].third, endl);
}
}

bool getInput()
{
//get input

triple elephant;
int weight, iq;
int i = 1;
while (scanf("%d %d ", &weight, &iq) != EOF)
{
elephant.first = weight;
elephant.second = (iq);
elephant.third = i;
elephants.push_back(elephant);
++i;
}
return true;
}

void process()
{
//process input
e2 = elephants;
sort(elephants.begin(), elephants.end(), srt());
dbg( dump(); );

vi LIS;
LIS.push_back(1);
int j = 0, mx, dif = 1;
vi BACK;
BACK.push_back(elephants[0].third);
dbg( puts(""); );
FOR(i, 1, (int)elephants.size())
{
mx = 1;
for (j = i-1; j >= 0; --j)
{
if (elephants[j].first < elephants[i].first)
{
mx = max(LIS[j]+1, mx);
}
}
LIS.push_back(mx);
if (dif < LIS.back())
{
debug(elephants[i].first, TAB);
debug(elephants[i].second, TAB);
debug(elephants[i].third, endl);
BACK.push_back(elephants[i].third);
dif = LIS.back();
}
else if (dif == LIS.back())
{
debug(elephants[i].first, TAB);
debug(elephants[i].second, TAB);
debug(elephants[i].third, endl);
BACK.back() = elephants[i].third;
}
}

dbg (
REP(i, LIS.size())
printf("%d ", LIS[i]);
puts("");

debug(BACK.size(), endl);
REP(i, BACK.size())
{
printf("%d %d %d\n", e2[BACK[i]-1].first,
e2[BACK[i]-1].second,
BACK[i]);
}
puts("");
);

printf("%d\n", (int)BACK.size());
REP(i, BACK.size())
printf("%d\n", BACK[i]);

}

int main()
{
//    while ()
{
getInput();
process();

/*CLEAR GLOBAL VARIABLES!*/

/*CLEAR GLOBAL VARIABLES!*/
}

return 0;
}
``````
TIA..
all that matters is AC

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10131 - Is Bigger Smarter?

It is not acceptable answer. Because problem description says
W[a[1]] < W[a[2]] < ... < W[a[n]]
and
S[a[1]] > S[a[2]] > ... > S[a[n]]

In order for the answer to be correct, n should be as large as possible. All inequalities are strict: weights must be strictly increasing, and IQs must be strictly decreasing
3rd and 4th elephant have equal IQ = 1900. 3rd elephant's IQ should be smaller than 4th elephant's IQ.
tan_Yui wrote:I got WA several times.
My algorithm is almost same as 'Methods to solve'.

I want output for following set of input, or some other I/O.
Could anyone help me ?
Of cource, I know that there may be many correct outputs for a given input, our program only needs to find one.

Case 1 :

Code: Select all

``````6202 3231
3155 6784
5813 5706
8530 8021
3805 1907
9376 2724
6137 1932
7432 6366
8562 5375
1075 2842
3148 9839
9020 358
632 5996
7196 4332
7058 8872
``````
Thank you.
brianfry713 wrote: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
``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

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

### Re: 10131 - Is Bigger Smarter?

For sample input:

Code: Select all

``````6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900``````
Given output:

Code: Select all

``````4
4
5
9
7``````
My question: "Is the bellow output for the above input also accepted?

Code: Select all

``````4
4
5
9
1``````
And I also want to know when more than one solution is possible, is any of them acceptable? And is there any case in judge's input like this?
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
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: 10131 - Is Bigger Smarter?

There may be many correct outputs for a given input, your program only needs to find one.
And I also want to know when more than one solution is possible, is any of them acceptable?
Yes.
My question: "Is the bellow output for the above input also accepted?
Yes.
And is there any case in judge's input like this?
Probably.

See:
http://uva.onlinejudge.org/index.php?op ... ategory=13
The yellow check means this problem has a special judge. Special judge problems use a program that reads in the judge's input, output, and the user's output and determines if the user's output is AC or not. Standard green check problems just check if the user's output matches the judge's output exactly.
On this problem the special judge checks if the sequence is as large as possible and that the given sequence has weights that are strictly increasing and IQs that are strictly decreasing.
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

### Re: 10131 - Is Bigger Smarter?

Give me some tricky input and output. I am getting WA with my code.
My code:

Code: Select all

``````#include <stdio.h>
#define maxi 1010
int visited[maxi][maxi], precal[maxi][maxi], n, num1[maxi], num2[maxi], match[maxi], m=0;
int lcslen(int i, int j)
{
if(i>n || j>n)
return 0;
if(visited[i][j]==1)
return precal[i][j];

int ans;
if(num1[i]==num2[j] && num1[i]>0)
ans=1+lcslen(i+1, j+1);
else
{
int v1=lcslen(i, j+1);
int v2=lcslen(i+1, j);
if(v1>v2)
ans=v1;
else ans=v2;
}
visited[i][j]=1;
precal[i][j]=ans;
return precal[i][j];
}
void printLCS(int i,int j)
{
if(i>n || j>n){
for(int i=0;i<m;i++)
printf("%d\n",match[i]);
return;
}
if(num1[i]==num2[j] && num1[i]>0){
match[m++]=num1[i];
printLCS(i+1,j+1);
}
else
{
if(precal[i+1][j]>precal[i][j+1])
printLCS(i+1,j);
else
printLCS(i,j+1);
}
}
int compare(const void *a, const void *b)
{
return (*(int*)b - *(int*)a);
}
int main()
{
int i, j, k, w[maxi], iq[maxi], s=1, tmp;
while(scanf("%d %d", &w[s], &iq[s])!=EOF)
{
s++;
}
for(i=1;i<s;i++)
{
num1[i]=i;
num2[i]=i;
}
for(i=1;i<s;i++)
{
for(j=1;j<s-1;j++)
{
if(w[j]>w[j+1])
{
tmp=w[j];
w[j]=w[j+1];
w[j+1]=tmp;

tmp=num1[j];
num1[j]=num1[j+1];
num1[j+1]=tmp;
}
else if(w[j]==w[j+1])
num1[j+1]=0;
if(iq[j]<iq[j+1])
{
tmp=iq[j];
iq[j]=iq[j+1];
iq[j+1]=tmp;

tmp=num2[j];
num2[j]=num2[j+1];
num2[j+1]=tmp;
}
else if(iq[j]==iq[j+1])
num2[j+1]=0;
}
}
n=s-1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
visited[i][j]=0;
printf("%d\n",lcslen(1, 1));
printLCS(1, 1);
return 0;
}
``````
Md. Shahidul Islam
Dept. of CSE at Begum Rokeya University, Rangpur, Bangladesh
UVa id: http://uhunt.felix-halim.net/id/438420
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: 10131 - Is Bigger Smarter?

Input:

Code: Select all

``````6296 5280
9500 3603
5611 7692
8070 4728
7927 8073
8573 3954
7041 5549
333 1306
9527 7138
1717 472
7116 7846
5924 7658
7372 9510
1549 4314
5215 1716
6995 1748
5351 1510
9202 2846
3925 961
5386 3623
3928 1851
3751 3958
1615 7320
4457 436
907 1142
5339 6173
182 4375
3884 1262
1927 3906
5621 5433
3532 7141
5003 8968
8165 8882
6195 556
4178 2090
292 1580
1889 8105
5424 4043
830 3504
997 9880
2404 8088
2462 6335
7596 2586
6491 2698
4482 5875
3015 8463
3782 8013
6895 8017
4924 1947
4036 9441
1020 9101
7205 4327
4721 9260
9115 8980
5211 5550
3638 111
2797 7615
6552 2451
5148 6745
2619 9394
4208 9629
7642 1985
2 7990
9936 888
328 1277
378 323
4649 7699
3310 3934
2914 9370
1271 2425
8887 8124
2090 1260
3711 1684
8428 4993
4386 8858
4839 7398
9382 4946
2935 2480
9719 5735
7012 9222
9544 46
4096 7389
1322 4192
9913 7405
9829 587
8711 7536
5147 8716
6751 7152
2145 8857
4067 1530
8927 2882
7827 8905
7736 8308
4043 761
6334 7454
3851 1054
4794 5877
6421 7946
1702 2467
3054 2685
220 7883
2950 8116
5267 5367
575 9700
1229 7411
6645 4641
9897 6507
4814 4471
1584 3984
1437 8856
6261 7917
146 1639
9584 1054
3521 6566
5602 7638
5520 2926
1041 2174
3892 4821
4520 2659
6422 4466
5459 2100
8606 3066
7536 1707
5691 9771
8627 9119
3388 7127
8766 1239
8645 3533
6450 4701
8690 8517
1442 2051
4224 4209
9029 8834
7844 8115
2581 9900
8351 4265
7330 4391
6097 3308
3079 1218
6688 1787
5266 8057
9295 6427
9959 383
1435 7939
2807 6408
4811 125
685 4248
9433 9034
7149 6066
2317 7277
7893 6081
471 668
3975 5223
2792 2919
1058 3405
1461 5831
2258 6323
3057 756
5046 8568
4976 843
7319 7853
8452 6138
5171 8004
421 7885
1513 8671
4751 9089
9756 9405
979 1573
4492 83
9839 3770
5953 5549
8223 1300
2055 8210
6777 7631
4825 3452
1304 8104
4241 2144
6499 9756
3992 5764
4434 6919
6007 5504
4908 9185
757 2115
8549 5887
9656 1600
3500 8387
9686 5608
169 8074
2056 8092
1544 3298
1401 6881
9024 2847
8954 1994
7757 5522
8792 2945
8448 2190
7726 4798
3264 9708
5594 4835
6434 1812
6551 1601
3561 6286
711 6236
680 3729
3378 2767
9647 2223
1421 4779
3124 5022
6895 6727
6023 7232
9421 5686
483 823
530 7147
1981 99
8262 6123
7723 4766
7403 4812
7400 7635
1364 8114
7232 8079
6653 4741
5871 3230
8251 4425
7503 5346
2577 5145
830 3526
4348 8350
5496 7664
4114 4877
7351 3828
4945 2376
7187 1425
9060 8700
6813 4586
9016 6775
7867 4044
3625 2020
2797 90
5435 1875
3371 299
3824 8012
6361 552
8215 4523
5751 8208
8387 8681
1056 3101
4526 9683
8382 8242
9180 9937
6711 1546
1941 4547
6567 4577
4666 5565
7439 9363
6013 101
4464 7161
7712 9837
711 7176
1735 2279
959 6462
9562 121
6155 2014
6607 439
375 4537
6082 5786
6685 7085
8014 8023
3587 3251
8965 2679
9131 7378
4538 4977
1165 9946
7121 8602
880 8228
4689 8855
5327 1838
203 602
1041 1482
6018 6809
8947 7767
1204 8451
2825 5631
5233 9217
8247 2764
141 4197
5525 7378
7323 1030
9631 3042
1269 796
9650 6862
8699 2309
2910 4977
2810 5253
2062 302
8069 8827
3629 1008
6638 9272
4840 6454
9217 8222
``````
AC output:

Code: Select all

``````33
104
51
281
219
37
189
41
57
126
114
202
179
253
55
171
181
1
129
106
234
243
223
136
6
122
195
91
192
18
206
185
85
143
``````
Check input and AC output for thousands of problems on uDebug!

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Why WA?

I am getting WA for the following code. Plz tell me the mistake.

Code: Select all

``````#include<algorithm>
#include<cstdio>
using namespace std;
int w[2000],p[2000],m[2000],m_id[2000],in[2000],index[2000];
void print(int end)
{
if(end<0)
return;

printf("%d\n",index[end]);
print(p[end]);
}
int main()
{
int i=0,pos,l,l_end,j,t;
while(scanf("%d%d",&w[i],&in[i])!=EOF)
{
index[i]=i+1;
for(j=0;j<i;j++)
{
if(w[j]<w[i])
{
t=w[j];
w[j]=w[i];
w[i]=t;
t=in[j];
in[j]=in[i];
in[i]=t;
t=index[j];
index[j]=index[i];
index[i]=t;
}
}
i++;
}
// for(j=0;j<i;j++)
// printf("%d  %d  %d\n",index[j],w[j],in[j]);
// printf("ensd");
j=0;
l=l_end=0;
while(j<i)
{
if(w[j]==w[j-1])
{
j++;
continue;
}
pos=lower_bound(m,m+l,in[j])-m;
m[pos]=in[j];
m_id[pos]=j;
p[j]=pos>0?m_id[pos-1]:-1;
//printf("%d %d %d %d %d  %d  %d\n",pos,m[pos],m_id[pos],j,p[j],l,l_end);
if(pos==l)
{
l++;
l_end=j;
}
j++;
}
printf("%d\n",l);
// scanf("%d",&l);
print(l_end);
return 0;
}
``````

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 10131 - Is Bigger Smarter?

It is written that :
There may be many correct outputs for a given input, your program only needs to find one.
So, its not necessary to get the same output as that given in the judge's sample output

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 10131 - Is Bigger Smarter?

I am getting the following output ... not the one you said
4
4
5
9
1
which matches the following:
1000
1100
2000
6008