Did anyone solved this question in O(1) [Using conditional statements and some basic math] ??
It seems to me the time complexity is O(21 X 21). If you iterate through possible numbers of C1 and C2, the number of C3 is (240 - number of C1 * A - number of C2 * B) / C. There is no need to iterate through C3, since you just pick the max. from the remaining time after setting the numbers of C1 and C2.
Can someone tell me if this can be solved using recursion:
#include<bits/stdc++.h>
using namespace std;
int solve(vector<pair<long long, int>> &v, int totalTime, int remainingTime, long long points, int idx, int n, vector<int> &ansVec){
int a, b, xQuestions;
if(idx == n){
ansVec.push_back(points);
// cout << points << endl;
return points;
}
// considering
// if((v.at(idx).second * 20) <= remainingTime){
// remainingTime = remainingTime - (v.at(idx).second * xQuestions);
// points = points + v.at(idx).first * xQuestions;
// a = solve(v, totalTime, remainingTime, points, idx+1, n);
// }else{
xQuestions = remainingTime/v.at(idx).second;
xQuestions = xQuestions < 20 ? xQuestions: 20;
remainingTime = remainingTime - (v.at(idx).second * xQuestions);
points = points + v.at(idx).first * xQuestions;
a = solve(v, totalTime, remainingTime, points, idx+1, n, ansVec);
// }
// not considering
remainingTime = remainingTime + (v.at(idx).second * 20);
points = points - v.at(idx).first * xQuestions;
b = solve(v, totalTime, remainingTime, points, idx+1, n, ansVec);
// int mz = a + b;
return a + b;
}
int main(){
int t = 0;
cin >> t;
while(t--){
int total = 240;
int ans = 0;
int a, b, c;
cin >> a >> b >> c;
long long x, y, z;
cin >> x >> y >> z;
vector<pair<long long, int>> v;
v.push_back(make_pair(x, a));
v.push_back(make_pair(y, b));
v.push_back(make_pair(z, c));
vector<int> ansVec;
ans = solve(v, total, 240, 0, 0, 3, ansVec);
sort(ansVec.begin(), ansVec.end());
cout << ansVec.at(ansVec.size()-1) << endl;
}
return 0;
}
This is how I did, although the sample inputs are passing, I’m missing something.
Can someone please help me understand where im going wrong.
thanks for that.
I have an issue with the explanation there
this coveys wrong sense towards the approach .
can u please explain how it is 240
Just change for all loops to start from p = 0,q =0 and r =0. Because there can be situations where we did not solve any question for a given section.
I have made the changes to your code.
#include <bits/stdc++.h>
#define int long long int
using namespace std;
int32_t main()
{
int t;
cin >> t;
for (int i = 0; i < t; i++)
{
int a,b,c,x,y,z,M=0;
cin>>a>>b>>c;
cin>>x>>y>>z;
int p,q,r;
vector<vector> number;
for(p=0;p<=20;p++){
for(q=0;q<=20;q++){
for(r=0;r<=20;r++){
if(ap+bq+cr<=240){
vector vec;
vec={p,q,r};
number.push_back(vec);
}
}
}
}
for(int i=0;i<number.size();i++){
p=number[i][0];
q=number[i][1];
r=number[i][2];
int sum=xp+yq+zr;
if(M<=sum) M=sum;
}
cout<<M<<’\n’;
}
return 0;
}
The fact that it had a brute force solution didn’t cross my mind at first, so I went with DP here as it was covering all the cases, If you are confident with your DP and constraints allow u can go with DP it will never fail, on the other hand, greedy may or may not fail (because in DP you don’t have to prove if the intuition was correct or not).
In this problem, it was overkill for DP though I did it , I also got the brute force solution as I was coding my DP solution.
I’d say it will come to you automatically as you solve more and more questions.
1 Like
my code failed for some test cases, im unable to find the bug,pls find it below
https://ideone.com/6CwgDF
can someone point the mistake out?
For below test case,
1
7 8 9
7 8 9
Correct output is: 240
Your Output is: 239
1 Like
and this is because Your code is doing something like: Calculating points of 20 questions of 7 min/que type= (total 140 min) then 11 questions of 9 min/ que type (total=239), total given time is 240 min but It haven’t used the last minute, If You manage to use that last min(total time) by reducing 1 question of 7min/que type and adding 1 question of 8 min/que type, Code outcome will be 240, as 19 questions of 7 min/que type + 11 of 9 min type + 1 of 8 min/que type= (total 240 min used and point calculated is also 240).
thanks, i got it.
#include <bits/stdc++.h>
#define ll long long
int main(){
// #ifndef ONLINE_JUDGE
// freopen("input.txt", "r", stdin);
// #endif
// precomp();
FAST;
int t ; cin >>t;
while(t--)
{
ll a,b,c;
ll x,y,z; cin>>a>>b>>c>>x>>y>>z;
vector<ll> cost;
vector<ll> val;
for(int i =0;i<60;i++){
if(i<20){
cost.pb(a);
val.pb(x);
}
else if(i<40){
cost.pb(b);
val.pb(y);
}
else{
cost.pb(c);
val.pb(z);
}
}
vector<vector<ll>> dp(61,vector<ll>(241,0));
for(int i = 1 ; i<=60;i++){
for(int j=1;j<=240;j++){
if(j>=cost[i-1]){
dp[i][j]=max(dp[i-1][j],val[i-1]+dp[i-1][j-cost[i-1]]);
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
cout << dp[60][240]<<endl;
return 0;
} // int main scope
simple knapsack solution happy vector users 
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int time[3];
for (int i = 0; i < 3; i++)
{
cin >> time[i];
}
int points[3];
for (int i = 0; i < 3; i++)
{
cin >> points[i];
}
int totalPoints = (points[0] + points[1] + points[2]) * 20;
int totalTime = (time[0] + time[1] + time[2]) * 20;
int maxPoints = 0;
if (totalTime > 240)
{
for (int i = 0; i < 3; i++)
{
int subTime = totalTime;
int subPoints = totalPoints;
while (subTime > 240)
{
subTime -= time[i];
subPoints -= points[i];
}
maxPoints = max(maxPoints, subPoints);
}
cout << maxPoints << endl;
}
else
{
cout << totalPoints << endl;
}
}
return 0;
}
Can anyone plz check my code and point out what mistake am I doing??