ICPC Regional Hanoi 2024 Editorial

G: Gid-osh

Đề bài

Cho dãy $a$ có $n$ phần tử. Bỏ đi chính xác một phần tử sao cho $\max-\min$ của dãy là nhỏ nhất.

Lời giải

Sắp xếp $a$ tăng dần. Nếu $n=2$ thì đáp án là $0$ . Nếu không thì ta sẽ bỏ phần tử đầu hoặc cuối đi, đáp án cuối cùng là $\min(a_{n - 1} - a_1, a_n - a_2)$ .

F: FizzBuzz

Đề bài

Cho 3 số nguyên dương $n,a,b$ , chương trình FizzBuzz sẽ in ra:

fizzbuzz nếu $n$ chia hết cho cả $a$ và $b$ .
fizz nếu $n$ chia hết cho $a$ nhưng không chia hết cho $b$ .
buzz nếu $n$ chia hết cho $b$ nhưng không chia hết cho $a$ .
n nếu $n$ không chia hết cho cả $a$ và $b$ .

Cho số tự nhiên $n \left(1\le n\le10^9\right)$ và một xâu có dạng như trên, tìm một bộ số $a,b$ bất kì sao cho $1<a<b\le10^9$ và chương trình FizzBuzz với đầu vào $n$ trả về đúng xâu đó. In ra -1 nếu không tồn tại $a,b$ thoả mãn.

Lời giải

Ta chỉ cần xét tất cả trường hợp một cách cần thận.

1. Trường hợp $s$ là số

Cần $n$ không chia hết cho cả $a$ và $b$ ( $1 \le a < b \le 10^9$ ):

Trường hợp tổng quát: Chọn $a = n + 1$ và $b = n + 2$ . Khi $n < n + 1 < n + 2$ , phép chia lấy dư $n \bmod a = n \neq 0$ và $n \bmod b = n \neq 0$ .
Trường hợp biên:
- $n = 1$ : Chọn $a = 2, b = 3$ ( $1$ không chia hết cho $2$ và $3$ ).
- $n = 10^9$ : Không thể chọn $n+1$ vì vượt giới hạn. Chọn $a = 10^9 - 2$ và $b = 10^9 - 1$ (số dư lần lượt là $2$ và $1$ ).
- $n = 10^9 - 1$ : Chọn $a = 10^9 - 2$ và $b = 10^9$ (số dư lần lượt là $1$ và $10^9 - 1$ ).

2. Trường hợp $s =$ `"fizz"`

Cần $n$ chia hết cho $a$ nhưng không chia hết cho $b$ :

Trường hợp tổng quát ( $n < 10^9$ ): Chọn $a = n$ và $b = n + 1$ . Ta có $n \bmod n = 0$ và $n \bmod{(n+1)} = n \neq 0$ .
Trường hợp biên ( $n = 10^9$ ): Chọn $a = 2, b = 3$ (vì $10^9$ chia hết cho $2$ nhưng không chia hết cho $3$ ).

3. Trường hợp $s =$ `"buzz"`

Cần $n$ chia hết cho $b$ nhưng không chia hết cho $a$ (với $a < b$ ):

Nếu $n \le 2$ : Không tồn tại đáp án, in -1 -1.
- Điều kiện để $n$ chia hết cho $b$ với $b > a \ge 1$ đòi hỏi $b \ge 2$ .
- Với $n = 1$ , không có ước nào $\ge 2$ .
- Với $n = 2$ , chọn $b = 2 \implies a = 1$ , nhưng $2$ lại chia hết cho $1$ nên kết quả bị biến thành "fizzbuzz".
Nếu $n > 2$ : Chọn $b = n$ và $a = n - 1$ . Ta có $n \bmod n = 0$ , còn $n \bmod{(n-1)} = 1 \neq 0$ (do $n \ge 3$ ).

4. Trường hợp $s =$ `"fizzbuzz"`

Cần $n$ chia hết cho cả $a$ và $b$ với $1 \le a < b$ :

Nếu $n = 1$ : Không tồn tại cặp $(a, b)$ vì $1$ chỉ có duy nhất ước là $1$ , không thỏa mãn $a < b$ . In -1 -1.
Nếu $n \ge 2$ : Chọn hai ước $a = 1$ và $b = n$ . Cả $1$ và $n$ đều chia hết $n$ , đồng thời đảm bảo $1 < n \le 10^9$ .

Code

C++

