COCA2006-EDITORIAL

Contest link

PROBLEM LINK:

Contest
Practice

Author: yashu2040
Tester: pulkit_0110
Editorialist: freemancs

DIFFICULTY:

MEDIUM-HARD.

PREREQUISITES:

DP, Math

PROBLEM:

We want to distribute the beds to all N states such that each state gets atmost B beds.

EXPLANATION:

This problem can be solved using Dynamic Programming.

dp[i]—>>the number of ways such that we allocated i beds so far.

For each state we first iterate over number of beds used so far and then we consider all possibilites of giving beds to it.

Code for above logic

Setter's Solution

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define pb push_back
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
main()
{
// fast();
int n, B;
cin>>B>>n;
vector dp(B+1);
// dp[i] - the number of ways such that we allocated i beds so far.
dp[0]=1;
for(int states=0;states<n;states++)
{
int req;
cin>>req;
//For each state,we consider the number of beds allocated so far(used).
for(int used=B;used>=0;used–)
{
int tmp = dp[used];
//Each state can take minimum 0 beds and maximum req beds
int L = used+1;//We allocate 1 bed
int R = used+min(req,B-used);//Or we allocate the number of beds equal to req taking into account beds remaining
for(int i=L;i<=R;i++)
{
dp[i]=(dp[i]%mod+tmp%mod)%mod;
}
}

}
//final answer is dp[k].
cout<<dp[B];

}

TIME COMPLEXITY- O(NBB) WHICH WILL THROW TLE.

How to optimise it??

Lets try to prevent the use of innermost loop.
We see that we are adding tmp to range L to R for each state.
Here,we can use prefix sums for this.We can make pref array of size B for each state and we increase the count of pref[L] by 1 and decrease the count of pref[R+1]
by 1.
After iterating over all possibilites for each state,we can simply do prefix sum of our pref array and we increase dp[i] by pref[i].
Time Complexity-O(N*B)

Setter's Solution
	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long
	#define int long long
	#define pb push_back
	#define mod 1000000007
	#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
	main()
	{
	//	fast();
		int n, B;
		cin>>B>>n;
		vector<int> dp(B+1);
		// dp[i] - the number of ways such that we allocated i beds so far.
		dp[0]=1;
		for(int states=0;states<n;states++) 
		{
			int req;
			cin>>req;
			vector<int> pref(B+1,0);
			//For each state,we consider the number of beds allocated so far(used).
			for(int used=B;used>=0;used--) 
			{
				int tmp = dp[used];
				//Each state can take minimum 0 beds and maximum req beds
				int L = used+1;//We allocate 1 bed
				int R = used+min(req,B-used);//Or we allocate the number of beds equal to req taking into account beds remaining 
				
				/*for(int i=L;i<=R;i++) 
				{
					dp[i]=(dp[i]%mod+tmp%mod)%mod;
				}*/
				if(L <= R)
				{
					pref[L]=(pref[L]%mod+tmp%mod)%mod;
					if(R + 1 <= B)
					{
					   pref[R+1]=pref[R+1]-tmp;
					   if(pref[R+1]<0)
					   pref[R+1]+=mod;
					}
				}
				
			}
			int sum = 0;
			for(int i=0;i<=B;i++)
			{
				sum=(sum%mod+pref[i]%mod)%mod;
				dp[i]=(dp[i]%mod+sum%mod)%mod;
			}
			
		}
		//final answer is dp[B].
		cout<<dp[B]%mod;
	}

Can you tell the original source of this question? It would be helpful :slight_smile:

I didnt understand the editorial. Can someone explain it?

2 Likes

https://www.codechef.com/PCO12020/problems/HELCARP
this is a very similar question

1 Like

thank you :slight_smile:

Thanks for the nice ques, for those who don’t understand that, they can try this code
https://www.codechef.com/viewsolution/34874516