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

Nguồn: LeetCode 1997 Độ khó: Khá Quy hoạch động Mảng cộng dồn Modulo

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

1997. First Day Where You Have Been in All the Rooms – Ngày đầu tiên bạn đã ở trong tất cả các phòng (LeetCode, độ khó Medium)

Có $n$ phòng bạn cần đến thăm, được đánh số từ $0$ đến $n - 1$. Các ngày cũng được đánh số, bắt đầu từ $0$. Mỗi ngày bạn sẽ vào thăm đúng một phòng.

Ban đầu, vào ngày $0$, bạn thăm phòng $0$. Thứ tự thăm các phòng ở những ngày tiếp theo được xác định bởi các quy tắc sau cùng với một mảng nextVisit độ dài $n$ (đánh số từ 0):

• Giả sử vào một ngày nào đó bạn thăm phòng $i$,
• nếu bạn đã vào phòng $i$ một số lẻ lần (tính cả lần hiện tại) thì vào ngày tiếp theo bạn sẽ thăm phòng nextVisit[i], trong đó $0 \le$ nextVisit[i] $\le i$;
• nếu bạn đã vào phòng $i$ một số chẵn lần (tính cả lần hiện tại) thì vào ngày tiếp theo bạn sẽ thăm phòng $(i + 1) \bmod n$.

Hãy trả về số thứ tự của ngày đầu tiên mà bạn đã từng ở trong tất cả các phòng. Có thể chứng minh rằng ngày như vậy luôn tồn tại. Vì đáp án có thể rất lớn, hãy trả về nó theo modulo $10^9 + 7$.

Ràng buộc:

• $n =$ nextVisit.length
• $2 \le n \le 10^5$
• $0 \le$ nextVisit[i] $\le i$

Định dạng vào/ra để chạy thử trên máy: trên LeetCode các bạn chỉ cần viết hàm firstDayBeenInAllRooms trong class Solution. Để chạy như một chương trình bình thường (và dùng khung chạy tay bên dưới), mình đặt thêm định dạng:

• Dữ liệu vào: dòng đầu là số nguyên $n$, dòng thứ hai gồm $n$ số nguyên nextVisit[0], nextVisit[1], ..., nextVisit[n-1].
• Kết quả: một số nguyên là số thứ tự ngày cần tìm, lấy modulo $10^9 + 7$.

Ví dụ 1 – LeetCode

Input: nextVisit = [0,0]
Output: 2

Ví dụ 1 – stdin / stdout

2
0 0
---
2

Ví dụ 2 – LeetCode

Input: nextVisit = [0,0,2]
Output: 6

Ví dụ 2 – stdin / stdout

3
0 0 2
---
6

Ví dụ 3 – LeetCode

Input: nextVisit = [0,1,2,0]
Output: 6

Ví dụ 3 – stdin / stdout

4
0 1 2 0
---
6

Giải thích ví dụ của đề:

• Ví dụ 1:
  • Ngày 0, bạn thăm phòng 0. Tổng số lần bạn đã vào phòng 0 là 1, là số lẻ. Ngày tiếp theo bạn sẽ thăm phòng nextVisit[0] = 0.
  • Ngày 1, bạn thăm phòng 0. Tổng số lần bạn đã vào phòng 0 là 2, là số chẵn. Ngày tiếp theo bạn sẽ thăm phòng $(0 + 1) \bmod 2 = 1$.
  • Ngày 2, bạn thăm phòng 1. Đây là ngày đầu tiên bạn đã ở trong tất cả các phòng.
• Ví dụ 2: thứ tự phòng bạn thăm theo từng ngày là [0,0,1,0,0,1,2,...]. Ngày 6 là ngày đầu tiên bạn đã ở trong tất cả các phòng.
• Ví dụ 3: thứ tự phòng bạn thăm theo từng ngày là [0,0,1,1,2,2,3,...]. Ngày 6 là ngày đầu tiên bạn đã ở trong tất cả các phòng.