1
void solve() {
2
  int n;
3
  string s;
4
  cin >> n >> s;
5
  if (s[0] != 'f' && s[0] != 'b') {  // s is number
6
    if (n == 1)
7
      cout << 2 << ' ' << 3 << '\n';
8
    else if (n == int(1e9))
9
      cout << int(1e9) - 2 << ' ' << int(1e9) - 1 << '\n';
10
    else if (n == int(1e9 - 1)) {
11
      cout << int(1e9) - 2 << ' ' << int(1e9) << '\n';
12
    } else {
13
      cout << n + 1 << ' ' << n + 2 << '\n';
14
    }
15
  } else {
16
    if (s == "fizz") {
17
      if (n == (int)1e9)
18
        cout << 2 << ' ' << 3 << '\n';
19
      else
20
        cout << n << ' ' << n + 1 << '\n';
21
    } else if (s == "buzz") {
22
      if (n <= 2)
23
        cout << -1 << ' ' << -1 << '\n';
24
      else
25
        cout << n - 1 << ' ' << n << '\n';
26
    } else {
27
      if (n == 1) {
28
        cout << -1 << ' ' << -1 << '\n';
29
      } else {
30
        cout << 1 << ' ' << n << '\n';
31
      }
32
    }
33
  }
34
}

C: Classroom Carnival Chaos

Đề bài

Có $n$ lớp học, mỗi lớp có $m$ học sinh. Đếm số cách xếp $n \times m$ học sinh này vào lưới ô vuông $n \times m$ sao cho không có hai học sinh nào cùng lớp đứng cùng cột, modulo $10^9+7.$ Giải $T$ test.

Giới hạn: $1\le T \le10^5$ , $1 \le n, m \le 10^7$ .

Lời giải

Ta cần đếm số cách xếp mà mỗi cột có đúng một học sinh của mỗi lớp. Ta đếm theo hai bước:

Chọn cột cho từng học sinh. Mỗi lớp có $m$ học sinh và có $m$ cột, mỗi cột nhận đúng một học sinh của lớp đó. Như vậy mỗi lớp phân bổ học sinh vào các cột bằng một hoán vị, có $m!$ cách. Với $n$ lớp độc lập, ta có $(m!)^n$ cách.
Xếp học sinh trong cột. Sau bước 1, mỗi cột có đúng $n$ học sinh, và họ được xếp vào $n$ ô của cột đó theo $n!$ cách. Với $m$ cột độc lập, ta có $(n!)^m$ cách.

Hai bước trên độc lập nên theo quy tắc nhân, đáp án là $(m!)^{n}\cdot(n!)^{m}\pmod{10^9+7}.$

Độ phức tạp. Tính $n!$ và $m!$ bằng một vòng lặp trong $O(\max(n,m))$ , sau đó với mỗi test dùng lũy thừa nhanh trong $O(\log n+\log m)$ .

D: Distinguished Permutation

Đề bài

Cho hoán vị độ dài $n$ . Gọi $F(P)$ là số đoạn con của hoán vị $P$ mà cũng là một hoán vị. Một hoán vị $P$ là đặc biệt nếu $F(P)$ của nó là lớn nhất trong toàn bộ các hoán vị cùng độ dài với nó.

Cho hai số tự nhiên $n$ và $k$ . Tìm hoán vị đặc biệt có thứ tự thứ $k$ trong tập các hoán vị đặc biệt độ dài $n$ sắp xếp theo thứ tự từ điển.

Giới hạn: $1 \le n \le 10^5,1 \le k \le 10^{18}$ . $k$ không vượt quá số hoán vị đặc biệt có độ dài $n$ .

Lời giải

Để đơn giản ta có thể coi thứ tự từ điển tính từ $0$ , khi này ta cần tìm hoán vị đặc biệt có thứ tự từ điển $k-1$ .

Ta có nhận xét khá hiển nhiên sau: Một hoán vị $P$ có $F(P)$ đạt giá trị cực đại là $n$ khi và chỉ khi với mọi $L \in [1, n]$ , tập hợp $\{1, 2, \dots, L\}$ tạo thành một đoạn con liên tiếp.

Từ đó ta có cách để xây dựng tất cả các hoán vị đặc biệt như sau: bắt đầu từ phần tử $1$ , sau đó lần lượt thêm các số $i$ từ $2$ đến $n$ vào đầu hoặc cuối của hoán vị hiện tại. Từ đó ta suy ra được số hoán vị đặc biệt độ dài $n$ là $2^{n-1}$ . Hơn nữa, việc thêm số $i$ vào đầu hoặc cuối phụ thuộc vào bit thứ $i-2$ trong biểu diễn nhị phân của $k-1$ . Nếu bit này bằng 0 thì ta sẽ thêm vào cuối, nếu là 1 thì sẽ thêm vào đầu.

