## 10131 - Is Bigger Smarter?

Moderator: Board moderators

\$u!fur
New poster
Posts: 2
Joined: Thu Jun 12, 2008 10:30 am

### Re: 10131 - Is Bigger Smarter?

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <list>
#include <cmath>
#include <sstream>
#include <cstdlib>
#include <cstring>

#define re return
#define SZ size()
#define L length()
#define vi vector<int>
#define vs vector<string>
#define REP(i,n) for(int i=0;i<n;i++)
#define KEP(i,a,b) for(int i=a;i<=b;i++)
#define MEP(i,a,b) for(int i=a;i>=b;i--)
#define Sort(a) sort(a.begin(),a.end())
#define MAX 1001
using namespace std;
vi w,s;
vi fin,fout;
vi orgw,orgs;

vi b(MAX);

void printlis(int max,int pos)
{
if(max<0) return;
int x=fout[pos]; int y=fin[pos];
int display;
REP(i,fout.SZ)
if(x==orgw&&y==orgs)
{
display=i;
break;
}
for(int i=pos;i>=0;i--)
if(b==max-1)
{
printlis(--max,i);
break;
}
cout<<display+1<<endl;
}

int main()
{

int x,y;
while(cin>>x)
{
cin>>y;
w.push_back(x);
s.push_back(y);
}

orgw=w;
orgs=s;
fin=s;
sort(fin.begin(),fin.end());
reverse(fin.begin(),fin.end());
REP(i,fin.SZ)
{
for(int j=0;j<s.SZ;j++)
{
if(fin==s[j])
{
fout.push_back(w[j]);
w.erase(w.begin()+j);
s.erase(s.begin()+j);
break;
}
}
}

int len=fout.SZ;

int max=0,pos=0;
for(int i=0;i<len;i++) b=1;
for(int i=1;i<len;i++)
for(int j=0;j<len;j++)
{
if(fout>fout[j]&&fin<fin[j]&&b<b[j]+1)
b=b[j]+1;
if(max<b)
{
pos=i;
max=b[i];
}
}
cout<<max<<endl;
printlis(max,pos);

return 0;
}

Attempted the question for a long time....but got WA ...??
Why plz sumbdy help me...!!

oscartheroot
New poster
Posts: 5
Joined: Sat Oct 11, 2008 1:03 pm

### Re: 10131 - Is Bigger Smarter?

I also get wrong answer, and have no idea of where's the error...

Code: Select all

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int troba (vector <long long> res, long long n){
for (int i=0; i<res.size(); i++) if (res[i]==n) return i;
return -44;
}

int main(){
vector <pair <long long, long long> > nums;
pair <long long, long long> aux;
vector <long long> res;
while (cin>>aux.first>>aux.second){
nums.push_back (aux);
res.push_back (aux.second);
}
sort (nums.begin(), nums.end());
vector <long long> v (nums.size(), 0);
vector <vector <long long> > seq (nums.size());
long long respos=0, resmax=0;
for (int i=0; i<nums.size(); i++){
long long pos=i, maxi=0;
for (int j=0; j<i; j++){
if (nums[j].second>nums[i].second and nums[j].first<nums[i].first) if (v[j]>maxi){maxi=v[j]; pos=j;}
}
seq[i]=seq[pos];
seq[i].push_back (i);
v[i]=max(maxi, v[i]);
v[i]++;
if (v[i]>resmax) {respos=i; resmax=v[i];}
}
cout<<resmax<<endl;
for (int i=0; i<seq[respos].size(); i++){
long long a=troba (res, nums[seq[respos][i]].second);
cout<<a+1<<":= "<<nums[seq[respos][i]].first<<" "<<nums[seq[respos][i]].second<<endl;
}
system ("pause");
}

``````
I first sort the first elements of the vector <pair <long long> > increasingly, so after I only have to search for the longest decreasing sequence.

But It seems it doesn't work

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

### Re: 10131 - Is Bigger Smarter?