1997. First Day Where You Have Been in All the Rooms (LeetCode, 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 $10^9 + 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 \le n \le 10^5$
• 0 <= nextVisit[i] <= i

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Lưu ý nhỏ: khi nộp trên CLUE OJ các bạn dán toàn bộ code, gồm cả hàm main, vì đề trên CLUE OJ đọc dữ liệu vào và in kết quả đúng theo định dạng ở phần đề bài, giống như khi các bạn chạy thử trên máy hoặc ở trang Chạy code online của blog.

Mình giải thích thêm ví dụ 2 (nextVisit = [0,0,2]) cho bạn nào chưa hiểu đề:

Ngày	Phòng	Số lần đã vào phòng đó	Ngày sau đi đâu
0	0	1 (lẻ)	nextVisit[0] = 0
1	0	2 (chẵn)	(0 + 1) mod 3 = 1
2	1	1 (lẻ)	nextVisit[1] = 0
3	0	3 (lẻ)	nextVisit[0] = 0
4	0	4 (chẵn)	1
5	1	2 (chẵn)	2
6	2	1 (lẻ)	đã đủ 3 phòng → đáp án 6

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Mô phỏng từng ngày · số ngày có thể ~2^NCách 2QHĐ + mảng cộng dồn · O(N)

Cách 1Mô phỏng từng ngày – O(số ngày)

Cách tự nhiên nhất là làm đúng như đề: giữ mảng cnt[] đếm số lần đã vào từng phòng, biến visited đếm số phòng đã từng vào, rồi cho từng ngày trôi qua. Ngày nào visited bằng $n$ thì đó là đáp án.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& nextVisit) {
        int n = (int) nextVisit.size();
        vector<long long> cnt(n, 0);
        int visited = 0, room = 0;
        long long day = 0;
        while (true) {
            cnt[room]++;
            if (cnt[room] == 1) visited++;
            if (visited == n) return day % 1000000007;
            if (cnt[room] % 2 == 1) room = nextVisit[room];
            else room = (room + 1) % n;
            day++;
        }
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> nextVisit(n);
    for (int i = 0; i < n; i++) cin >> nextVisit[i];
    Solution sol;
    cout << sol.firstDayBeenInAllRooms(nextVisit);
    return 0;
}

import sys
from typing import List

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        n = len(nextVisit)
        cnt = [0] * n
        visited, room, day = 0, 0, 0
        while True:
            cnt[room] += 1
            if cnt[room] == 1:
                visited += 1
            if visited == n:
                return day % 1000000007
            if cnt[room] % 2 == 1:
                room = nextVisit[room]
            else:
                room = (room + 1) % n
            day += 1

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    nextVisit = list(map(int, data[1:1 + n]))
    print(Solution().firstDayBeenInAllRooms(nextVisit))

if __name__ == "__main__":
    main()

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng cnt nên là $O(N)$.
• Thời gian: bằng đúng số ngày phải mô phỏng. Vấn đề là số ngày này có thể rất lớn: với nextVisit toàn số 0, mỗi lần sang một phòng mới ta lại bị đá về phòng 0 và đi lại từ đầu, số ngày gấp đôi sau mỗi phòng, đáp án là $2^n - 2$.

Không gian$O(N)$

Thời gian$O(\text{số ngày})$, tệ nhất $\approx O(2^N)$

Chắc chắn TLE

Mình thử với $n = 30$ và nextVisit toàn 0: phải mô phỏng $2^{30} - 2 \approx 1.07 \cdot 10^9$ ngày, code C++ chạy hơn 4 giây. Còn $n$ lên tới $10^5$ thì số ngày là con số khổng lồ, chính vì thế đề mới bắt lấy modulo $10^9 + 7$. Cách này chỉ dùng để hiểu đề và làm code đối chiếu.

Cách 2Quy hoạch động + mảng cộng dồn – O(N)

