12124 - Assemble

[Farsan]

I tried basic recursion but got TLE.Is this a DP problem? But budget is very high (1000000000) so i how could i possibly apply dp? Thanks . Here is my code

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include<iomanip>
#define inf 10000000
#define Max(v) *max_element(v.begin(),v.end())
#define Min(v) *min_element(v.begin(),v.end())
#define inp1(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d %d",&x,&y)
#define Unique(v) v.resize(unique(v.begin(),v.end())-v.begin())
#define Sort(v) sort(v.begin(),v.end(),greater<int>());
#define fread() freopen("inp.txt","r",stdin)
#define fwrite() freopen("out.txt","w",stdout)
#define mem(n,m) memset(n,m,sizeof n)
//priority_queue< int, vector<int>, greater<int> > PQ;// keeps in ascending order
// bool operator < ( const node& b ) const

using namespace std;

vector<long>quality[1010],price[1010];
long mx;

int solve(int i,int n,long budget,long q)
{
    if(i>n)
    {
        if(q>mx)
        mx=q;
        return 0;
    }
    int j,k;
    for(j=0,k=price[i].size();j<k;j++)
    {
        if(budget-price[i][j]>=0)
        {
            if(quality[i][j]<q)
            solve(i+1,n,budget-price[i][j],quality[i][j]);
            else
            solve(i+1,n,budget-price[i][j],q);
        }
    }
    return 0;

}

int main()
{
    int i,j,k,m,n,p,t;
    long b,q;
    inp1(t);
    while(t--)
    {
       scanf("%d %ld",&n,&b);
       for(i=1;i<=n;i++)
       {
         quality[i].clear();
         price[i].clear();
       }
       string s1,s2;
       map<string,int>mp;
       k=0;
       while(n--)
       {
          cin>>s1>>s2;
          if(!mp[s1])
          mp[s1]=++k;
          m=mp[s1];
          inp1(p);
          cin>>q;
          price[m].push_back(p);
          quality[m].push_back(q);
        }
        mx=0;
        solve(1,k,b,1000050000);
        cout<<mx<<endl;
    }
    return 0;
}

[brianfry713]

Start off buying the cheapest component of each type. Keep upgrading the lowest quality component while you can without exceeding the budget.

[Farsan]

Start off buying the cheapest component of each type. Keep upgrading the lowest quality component while you can without exceeding the budget.

I tried by sorting the components with respect to price and then maximized quality .Still TLE, here is my updated code

Code: Select all

#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<limits>
#include<iomanip>
#define inf 10000000
#define Max(v) *max_element(v.begin(),v.end())
#define Min(v) *min_element(v.begin(),v.end())
#define inp1(x) scanf("%d",&x)
#define inp2(x,y) scanf("%d %d",&x,&y)
#define Unique(v) v.resize(unique(v.begin(),v.end())-v.begin())
#define Sort(v) sort(v.begin(),v.end(),greater<int>());
#define fread() freopen("inp.txt","r",stdin)
#define fwrite() freopen("out.txt","w",stdout)
#define mem(n,m) memset(n,m,sizeof n)
//priority_queue< int, vector<int>, greater<int> > PQ;// keeps in ascending order
// bool operator < ( const node& b ) const

using namespace std;

vector<pair<int,long> >v[1010];
long mx;

int solve(int i,int n,long budget,long q)
{
    if(i>n)
    {
        if(q>mx)
        mx=q;
        return 0;
    }
    int j,k;
    for(j=0,k=v[i].size();j<k;j++)
    {
        if(budget-v[i][j].first>=0)
        {
            if(v[i][j].second<q)
            solve(i+1,n,budget-v[i][j].first,v[i][j].second);
            else
            solve(i+1,n,budget-v[i][j].first,q);
        }
        else
        break;
    }
    return 0;
}

int main()
{
    int i,j,k,m,n,p,t;
    long b,q;
    inp1(t);
    while(t--)
    {
       scanf("%d %ld",&n,&b);
       for(i=1;i<=n;i++)
       {
            v[i].clear();
       }
       string s1,s2;
       map<string,int>mp;
       k=0;
       while(n--)
       {
          cin>>s1>>s2;
          if(!mp[s1])
          mp[s1]=++k;
          m=mp[s1];
          inp1(p);
          cin>>q;
          v[m].push_back(make_pair(p,q));
        }
        for(i=1;i<=n;i++)
        sort(v[i].begin(),v[i].end());
        mx=0;
        solve(1,k,b,1000050000);
        cout<<mx<<endl;
    }
    return 0;
}

[brianfry713]

Don't use recursion.

Code: Select all

Buy the cheapest component of each type.
while(true) {
  Try to upgrade the lowest quality component, if you can't do that without exceeding the budget, break the while loop.
}

[cutenemo]

Can anyone provide more edge cases or describe some?

I created these and got them right, I think

Code: Select all

Input
4
5 100
a x 10 6
b z 20 5
c z 30 11
a y 30 4
a r 10 3
3 100
a x 10 6
b z 20 5
c z 30 11
5 100
a x 5 4
a y 55 3
a z 35 6
a s 67 5
a r 99 7
5 100
a x 100 3
a y 50 6
b y 50 4
b z 100 5
b r 40 9
Sample Output
5
5
7
6

[brianfry713]

Your I/O is correct. You can post or PM me your code if you want.