0
$\begingroup$

I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below:

The director of a hospital want to schedule a working plan for a nurse in a given period of N consecutive days 1,..., N. Due to the policy of the hospital, each nurse cannot work all the days 1,..., N. Instead, there must be days off in which the nurse need to take a rest. A working plan is a sequence of disjoint working periods. A working period of a nurse is defined to be a sequence of consecutive days on which the nurse must work and the length of the working period is the number of consecutive days of that working period. The hospital imposes two constraints:

Each nurse can take a rest only one day between two consecutive working periods. it means that if the nurse takes a rest today, then she has to work tomorrow (1)

The length of each working period must be greater or equal to K1 and less than or equal to K2 (2)

The director of the hospital want to know how many possible working plans satisfying above constraint?

input

6 2 3

output

4

I have thought a lot and just give an initial idea: I will use an 1-D array to represent a schedule from day 1 to day N. for each day (ith day), I have two choices: the nurse will work this day or the nurse will not work on this day.

If the nurse does not work on the ith day, the ways for this case is the total ways of the ith-2 day. (Because she must have a day off on the previous day.

Else, the ways for this case will be the sum of total ways of the ith-j day, with j in [K1, K2].

However, I do not know why I am wrong and which way will be the correct answer. I really need your help to derive an appropriate algorithm

$\endgroup$
3
  • $\begingroup$ Can you provide attribution for where you read this? Can you identify the book (title & authors) and the exercise (e.g., exercise number, chapter number)? This helps others who have a similar question find this page by search, and complies with our requirements regarding crediting the source of copied material: cs.stackexchange.com/help/referencing $\endgroup$ – D.W. Dec 3 '20 at 16:11
  • $\begingroup$ @D.W. Oh i am so sorry I use the wrong vocab. It is just an exercise paper that my teacher gave to me for practice, $\endgroup$ – Hoang Nam Dec 3 '20 at 16:13
  • $\begingroup$ I see that you also posted this on SO and got an answer there: stackoverflow.com/q/65129090/781723. $\endgroup$ – D.W. Dec 12 '20 at 18:49
0
$\begingroup$

You can solve this problem with dynamic programming. Your states are dp[day_number][worked_sofar]. here is a recursive implementation:

#include<bits/stdc++.h>

using namespace std;

vector<vector<int> > dp;
int n, k1, k2;
int solve(int day, int sofar){
    if(day > n || sofar > k2)return 1;
    if(dp[day][sofar] != -1)return dp[day][sofar];
    int ans = solve(day + 1, sofar + 1);
    if(sofar >= k1)ans += solve(day + 1, 0);
    return dp[day][sofar] = ans;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> k1 >> k2;
    dp.assign(n + 1, vector<int>(k2 + 1, -1));
    cout<<solve(1, 0);
    return 0;
}

```
$\endgroup$
1
  • $\begingroup$ We deal with ideas, theory and pseudocode on the site. Would you mind explaining your idea on a high-level rather than just giving code that is somewhat cluttered with details not relevant for the problem in a theoretical sense? $\endgroup$ – Juho Dec 5 '20 at 9:37
0
$\begingroup$

The above answer from @Usman is almost right, except for the return condition part.

The sofar part needs to be exactly $0$ (if the nurse takes a day off) or in between $k_1$ and $k_2$.

Here is the correct version:

if (sofar > k2) return 0;
if (day >= 2) {
    if (sofar == 0 || sofar >= k1) return 1;   
    else return 0;  
}  
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.