To oscartheroot,
1. Add return 0; at the bottom of main function.
2. Remove system("pause");
3. Your program outputs extra things.
4. You can simply use int type instread of long long type.
5. The problem says there are no more than 1000 elephants. You can simply use a 1000-unit-array instead of a vector.
6. To find a LIS, you should backtrace from the end of the DP array. It's not correct to trace from the front of the DP array.
7. You can increase one more array. Use it to record the best route of the LISs during processing DP. That makes backtracing easier.

oscartheroot
New poster
Posts: 5
Joined: Sat Oct 11, 2008 1:03 pm

### Re: 10131 - Is Bigger Smarter?

1. my program has no difficulty to end, I mean, it's not necessary to put the return 0; is it? Well, I'll put it.
2. I obviously take away system ("pause"); before sending it to the judge
3. Where does it output extra things? I don't see it....
6. But it should find a valid solution anyway, isn't it? It's only that thinks of a different solution, but in the problem it is said:
There may be many correct outputs for a given input, your program only needs to find one.
so after all, my program finds a valid solution, maybe not the better one, but a valid one.

Thanks, I will correct the other things and see what happens.

khjhs8062
New poster
Posts: 1
Joined: Sun Jun 14, 2009 6:14 am
Location: Taiwan

### Re: 10131 - Is Bigger Smarter?

Can anyone see my code?
My program gets PE(yeah, not WA) so many times.
I don't know why...

Code: Select all

``````delete after helloneo's Reply
thx helloneo!
``````
Last edited by khjhs8062 on Sun Jun 14, 2009 3:58 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 10131 - Is Bigger Smarter?

khjhs8062 wrote:Can anyone see my code?
My program gets PE(yeah, not WA) so many times.
I don't know why...
Maybe there is an issue on the special corrector problem..

http://acm.uva.es/board/viewtopic.php?&t=42722

mahmutm2
New poster
Posts: 1
Joined: Mon Oct 12, 2009 10:37 am

### Re: 10131 - Is Bigger Smarter?

i send my code because
''your program only needs to find one" but i got WA.
Here is my code:

Code: Select all

``````#include<iostream>
#include<cstdlib>
using namespace std;
int n;
struct par{
int first;
int second;
int eskiyer;
};
par dizi[100000];
int cmp(const void* a, const void *b){return ((*( par * )a).first - (*( par *)b).first);}
int best[100001],parent[100001];
int main()
{
int end=0;
while(1)
{
if(cin.eof()){end--;break;}
cin>>dizi[end].first>>dizi[end].second;
dizi[end].eskiyer=end;
end++;
}
for(int i=0;i<end;i++){best[i]=1;parent[i]=i;}
qsort(dizi,end,sizeof(par),cmp);
/*
for(int i=0;i<end;i++)
cout<<dizi[i].first<<' '<<dizi[i].second<<endl;
*/
for(int i=1;i<end;i++)
for(int j=0;j<i;j++)
if(dizi[i].first>dizi[j].first&&

dizi[i].second<dizi[j].second&&

best[i]<best[j]+1){

best[i]=best[j]+1;
parent[i]=j;

}
int max=0;
int old=0,ydk=0;
for(int i=0;i<end;i++)if(max<best[i]){max=best[i];ydk=i;}
cout<<max<<endl;
while(ydk!=old)
{
old=ydk;
cout<<dizi[ydk].eskiyer+1<<endl;
ydk=parent[ydk];
}
return 0;
}
``````
can anyone help me?

amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

### Re: 10131 - Is Bigger Smarter?

I have this question:

500(3) 1000(4) 1100(5) 2000(9) 6000(2) 6000(6) 6000(8) 6008(1) 8000(7)
4000(4) 3000(5) 2100(2) 2000(3) 2000(6) 1900(9) 1400(7) 1300(1) 1200(8)

4 5 2 6 7?

1000(4) 1100(5) 6000(2) 6000(6) 8000(7)
4000(4) 3000(5) 2100(2) 2000(6) 1400(7)

If the answer can be out of the input order like

4 5 9 7 (here 9 comes before 7)

