CLOSED
Recently I encountered a problem in one of the coding rounds that I attended and as of yet I am unable to solve it, or even find a direction in which to tackle this. I've tried using greedy or dp but could not find any solution. I don't know what the difficulty of the problem might be, but I thought of sharing it anyway. Any help would be appreciated.
Problem Statement:
You are standing in an election for your college. To win the election you need to win maximum number of hostels out of N possible. Your friends come up with a strategy to help you win. According to them for a given hostel i (1<=i<=N) the campaigning in that hostel starts from day a[i]. You are given L (the end date for campaigning). To win in a particular hostel i, you can start campaigning in that hostel from a[i] onward (a[i] inclusive), but you need to campaign for at least b[i] days straight (without any breaks) to win in that hostel, such that your last campaigning day doesn't exceed L.
Constraints:
1<=T<=1000
1<=N<=1000, 1<=L<=1000
1<=a[i], b[i]<=1000
Input:
T (testcases)
N L
a[1] b[1]
a[2] b[2]
...
...
a[N] b[N]
Output:
X (Maximum hostels you could win)
Sample Testcase:
Input:
1
2 10
2 2
2 7
Output:
2
Explanation:
You campaign from day 2 to day 8 in hostel 2 and from day 9 to day 10 in hostel 1.
Consider that we are in a state (i,j) if we analyzed i hostels and finished at day j. This state can lead to all states (i+1, j+b[k]) where k is a hostel that was not yet analyzed, j+b[k] is less L and j is greater or equal to a[k]. Each state save the quantity of hostels we won at that state.
UPD: Bad idea, need to keep the mask of the visited hostels for each state, which is impossible for these constraints.
Yeah, I thought along the same lines but encountered the same problem you did, how to keep track of hostels we have already campaigned for.
maybe use $$$dp[i][j]$$$ as the number of hostel you won till $$$i'th$$$ hostel and $$$j'th$$$ day you were last campaigning and make transitions on whether you wanna win this hostel or not..
But how will you keep track of which hostels we have won in a state?
UPD: Sorry, my bad. Thanks for the solution though.
why do we need to keep track of them? for every state there are only 2 transition.
dp[i]=max(dp[i-1], (for every a[i] from 0->n)(i-b[i]==a[i])?dp[a[i]]+1:0))
i-> days starting from 0->L dp[i]->max no of disjoint ranges(a[i],a[i]+b[i]) for less than i
Auto comment: topic has been updated by Pieck (previous revision, new revision, compare).
Seems that there exists an optimal solution where the hostels are visited in non decreasing order of a.
Lets say there are two hostels a_1 <= a_2, if you can do campaign in hostel 2 then hostel 1, you can also do campaign in hostel 1 then hostel 2 regardless. So you can just sort the hostels and consider them one by one (which leads to an obvious O(n^2) DP)
Isn't it O(n) DP?
dp[i] = max(dp[i+1], 1 + dp[i + b[i]]); for all i from L to 0
definitely possible to be O(n) (after sorting) too, but not sure about your construct.
n — number of hostels
l — last day
vec[i] — {a[i],b[i]}
This would be correct right?
CSES — Projects: This seems similar to your problem.