Блог пользователя Pieck

Автор Pieck, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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.

»
3 года назад, # |
  Проголосовать: нравится +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..

  • »
    »
    3 года назад, # ^ |
    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
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)

  • »
    »
    3 года назад, # ^ |
    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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
    DP Code

    This would be correct right?

»
3 года назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

CSES — Projects: This seems similar to your problem.