Chứng minh

Gọi $S_n$ là tập các hoán vị đặc biệt độ dài $n$ , đã sắp xếp theo thứ tự từ điển. Ta chứng minh mệnh đề sau:

Với mọi $n\ge1$ và $0\le r<2^{n-1}$ , hoán vị đặc biệt có thứ tự $r$ (tính từ $0$ ) là hoán vị nhận được bằng cách bắt đầu từ $[1]$ rồi thêm lần lượt $i=2,\dots,n$ , trong đó $i$ được thêm vào đầu nếu bit thứ $i-2$ của $r$ bằng $1$ , và vào cuối nếu bằng $0$ .

Với $r=k-1$ ta có điều phải chứng minh.

Bước cơ sở. Với $n=1$ , $S_1={[1]}$ và $r=0$ , mệnh đề đúng.

Bước quy nạp. Giả sử mệnh đề đúng với $n-1$ . Gọi $T_0<T_1<\dots<T_{M-1}$ là các hoán vị của $S_{n-1}$ , với $M=2^{n-2}$ . Theo giả thiết quy nạp, $T_j$ được tạo từ các bit của $j$ .

Xét $P\in S_n$ . Bước hiện tại thêm $n$ vào đầu hoặc vào cuối, và trước đó ta có một hoán vị $T\in S_{n-1}$ . Vậy $P$ có dạng $[T,n]$ hoặc $[n,T]$ . Hai dạng này cho các hoán vị khác nhau, và $T$ được xác định bằng cách xóa $n$ . Do đó $S_n$ gồm đúng $2M$ hoán vị: mỗi $T_j$ cho một hoán vị $[T_j,n]$ và một hoán vị $[n,T_j]$ .

Ta sắp xếp các hoán vị này:

Mọi hoán vị có dạng $[n,T]$ lớn hơn mọi hoán vị có dạng $[T,n]$ . Hoán vị đầu bắt đầu bằng $n$ , còn hoán vị sau bắt đầu bằng một số nhỏ hơn $n$ .
Trong cùng một nhóm, thứ tự giống thứ tự của $T_j$ .

Vậy thứ tự trong $S_n$ là:

[T_0,n],\ [T_1,n],\ \dots,\ [T_{M-1},n],\ [n,T_0],\ [n,T_1],\ \dots,\ [n,T_{M-1}].

Xét hoán vị có thứ tự $r$ , với $0\le r<2M=2^{n-1}$ :

Nếu $r<M$ , đó là $[T_{r},n]$ . Khi này bit thứ $n-2$ của $r$ (có trọng số $2^{n-2}=M$ ) bằng $0$ , và $n$ được thêm vào cuối.
Nếu $r\ge M$ , đó là $[n,T_{r-M}]$ . Khi này bit thứ $n-2$ của $r$ bằng $1$ , và $n$ được thêm vào đầu. Phần $T_{r-M}$ cũng chính là phần tạo từ các bit thấp của $r$ .

Trong cả hai trường hợp, $T_j$ với $j=r\bmod M$ (các bit $0,\dots,n-3$ của $r$ ) được tạo theo giả thiết quy nạp, nên các số $i$ từ $2,\dots,n-1$ được thêm đúng theo bit thứ $i-2$ của $r$ và số $n$ được thêm theo bit thứ $n-2$ của $r$ . Ta kết luận mệnh đề đúng với $n$ . $\blacksquare$

Độ phức tạp của thuật toán là $\mathcal{O}(n)$ .

Code

C++

1
#include <bits/extc++.h>
2

3
using namespace std;
4

5
typedef long long ll;
6

7
void solve() {
8
  int n;
9
  ll k;
10
  cin >> n >> k;
11
  --k;
12
  deque<int> p;
13
  p.push_back(1);
14

15
  auto get_bit = [&](ll x, int pos) { return (x >> pos) & 1; };
16

17
  int pivot = min(n, 61);
18

19
  for (int i = 2; i <= pivot; ++i) {
20
    if (get_bit(k, i - 2) == 1) p.push_front(i);
21
    else p.push_back(i);
22
  }
23
  for (int i = pivot + 1; i <= n; ++i) p.push_back(i);
24
  for (auto i : p) cout << i << ' ';
25
  cout << '\n';
26
}
27

28
int main() {
29
  cin.tie(0)->sync_with_stdio(0);
30
  cin.exceptions(cin.failbit);
31
  int tc = 1;
32
  cin >> tc;
33
  for (int i = 1; i <= tc; ++i) {
34
    solve();
35
  }
36
}

