1997

1997. First Day Where You Have Been in All the Rooms (Medium)

There are n rooms you need to visit, labeled from 0 to n - 1. Each day is labeled, starting from 0. You will go in and visit one room a day.

Initially on day 0, you visit room 0. The order you visit the rooms for the coming days is determined by the following rules and a given 0-indexed array nextVisit of length n:

• Assuming that on a day, you visit room i,
• if you have been in room i an odd number of times (including the current visit), on the next day you will visit the room specified by nextVisit[i] where 0 <= nextVisit[i] <= i;
• if you have been in room i an even number of times (including the current visit), on the next day you will visit room (i + 1) mod n.

Return the label of the first day where you have been in all the rooms. It can be shown that such a day exists. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: nextVisit = [0,0]
Output: 2
Explanation:
- On day 0, you visit room 0. The total times you have been in room 0 is 1, which is odd.
  On the next day you will visit room nextVisit[0] = 0
- On day 1, you visit room 0, The total times you have been in room 0 is 2, which is even.
  On the next day you will visit room (0 + 1) mod 2 = 1
- On day 2, you visit room 1. This is the first day where you have been in all the rooms.

Example 2:

Input: nextVisit = [0,0,2]
Output: 6
Explanation:
Your room visiting order for each day is: [0,0,1,0,0,1,2,...].
Day 6 is the first day where you have been in all the rooms.

Example 3:

Input: nextVisit = [0,1,2,0]
Output: 6
Explanation:
Your room visiting order for each day is: [0,0,1,1,2,2,3,...].
Day 6 is the first day where you have been in all the rooms.

 

Constraints:

• n == nextVisit.length
• 2 <= n <= 105
• 0 <= nextVisit[i] <= i

Solution 1. DP

Let dp[i] be the number of days needed to jump from room 0 to room i. The answer is dp[N - 1].

For dp[i], on top of the days needed for reaching room i-1, i.e. dp[i-1], we need these extra days to go from room i-1 to room i.

• If A[i-1] == i-1, we just need 2 days
• Otherwise, we need to jump to room A[i-1] first, taking 1 day. Then spent dp[i-1] - dp[A[i-1]] days to go from room A[i-1] to room i-1 again. Lastly, take 1 day to go from room i-1 to room i. So in total, we need extra 2 + dp[i-1] - dp[A[i-1]] days.

After some simplification, we get the following:

dp[i] = dp[i-1]                           // days needed to reach room i - 1
          + 2 + dp[i-1] - dp[A[i-1]]      // days needed to go from room i - 1 to room i
      = 2 + 2 * dp[i-1] - dp[A[i-1]]
               where 0 <= i < N - 1
dp[0] = 0

// OJ: https://leetcode.com/problems/first-day-where-you-have-been-in-all-the-rooms/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& A) {
        long mod = 1e9 + 7, N = A.size();
        vector<int> dp(N + 1);
        for (int i = 1; i < N; ++i) {
            dp[i] = ((long)2 + 2 * dp[i - 1] - dp[A[i - 1]] + mod) % mod;
        }
        return dp[N - 1];
    }
};

Discuss

https://leetcode.com/problems/first-day-where-you-have-been-in-all-the-rooms/discuss/1445156/C%2B%2B-DP