Bài này áp dụng Quy Hoạch Động như sau. Điều đầu tiên cần để ý là nextVisit[i] $\le i$: khi nhảy theo nextVisit ta chỉ có thể lùi lại (hoặc đứng yên), còn muốn tiến lên thì chỉ có cách đi sang phòng $i + 1$. Từ đó rút ra hai nhận xét:

Nhận xét

• Các phòng được vào lần đầu theo đúng thứ tự $0, 1, 2, \ldots, n - 1$. Vậy đáp án chính là ngày đầu tiên vào phòng $n - 1$.
• Ngay khi lần đầu bước vào phòng $i$, mọi phòng $0, 1, \ldots, i - 1$ đều đã được vào một số chẵn lần (vì lần cuối cùng ta rời khỏi chúng là để tiến sang phòng kế, mà muốn tiến thì số lần phải chẵn). Nói cách khác, các phòng phía trước giống như "được làm mới".

Gọi $f[i]$ là số ngày (số bước) cần để đi từ lúc lần đầu đứng ở phòng $i - 1$ tới lúc lần đầu đứng ở phòng $i$.

Khi lần đầu ta ở phòng $i - 1$ (số lần là 1, lẻ), ngày hôm sau ta nhảy về phòng $v = $ nextVisit[i - 1]. Lúc này phòng $v$ có số lần lẻ, các phòng từ $v + 1$ tới $i - 1$ đều chẵn – y hệt tình trạng lúc lần đầu ta tới phòng $v$. Thế nên ta phải thực hiện lặp lại đúng các bước từ phòng $v$ → phòng $i - 1$ như lần đầu, mất $f[v + 1] + f[v + 2] + \ldots + f[i - 1]$ ngày. Về lại phòng $i - 1$ lần này là lần chẵn nên ngày kế tiếp ta sang được phòng $i$. Cộng thêm 1 ngày nhảy về $v$ và 1 ngày sang phòng $i$, ta có:

Công thức

$f[i] = f[i - 1] + f[i - 2] + \ldots + f[v + 1] + 2$, với $v = $ nextVisit[i - 1].

Nếu cứ cộng tay như vậy thì mỗi $f[i]$ mất $O(N)$, tổng cộng $O(N^2)$ – vẫn chậm với $n = 10^5$. Để tăng tốc thì ta dùng mảng cộng dồn: gọi $sum[i] = f[1] + f[2] + \ldots + f[i]$ (với $sum[0] = 0$). Khi đó:

Tăng tốc bằng mảng cộng dồn

$f[i] = sum[i - 1] - sum[v] + 2$,   $sum[i] = sum[i - 1] + f[i]$.
Thú vị là $sum[i]$ chính là ngày đầu tiên ta bước vào phòng $i$. Đáp án là $sum[n - 1] = f[1] + f[2] + \ldots + f[n - 1]$.

Vậy, tóm gọn lại, bài này như sau:

for i từ 1 -> n:
    f[i]   = sum[i - 1] - sum[nextVisit[i - 1]] + 2
    sum[i] = sum[i - 1] + f[i]
Đáp án: sum[n - 1]

Minh hoạ: đoạn đi lặp lại

Em nhập mảng nextVisit rồi bấm Tiếp. Mỗi ô là một ngày (số nhỏ phía trên là số thứ tự ngày, số to là phòng thăm ngày đó). Mỗi bước mình thêm đoạn ngày để đi từ phòng $i - 1$ sang phòng $i$: ô xanh dương là đoạn đi lặp lại, nó giống hệt đoạn tô vàng phía trước:

nextVisit

Ví dụ nhanh:

Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên. Trong code mảng dp chính là $f$; vòng lặp chạy tới $i = n$ (tính dư một phần tử, không ảnh hưởng gì), đáp án lấy $sum[n - 1]$. Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
int dp[100005];
int sum[100005];

