MAXPOINT - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

Setter: Lavish Gupta
Tester: Manan Grover
Editorialist: Ajit Sharma Kasturi

DIFFICULTY:

SIMPLE

PREREQUISITES:

None

PROBLEM:

There are three categories say C_1, C_2 and C_3. There will be 20 problems from each category appearing in a test. Problems in C_1 takes A minutes to complete and solving the problem gives X points. Problems in C_2 takes B minutes to complete and solving the problem gives Y points. Problems in C_3 takes C minutes to complete and solving the problem gives Z points. The total time of the test is 240 minutes. We need to find the maximum points we can achieve in the test by solving some problems.

QUICK EXPLANATION:

  • Since the number of problems for each category is quite small we can solve the problem by directly iterating over the number of problems taken from each category.

EXPLANATION:

The key observation in this problem is the constraints mentioned in the problem statement. Since the number of problems in each category is quite small, the simplest way to solve this problem is by using brute-force.

Let the number of problems taken from C_1, C_2 , C_3 be T_1, T_2 and T_3 respectively. Now the set of chosen problems will be valid if total time required to solve these problems is \leq 240 i.e, T_1 \cdot A+T_2 \cdot B+T_3 \cdot C \lt 240 . The total number of points we can get is T_1 \cdot X+T_2 \cdot Y+T_3 \cdot Z.

Now brute-forcing over all possible values of C_1, C_2 and C_3 from the range [0, 20] gives the time complexity for each test case as O( 21 \cdot 21 \cdot 21 ) which will easily fit in the time limit.

TIME COMPLEXITY:

O(21^3) for each testcase.

SOLUTION:

Editorialist's solution
#include <bits/stdc++.h>
using namespace std;

int main()
{
     int tests;
     cin >> tests;

     while (tests--)
     {
          int A, B, C, X, Y, Z;
          cin >> A >> B >> C >> X >> Y >> Z;

          int ans = 0;

          for (int take_a = 0; take_a <= 20; take_a++)
          {
               for (int take_b = 0; take_b <= 20; take_b++)
               {
                    for (int take_c = 0; take_c <= 20; take_c++)
                    {
                         int time = take_a * A + take_b * B + take_c * C;
                         if (time <= 240)
                         {
                              ans = max(ans, take_a * X + take_b * Y + take_c * Z);
                         }
                    }
               }
          }

          cout << ans << endl;
     }

     return 0;
}
Setter's solution

#define ll long long
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mp make_pair
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
//#include<bits/stdc++.h>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<utility>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
ll pi = acos(-1) ;
ll z =  1000000007 ;
ll inf = 100000000000000000 ;
ll p1 = 37 ;
ll p2 = 53 ;
ll mod1 =  202976689 ;
ll mod2 =  203034253 ;
ll fact[100] ;
ll gdp(ll a , ll b){return (a - (a%b)) ;}
ll ld(ll a , ll b){if(a < 0) return -1*gdp(abs(a) , b) ; if(a%b == 0) return a ; return (a + (b - a%b)) ;} // least number >=a divisible by b
ll gd(ll a , ll b){if(a < 0) return(-1 * ld(abs(a) , b)) ;    return (a - (a%b)) ;} // greatest number <= a divisible by b
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
ll e_gcd(ll a , ll b , ll &x , ll &y){ if(b > a) return e_gcd(b , a , y , x) ; if(b == 0){x = 1 ; y = 0 ; return a ;}
ll x1 , y1 ; e_gcd(b , a%b , x1 , y1) ; x = y1 ; y = (x1 - ((a/b) * y1)) ; return e_gcd(b , a%b , x1 , y1) ;}
ll power(ll a ,ll b , ll p){if(b == 0) return 1 ; ll c = power(a , b/2 , p) ; if(b%2 == 0) return ((c*c)%p) ; else return ((((c*c)%p)*a)%p) ;}
ll inverse(ll a ,ll n){return power(a , n-2 , n) ;}
ll max(ll a , ll b){if(a > b) return a ; return b ;}
ll min(ll a , ll b){if(a < b) return a ; return b ;}
ll left(ll i){return ((2*i)+1) ;}
ll right(ll i){return ((2*i) + 2) ;}
ll ncr(ll n , ll r){if(n < r) return 0 ; return ((((fact[n] * inverse(fact[r] , z)) % z) * inverse(fact[n-r] , z)) % z);}
void swap(ll&a , ll&b){ll c = a ; a = b ; b = c ; return ;}
//ios_base::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
using namespace std ;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
//__builtin_popcount(n) -> returns number of set bits in n
#define pll pair<ll ,ll> 
#define tll tuple<ll ,ll ,ll>