Then why can't 2 come before 6 and 7 to make it a 5 length sequence?

mohamed90
New poster
Posts: 2
Joined: Mon Aug 02, 2010 7:59 pm

### Re: 10131 - Is Bigger Smarter?

please help i get alot of WA and i don't know if what i do is right or not because there are many answers are right

i take the input and put in the first -100000 and 100000 and sort it
then do lis check if( second[prev] > second[cur])
and print the path

back_tracker
New poster
Posts: 9
Joined: Sun Jun 19, 2011 12:03 am

### Re: 10131 - Is Bigger Smarter?

Hi,

This is an automated response from UVa Online Judge.

Your submission with number 9045104 for the problem 10131 - Is Bigger Smarter? has succeeded with verdict Accepted.

Congratulations! Now it is time to try a new problem.

Best regards,

The UVa Online Judge team

"Every thing should be done simple" =D

Dunknow
New poster
Posts: 1
Joined: Fri Jan 13, 2012 3:26 am

### Re: 10131 - Is Bigger Smarter?

Code: Select all

``````/* @BEGIN_OF_SOURCE_CODE */
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <ctime>
#include <iterator>

using namespace std;

vector<pair<int,pair<int,int> > > elephants;

bool check (const pair<int,pair<int,int> > & left, const pair<int,pair<int,int> >& right) { //mem function
return (left.second.first<right.second.first)&&(left.second.second>right.second.second);
}

bool sort_pred (const pair<int,pair<int,int> > & left, const pair<int,pair<int,int> > & right){
if (left.second.first==right.second.first){
return left.second.second<right.second.second; //Switch inequality value?
}
return left.second.first>right.second.first;
}

int p [1001];
int m [1001] = {0};

void print_recurse (int i, int p_i){
if(p_i==-1){
}
return;
}
//cerr<<elephants[i].first<<" <<"<<endl;

print_recurse(p_i,p[p_i]);

}

int main (){
//freopen("isbiggersmarter.txt", "r", stdin);
int w, iq;
int c = 1;
string garbage;
while (getline(cin,garbage)){
stringstream ss;
ss<<garbage;
ss>>w>>iq;
elephants.push_back(make_pair(c,make_pair(w,iq)));
c++;
}

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

//int m [1000] = {0};  //made into global
//parent array made into global variable
for (int k = 0;k<1001;k++){
p[k] = -1;
//cerr<<m[k]<<endl;
}
//REMEMBER TO START PARENT LABEL AT 1 !!!!
for (int i = 0;i<elephants.size();i++){

int pick  = 0;
for (int j =0;j<elephants.size();j++){
if(m[j]>m[i]+pick&&check(elephants[i],elephants[j])){
pick=m[j];
p[i] = j; //CHANGE IF NECESSARY
}
}
m[i]+=pick+1;
}

int greatest_index = 0;
for (int i = 0;i<elephants.size();i++){
if(m[i]>m[greatest_index]) greatest_index = i;

}

cerr<<m[greatest_index]<<endl;
print_recurse(greatest_index, p[greatest_index]);

return 0;
}

/* @END_OF_SOURCE_CODE */
``````

I've got WA several times, yet I followed all the recommendations in this thread + I tried input with getline() and cin>> but neither one seems to be getting me AC. My algo is perfect to me, but I still can't get it to work.

Any help would be appreciated!

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

rambo1980
New poster
Posts: 15
Joined: Sun Mar 18, 2012 2:45 pm

### Re: 10131 - Is Bigger Smarter?

Can anybody tell me what i am doing wrong here? I'm getting WA for this problem.
Here's what i did-
1. Create a structure which holds the weight, iq and serial no. of the elephants
2. Sort the structure array in descending order in the basis of their iq
3. Now create the sequence of LIS
4. print the stored serials of the elephants in order

I've tested it with several testcases, seems to work file. Where is it going wrong actually?

Code: Select all

``AC``
Last edited by rambo1980 on Thu Apr 05, 2012 8:19 am, edited 1 time in total.

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