10131 - Is Bigger Smarter?

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 10131 - Is Bigger Smarter?

Post by $u!fur » Mon Jun 16, 2008 11:37 am

#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 :oops: ...??
Why plz sumbdy help me...!!

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

Re: 10131 - Is Bigger Smarter?

Post by oscartheroot » Mon Nov 10, 2008 10:29 pm

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?

Post by DJWS » Tue Nov 11, 2008 6:38 am

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?

Post by oscartheroot » Tue Nov 11, 2008 10:14 am

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 :D
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?

Post by khjhs8062 » Sun Jun 14, 2009 6:18 am

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?

Post by helloneo » Sun Jun 14, 2009 11:21 am

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..
Check this thread out..

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?

Post by mahmutm2 » Mon Oct 12, 2009 11:31 am

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?

thx advance

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

Re: 10131 - Is Bigger Smarter?

Post by amishera » Fri May 21, 2010 2:25 am

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)

Why is the answer not
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?

Post by mohamed90 » Mon Aug 02, 2010 8:12 pm

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
:cry:

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

Re: 10131 - Is Bigger Smarter?

Post by back_tracker » Wed Jul 13, 2011 1:53 pm

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?

Post by Dunknow » Fri Jan 13, 2012 3:29 am

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

vector<int> answers;
int p [1001];
int m [1001] = {0};

void print_recurse (int i, int p_i){
    answers.push_back(elephants[i].first);
    if(p_i==-1){
        //cerr<<answers.size()<<endl;
        for(int i = 0;i<answers.size();i++){
            cout<<answers[i]<<endl;
        }
        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?

Post by brianfry713 » Thu Jan 19, 2012 1:52 am

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?

Post by rambo1980 » Mon Apr 02, 2012 6:50 pm

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

Re: 10131 - Is Bigger Smarter?

Post by brianfry713 » Mon Apr 02, 2012 9:50 pm

Add these lines to your compare function.
if(q->iq == p->iq)
return (q->weight - p->weight);
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?

Post by rambo1980 » Thu Apr 05, 2012 8:18 am

thanks brainfry, my silly mistake :S

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest