# PROBLEM LINK:

Author: Daanish Mahajan
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

Easy-Medium

# PREREQUISITES:

Dynamic Programming

# PROBLEM

There are N chapters and only K minutes are left before the exam. Chapter i will be worth M_i marks in the paper, and shall take T_i minutes to prepare. Chef can study the chapters in any order but need to study them completely and atmost once. He knows that he will forget the first chapter that he will prepare (due to lack of sleep) and wonâ€™t be able to score any marks in it. Find the maximum marks that Chef can score in the exam.

# EXPLANATION:

Since our goal is to maximize the Chef score, and we know that the Chef will forget the first chapter he prepares due to lack of sleep. So whatever the set of chapters Chef plans to prepare in given time, he will always prepare the chapter first which has minimum marks among the set of chapters he chooses.

We can use Dynamic Programming to find the maximum marks Chef can score in the given exam. Letâ€™s move towards it:

• DP[0][j] denotes the maximum marks that Chef can prepare in j minutes such that he doesnâ€™t forgot any chapter.

• DP[1][j] denotes the maximum marks that Chef can prepare in j minutes such that he will forgot exactly one chapter.

Suppose Chef wants to prepare the i^{th} chapter which takes t time to completely prepare it. So the maximum time Chef can start preparing this chapter such that he can prepare this chapter within the time is (k-t). Hence Chef can start preparing i^{th} chapter from any time in [0, k-t] endpoints inclusive.

Let j be the time Chef starts preparing for the i^{th} chapter which takes t time to prepare and carries m marks. Hence the transition will be as follows:

DP[0][j+t]=max(DP[0][j+t],m+DP[0][j])

and

DP[1][j+t]=max(DP[1][j+t],m+DP[1][j],DP[0][j])

Here DP[0][j] is the maximum marks which Chef can score in j time when i^{th} chapter is not included yet and Chef doesnâ€™t forgets any chapter he prepares.

And, DP[1][j] is the maximum marks which Chef can score in j time when i^{th} chapter is not included yet and Chef forgets the first chapter he prepares.

We need to carefully set the initial state of the DP's.

Finally, DP[1][K] will be the maximum score that Chef can score in K minutes when he forgot the first chapter he prepares.

# TIME COMPLEXITY:

O(N*K) per test case

# SOLUTIONS:

Setter
``````#include <bits/stdc++.h>
#define pb push_back
#define ll long long int
#define pii pair<int, int>

using namespace std;

const int maxn = 1e3;
const int maxt = 1e4;
const int maxp = 1e9;
ll dp[2][2][maxt + 10];

int main()
{
int t; cin >> t;
int n, time;
while(t--){
cin >> n >> time;
int t = 0;
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
for(int k = 0; k < maxt + 10; k++){
if(i + j == 2)dp[i][j][k] = -maxp - 100;
else dp[i][j][k] = 0;
}
}
}
for(int i = 0; i < n; i++){
int marks, rtime; cin >> marks >> rtime;
for(int j = 0; j <= time; j++){
dp[t][0][j] = max(dp[1 - t][0][j], j >= rtime ? dp[1 - t][0][j - rtime] + marks : 0);
dp[t][1][j] = max(dp[1 - t][1][j], j >= rtime ? max(dp[1 - t][1][j - rtime] + marks, dp[1 - t][0][j - rtime]) : -maxp - 100);
}
t = 1 - t;
}
ll ans = dp[1 - t][1][time];
cout << ans << endl;
}
}
``````
Tester
``````#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef double f80;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll,ll> pll;
#define double long double
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const int infi=0x3f3f3f3f;
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b>0) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}

int sum_nk=0;

void solve() {
int n=readIntSp(1,1000),k=readIntLn(1,10000);
sum_nk+=n*k;
assert(sum_nk<=10'000'000);
vector<vector<int>> dp(2,vi(k+1,-infl));
dp[0][0]=0;
fr(i,1,n) {
int m=readIntSp(1,1000'000'000),t=readIntLn(1,k);
for(int j=k-t; j>=0; j--) {
dp[1][j+t]=max(dp[1][j+t],dp[1][j]+m);
dp[0][j+t]=max(dp[0][j+t],dp[0][j]+m);
dp[1][j+t]=max(dp[1][j+t],dp[0][j]);
}
}
cout<<*max_element(all(dp[1]))<<endl;
}

signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(1);
int t=readIntLn(1,10);
//	cin>>t;
fr(i,1,t)
solve();
//	assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}

``````
Editorialsit
``````#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
int n,k;
cin>>n>>k;

int weight[n],time[n];

for(int i=0;i<n;i++)
cin>>weight[i]>>time[i];

int dp[2][k+1];

for(int i=0;i<2;i++)
{
for(int j=0;j<=k;j++)
{
if(i==0)
dp[i][j]=0;
else
dp[i][j]=INT_MIN;
}
}

for(int i=0;i<n;i++)
{
int temp=time[i];

for(int j=k-temp;j>=0;j--)
{
dp[0][j+temp]=max(dp[0][j+temp],weight[i]+dp[0][j]);
dp[1][j+temp]=max({dp[1][j+temp],weight[i]+dp[1][j],dp[0][j]});
}
}

cout<<dp[1][k]<<"\n";
}

int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);

int t;
cin>>t;

while(t--)
solve();

return 0;
}

``````
7 Likes

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

can you find which test case is not passing ?
or my approch is wrong?
Thanks

How do we ensure that there is no recounting?

I think it is similar to knapsack problem.
I tried but i am getting TLE.
Can anyone help me to know how we can implement it using knapsack.
Thanks in advance.

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

can you please find which test case is not passing ?
or my approch is wrong?
Thanks

Give me the code

https://www.codechef.com/viewsolution/44360335
This is my python. I am neither using a dynamic programming approach to solve this question nor I am getting TLE. Two of the cases are passing successfully and the rest are not. I donâ€™t know, What is wrong with my or my approach.
Could anybody please help me?

I thought doing sorting using a custom comparator and trying the select the best fit according to given conditions
Can somebody explain why the greedy approach doesnâ€™t work here ??

Here you are taking the optimum solution 0/1 knapsack solution and omitting the chapter with the least marks. This will not always give you the correct answer as the optimum chapter to be forgotten by chef might not be any of the chapters selected in the knapsack solution.
For example, the 0/1 knapsack solution may be chapter x,y and z, with m[x] being the least. But if we need to forget one chapter it might be wiser to select chapters p,q,z and forget p.
m[q] + m[z] > m[y] + m[z]

1 Like

I submitted two solutions:

Other things remaining the sameâ€¦ the former one is getting accepted, while the other one is getting a wrong answer verdict, and I am unable to figure out the reason behind it. Would be very glad if anyone could help.
I have used a matrix of pairs, with the dp[i][j].F â†’ max marks that can be stored from the i subjects and till the jth point of time, dp[i][j].S-> storing the min. element in the included elements.

Simple Recusrive Memoization No Sorting