L: Locomotive Lane Logistics

Đề bài

Cho một đường ray có độ dài $s$ và $q$ truy vấn. Mỗi truy vấn có 1 trong 2 dạng:

+ l v: thêm 1 tàu có độ dài $l$ và vận tốc $v$ vào lịch trình.
- l v: xoá 1 tàu có độ dài $l$ và vận tốc $v$ khỏi lịch trình, đảm bảo trong lịch trình hiện tại có ít nhất 1 tàu như vậy.

Mỗi con tàu có phần mui và phần đuôi, khoảng cách giữa mui và đuôi của tàu chính là độ dài $l$ của nó. Con tàu sẽ xuất phát với mui chạm vạch xuất phát, đi đều liên tục với vận tốc $v$ về phía vạch kết thúc và chỉ ra khỏi đường ray khi đuôi rời khỏi vạch kết thúc. Mỗi con tàu ta có thể chọn cho nó thời điểm xuất phát là số thực bất kì.

Sau mỗi truy vấn, tính tổng thời gian ít nhất để đưa toàn bộ tàu trong danh sách ra khỏi đường ray mà không xảy ra tai nạn. Tai nạn có thể xảy ra giữa 2 tàu ở thời điểm mui của tàu đi sau đâm vào đuôi của tàu đi trước, vận tốc của tàu đi sau lớn hơn tàu đi trước và tàu đi trước chưa ra khỏi đường ray. In ra đáp án tối ưu (luôn có dạng là số hữu tỉ) theo modulo $998244353$ .

Lời giải

Trước tiên ta có thể rút ra 2 nhận xét tham lam đầu tiên về đáp án tối ưu:

Nếu 2 tàu có cùng vận tốc, thì chúng có thể đi nối đuôi nhau như là 1 tàu (vẫn thoả mãn điều kiện không xảy ra tai nạn), nên ta có thể giả sử vận tốc của tất cả các tàu đều khác nhau.
Để tối thiểu hoá tổng thời gian, các tàu cần di chuyển nối tiếp nhau khít nhất có thể, tàu chậm sẽ đi trước, rồi sau một khoảng thời gian tối ưu ta sẽ cho tàu nhanh hơn xuất phát và đuổi theo sau. Một cách để chứng minh nhận xét này, là tàu đi sau đã tận dụng triệt để khoảng thời gian tàu đi trước chiếm dụng đường ray để tranh thủ di chuyển được một khoảng cách nhất định.

Tiếp theo đó, bằng việc ngồi nháp toán và chứng minh công thức ta rút ra nhận xét quan trọng nhất của bài toán:

Giả sử có 2 tàu $T_1 = (l_1, v_1)$ và $T_2 = (l_2, v_2)$ với $v_1 < v_2$ . Ta cho $T_1$ đi trước, $T_2$ đi sau và $T_2$ sẽ có xu hướng đuổi kịp. Để tối ưu thời gian, ta căn chỉnh sao cho ngay thời điểm đuôi $T_1$ rời khỏi đường ray thì mui của $T_2$ cũng vừa chạm vạch kết thúc. Theo đó ta có giãn cách thời gian tối ưu giữa 2 tàu:

\frac{s + l_1}{v_1} - \frac{s}{v_2} = \frac{s}{v_1} - \frac{s}{v_2} + \frac{l_1}{v_1}

Áp dụng nhận xét trên cho $n$ tàu, thì tổng thời gian tối ưu là:

\frac{s}{v_1} - \frac{s}{v_n} + \sum_{i=1}^{n-1} \frac{l_i}{v_i} + \frac{s + l_n}{v_n} = \frac{s}{v_1} + \sum_{i=1}^n \frac{l_i}{v_i}

Chứng minh

Gọi $T_1$ là tàu chậm nhất. Với các tàu xuất phát trước $T_1$ , ta có đuôi của mỗi tàu phải rời vạch xuất phát trước khi mui tàu kế tiếp chạm vạch (nếu không hai tàu chồng lên nhau ngay tại vạch), nên tàu $i \neq 1$ chiếm vạch xuất phát ít nhất $\frac{l_i}{v_i}$ , và $T_1$ xuất phát không sớm hơn tổng các $\frac{l_i}{v_i}$ đó. Bản thân $T_1$ cần thêm $\frac{s + l_1}{v_1}$ để ra khỏi đường ray. Cộng lại, tổng thời gian $\ge \frac{s}{v_1} + \sum_{i=1}^n \frac{l_i}{v_i}$ với mọi cách sắp xếp.