void solve()
{
    ll max_t = 240 , max_q = 21 ;
    ll a , b , c , x , y , z ;
    cin >> a >> b >> c >> x >> y >> z ;

    ll score = 0 ;

    fo(i , max_q)
    {
        fo(j , max_q)
        {
            fo(k , max_q)
            {
                ll tot_t = (i*a) + (j*b) + (k*c) ;
                ll tot_s = (i*x) + (j*y) + (k*z) ;

                if(tot_t <= max_t)
                {
                    score = max(score , tot_s) ;
                }
            }
        }
    }
    cout << score << endl ;
    return ;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif
    
    ll t ;
    cin >> t ;
    //t = 1 ;
   
    for(ll x = 1 ; x <= t ; x++)
    {
        solve() ;
        //cout << "Case #" << x << ": " << solve() << '\n';
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
 
    return 0;

    
}

Tester's solution
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t;
  cin>>t;
  while(t--){
    int a, b, c;
    cin>>a>>b>>c;
    int x, y, z;
    cin>>x>>y>>z;
    int ans = 0;
    for(int i = 0; i < 21; i++){
      for(int j = 0; j < 21; j++){
        for(int k = 0; k < 21; k++){
          if(i * a + j * b + k * c <= 240){
            ans = max(ans, i * x + j * y + k * z);
          }
        }
      }
    }
    cout<<ans<<"\n";
  }
  return 0;
}


Please comment below if you have any questions, alternate solutions, or suggestions. :slight_smile:

5 Likes

I made a code in C for the same. It works perfectly as far as I know, but it failed some testcases. I would be grateful if you could point out why [CodeChef: Practical coding for everyone]

As we’re given 3 sets of problems and time required to solve them respectively. All 20 problems of any particular set, will take same amount of time. So, why we’re iterating through each problem in the loop as their time need is same??? Please someone explain.

1 Like

We have to maximize our points and this can happen if we optimally choose how many questions of type A, how many of type B, and how many of type C we have to solve in order to achieve the maximum. As points awarded for solving each one type of question might be same might be different from another type. So we have to iterate all possibilities and this can be done using 3 for loops

2 Likes

Got it now, thanks man!

1 Like

Check For the Input:-

1
1 1 1
5 6 7

Welcome … :heart:

oh thank you, I reckon that if the total time required to to solve all problems is below 240 minutes then my code fails

1 Like

Can someone explain me why we use O(21^3)? What does 21 mean right there? How to approach this problem and what’s the intuition behind this?

Can someone tell me what would have been the approach if the constraints were pretty high ?? Just out of curiosity…

2 Likes

I did this problem using dp, if we observe it carefully it is 0/1
knapsack .
TC : 20 * 240.

Here’s my Overkill DP knapsack solution https://www.codechef.com/viewsolution/51460563

3 Likes

You see there are 21 possible no of questions that can be solved in each section i.e. A,B and C including 0 . So 0-20 questions can be done for each section so 21 * 21* 21 are the no of possibilities we will have to check.This is pure hit and trial method.

1 Like

Can anyone pls share the optimized approach to this question.

hey, actually I calculated the scores for all combinations. which is by considering all appearance questions were solved first, calculating the score and remaining time and then considering Flavor and calculating the score and remaining time and then for Texture.
In this way, I have calculated for all combinations and considering the max score of all combinations as output for each test case.
my output is accurate for sample input and output but my answer is rejected can someone help me solve it.

can anyone help me with my code(C++), it successfully passed the sample inputs, yet it’s giving WA, i can’t find an error, plz help. here’s the link to my solution:

https://www.codechef.com/viewsolution/51448337

can anyone help me with my c++ code,i passed sample inputs but getting WA,
help me in finding error plz,here’s link to solution:

#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define pb push_back
typedef pair<ld,ld> pairs;
#define f first
#define s second
int main() {
	// your code goes here
	ld test;
	cin>>test;
	while(test--){
	    ld a,b,c,x,y,z;
	    ld total =240.00;
	    cin>>a>>b>>c;
	    cin>>x>>y>>z;
	    vector<pairs> vec = {{x*1.0/a*1.0,a*1.0},{y*1.0/b*1.0,b*1.0},{z*1.0/c*1.0,c*1.0}};
	    ld ans = 0;
	    sort(vec.rbegin(),vec.rend());
	    for(int i = 0;i<3;i++){
	       // cout<<vec[i].f<<" "<<vec[i].s<<endl;
	        if(vec[i].s*20<=total){
	            ans+=vec[i].f*vec[i].s*20;
	            total-=vec[i].s*20;
	            
	        }
	        else{
	           // cout<<total/vec[i].s<<endl;
	            ans+=vec[i].f*vec[i].s*(total/vec[i].s);
	            break;
	        }
	    }
	    cout<<ans<<endl;
	    
	}
	return 0;
}

1
7 8 9
7 8 9
answer is 240
but by yur approach its 239

1 Like

If someone can help me to when not to use dp as this question seems to me as a dp question I tried doing same but couldn’t succeeded.
If you could share your approach for this question.
Thanks in advance! :slight_smile:

How would we solve it if the values were large i.e without a n^3 solution?