Shuaib's blog

By Shuaib, 13 years ago, In English

Can someone please spot a problem with my solution to this UVa problem Is Bigger Smarter.

All the tests I've performed gives me correct result but I keep on getting WA on the judge.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <stack>
 
using namespace std;
bool cmp(pair<pair<int, int>, int> p1, pair<pair<int, int>, int> p2)
{
    if(p1.first.first<p2.first.first)
        return true;
    return false;
}
int main()
{
    int w, iq;
    vector<pair<pair<int, int>, int> > v; // to hold ((weight, iq), index_in_input)
    int i=1;
    while(cin>>w>>iq)
    {
        v.push_back(make_pair(make_pair(w, iq), i));
        i++;
    }
    sort(v.begin(), v.end(), cmp); //sort by weight
    vector<int> dp(v.size(), 1);
    vector<int> s(v.size());
    for(int i=0;i<s.size();i++)
        s[i] = i;
    int max = 1;
    int maxi=0;
    int lmaxi = 0;
    /*
     * In the following loop, find the longest decreasing subsequence on IQ,
     * such that for each successive member, weight is more then the previous
     * one. Also storing index of maximum length found thus far, and the choice
     * made to get till there.
     */
    for(int i=0;i<v.size();i++)
    {
        for(int j=0;j<i;j++)
        {
            if(v[i].first.first>v[j].first.first && v[i].first.second<v[j].first.second)
            {
                dp[i] = dp[j]+1;
                s[i] = j;
                if(dp[i]>max)
                {
                    max = dp[i];
                    maxi = i;
                }
            }
        }
    }
    cout<<max<<endl;
    stack<int> st;
    /*
     * Push choices made to get to the largest subsquence in a stack. And print
     * them in reverse.
     */
    for(int i=0;i<max;i++)
    {
       st.push(v[maxi].second);
       maxi = s[maxi];
    }
    for(int i=0;i<max;i++)
    {
        cout<<st.top()<<endl;
        st.pop();
    }
    return 0;
}
Tags dp, uva
  • Vote: I like it
  • -10
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
C'mon guys, what is so negative about this post? The down votes has made it disappear from activity list. If you couldn't respond with helpful comments, at least could have refrained from down voting it to sink so someone else could have a look.
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Found the issue:
if(v[i].first.first>v[j].first.first && v[i].first.second<v[j].first.second)
becomes:
if(v[i].first.first>v[j].first.first && v[i].first.second<v[j].first.second && dp[i]<=dp[j])