Các tàu xuất phát sau $T_1$ đều nhanh hơn hoặc bằng nó, mui của chúng luôn nằm sau đuôi $T_1$ , nên chúng chỉ băng qua vạch kết thúc sau khi $T_1$ đã ra hẳn; tại vạch kết thúc mỗi lúc chỉ có một tàu băng qua và tàu $i$ chiếm vạch đúng $\frac{l_i}{v_i}$ . Vậy nên ta thu được một cách dựng đạt được cận dưới của đáp án, nên công thức của nhận xét là tối ưu.

Để ý rằng chặn dưới không phụ thuộc thứ tự của các tàu khác ngoài $T_1$ , nên qua chứng minh ở trên ta thấy rằng thật ra cho tàu nhanh đi trước cũng có thể đạt được đúng giá trị này. Nhận xét "tàu chậm đi trước" chỉ là một cách dựng, không phải điều bắt buộc.

Tổng kết lại, thuật toán cuối cùng của bài chỉ cần duy trì 2 giá trị sau qua các thao tác thêm và xoá tàu khỏi danh sách:

Vận tốc $v_1$ của tàu chậm nhất trong danh sách hiện tại, có thể dùng multiset hoặc priority_queue.
Tổng $\frac{l_i}{v_i}$ của các tàu đang có trong danh sách hiện tại.

Độ phức tạp cho mỗi truy vấn là $\mathcal{O}(\log q)$ .

Code

C++

1
#include <bits/extc++.h>
2

3
using namespace std;
4

5
typedef long long ll;
6

7
const int mod = 998244353;
8

9
int binpow(int a, int b) {
10
  int res = 1;
11
  while (b) {
12
    if (b & 1) res = (ll)res * a % mod;
13
    a = (ll)a * a % mod;
14
    b >>= 1;
15
  }
16
  return res;
17
}
18

19
int inv(int a) { return binpow(a, mod - 2); }
20

21
void solve() {
22
  int s, q;
23
  cin >> s >> q;
24
  multiset<pair<int, int>> ms;
25
  int lv_sum = 0;
26
  while (q--) {
27
    char ch;
28
    int l, v;
29
    cin >> ch >> l >> v;
30
    if (ch == '+') {
31
      ms.insert({v, l});
32
      lv_sum += ll(l) * inv(v) % mod;
33
      lv_sum %= mod;
34
    } else {
35
      auto it = ms.find({v, l});
36
      ms.erase(it);
37
      lv_sum -= ll(l) * inv(v) % mod;
38
      lv_sum = (lv_sum + mod) % mod;
39
    }
40
    if (sz(ms) == 0) {
41
      cout << "0\n";
42
    } else {
43
      auto [v1, l1] = *ms.begin();
44
      int ans = (ll(s) * inv(v1) + lv_sum) % mod;
45
      ans = (ans + mod) % mod;
46
      cout << ans << '\n';
47
    }
48
  }
49
}
50

51
int main() {
52
  cin.tie(0)->sync_with_stdio(0);
53
  cin.exceptions(cin.failbit);
54
  int tc = 1;
55
  // cin >> tc;
56
  for (int i = 1; i <= tc; ++i) {
57
    solve();
58
  }
59
}

ICPC Regional Hanoi 2024 Editorial - X

G: Gid-osh

Đề bài

Lời giải

F: FizzBuzz

Đề bài

Lời giải

1. Trường hợp $s$ là số

2. Trường hợp $s =$ `"fizz"`

3. Trường hợp $s =$ `"buzz"`

4. Trường hợp $s =$ `"fizzbuzz"`

Code

C: Classroom Carnival Chaos

Đề bài

Lời giải

D: Distinguished Permutation

Đề bài

Lời giải

Code

L: Locomotive Lane Logistics

Đề bài

Lời giải

Code

Continue reading

G: Gid-osh

Đề bài

Lời giải

F: FizzBuzz

Đề bài

Lời giải

1. Trường hợp sss là số

2. Trường hợp s=s =s= "fizz"

3. Trường hợp s=s =s= "buzz"

4. Trường hợp s=s =s= "fizzbuzz"

Code

C: Classroom Carnival Chaos

Đề bài

Lời giải

D: Distinguished Permutation

Đề bài

Lời giải

Code

L: Locomotive Lane Logistics

Đề bài

Lời giải

Code

Continue reading

Related reading

1. Trường hợp $s$ là số

2. Trường hợp $s =$ `"fizz"`

3. Trường hợp $s =$ `"buzz"`

4. Trường hợp $s =$ `"fizzbuzz"`