Doublade's blog

By Doublade, history, 12 days ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +18
  • Vote: I do not like it

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +7 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it +1 Vote: I do not like it

      why do we need to keep track of them? for every state there are only 2 transition.

»
12 days ago, # |
Rev. 6   Vote: I like it +1 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Doublade (previous revision, new revision, compare).

»
12 days ago, # |
Rev. 3   Vote: I like it +2 Vote: I do not like it

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   Vote: I like it +6 Vote: I do not like it

    Isn't it O(n) DP?

    dp[i] = max(dp[i+1], 1 + dp[i + b[i]]); for all i from L to 0

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      definitely possible to be O(n) (after sorting) too, but not sure about your construct.

  • »
    »
    11 days ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it
    DP Code

    This would be correct right?

»
11 days ago, # |
  Vote: I like it -6 Vote: I do not like it

CSES — Projects: This seems similar to your problem.