class Solution {
public:
    int firstDayBeenInAllRooms(vector<int>& nextVisit) {
        memset(dp, 0, sizeof(dp));
        memset(sum, 0, sizeof(sum));
        int n = (int) nextVisit.size();
        for (int i = 1; i <= n; i++) {
            dp[i] = (sum[i - 1] - sum[nextVisit[i - 1]] + 2 + MOD) % MOD;
            sum[i] = (sum[i - 1] + dp[i]) % MOD;
        }
        return sum[n - 1];
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> nextVisit(n);
    for (int i = 0; i < n; i++) cin >> nextVisit[i];
    Solution sol;
    cout << sol.firstDayBeenInAllRooms(nextVisit);
    return 0;
}

import sys
from typing import List

MOD = 1000000007

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        n = len(nextVisit)
        dp = [0] * (n + 1)
        s = [0] * (n + 1)  # s[i] = dp[1] + dp[2] + ... + dp[i]
        for i in range(1, n + 1):
            dp[i] = (s[i - 1] - s[nextVisit[i - 1]] + 2) % MOD
            s[i] = (s[i - 1] + dp[i]) % MOD
        return s[n - 1]

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    nextVisit = list(map(int, data[1:1 + n]))
    print(Solution().firstDayBeenInAllRooms(nextVisit))

if __name__ == "__main__":
    main()

C++▶ Chạy tay từng dòng codedp[i] = sum[i-1] - sum[nextVisit[i-1]] + 2, sum[i] = sum[i-1] + dp[i], đáp án sum[n-1].

Dữ liệu vào (stdin) – sửa thoải mái3 0 0 2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4const int MOD = 1000000007;

5int dp[100005];

6int sum[100005];

7

8class Solution {

9public:

10 int firstDayBeenInAllRooms(vector<int>& nextVisit) {

11 memset(dp, 0, sizeof(dp));

12 memset(sum, 0, sizeof(sum));

13 int n = (int) nextVisit.size();

14 for (int i = 1; i <= n; i++) {

15 dp[i] = (sum[i - 1] - sum[nextVisit[i - 1]] + 2 + MOD) % MOD;

16 sum[i] = (sum[i - 1] + dp[i]) % MOD;

17 }

18 return sum[n - 1];

19 }

20};

21

22int main() {

23 int n;

24 cin >> n;

25 vector<int> nextVisit(n);

26 for (int i = 0; i < n; i++) cin >> nextVisit[i];

27 Solution sol;

28 cout << sol.firstDayBeenInAllRooms(nextVisit);

29 return 0;

30}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: hai mảng dp và sum nên là $O(N)$.
• Thời gian: một vòng lặp $n$ lần, mỗi lần $O(1)$ nhờ mảng cộng dồn, nên là $O(N)$ nha các bạn.

Không gian$O(N)$

Thời gian$O(N)$

Trừ trong modulo phải cộng thêm MOD

Vì sum đã bị lấy modulo nên sum[i - 1] có thể nhỏ hơn sum[nextVisit[i - 1]], hiệu bị âm. Trong C++ phép % với số âm cho ra số âm, nên mình cộng thêm MOD trước khi lấy % MOD. Các giá trị đều nhỏ hơn $10^9 + 7$ nên biểu thức không vượt quá khoảng $2 \cdot 10^9$, vẫn vừa kiểu int. Trong Python thì % luôn trả về số không âm nên không cần bước này.

Ghi chú của mình: code C++ và Python của cả 2 cách đều cho đúng 3 ví dụ của đề, và đã được so với một chương trình mô phỏng độc lập trên 300 bộ test ngẫu nhiên với $n \le 13$ – khớp hết. Để kiểm phần modulo, mình so thêm cách 2 với bản tính bằng số nguyên lớn của Python (không lấy modulo giữa chừng) trên 100 bộ test có $n \le 400$ và 2 bộ $n = 10^5$ – khớp hết. Với $n = 10^5$, cách 2 bản C++ chạy khoảng 0.03 giây, bản Python dưới 0.1 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