By Doublade, history, 12 days ago,

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.

• +18

 » 12 days ago, # | ← Rev. 2 →   0 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.
•  » » 12 days ago, # ^ |   0 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.
 » 12 days ago, # |   +7 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..
•  » » 12 days ago, # ^ | ← Rev. 3 →   0 But how will you keep track of which hostels we have won in a state? UPD: Sorry, my bad. Thanks for the solution though.
•  » » » 12 days ago, # ^ |   +1 why do we need to keep track of them? for every state there are only 2 transition.
 » 12 days ago, # | ← Rev. 6 →   +1 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
 » 12 days ago, # |   0 Auto comment: topic has been updated by Doublade (previous revision, new revision, compare).
 » 12 days ago, # | ← Rev. 3 →   +2 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)
•  » » 12 days ago, # ^ | ← Rev. 2 →   +6 Isn't it O(n) DP?dp[i] = max(dp[i+1], 1 + dp[i + b[i]]); for all i from L to 0
•  » » » 11 days ago, # ^ |   +1 definitely possible to be O(n) (after sorting) too, but not sure about your construct.
•  » » 11 days ago, # ^ | ← Rev. 4 →   0 DP Coden — number of hostelsl — last dayvec[i] — {a[i],b[i]}  int dp[n+5][l+5]; //dp[i][x] = max hostels you can win in x days with only first i hostels for(int i=0;i
 » 11 days ago, # |   -6 CSES — Projects: This seems similar to your problem.