Một số bài toán thú vị tuần 1 ( 1/5 - 7/5/2017)

Giới thiệu chuyên mục :
 Đây là chuyên mục ghi lại một vài toán tôi cho rằng thú vị tôi gặp trong 1 tuần và cách giải và 1 số hướng đi của nó. Hy vọng các bạn thích nó.

Bài toán 1: Permutation Happiness
Tóm tắt đề : Cho n người với mỗi chỉ số phân biệt từ 1 --> n. Họ xếp thành 1 hàng. Người thứ i được cho là hạnh phúc nếu có ít nhất 1 trong 2 người đứng cạnh anh ta có chỉ số lớn hơn anh ta.
Cho n (n <= 3000) và k <= n. Đếm số cách để xếp để tồn tại ít nhất k người hạnh phúc.



 Mở đầu:
 Ta bắt đầu với 1 bài toán: cho n số , đếm số hoán vị.
Bài toán này ai cũng biết rằng kết quả cho n!. Tuy nhiên nhìn về khía cạnh quy hoạch động một chút. Gọi dp[i] là kết quả cho i số.
Khi ấy để tính kết quả i+1 ta để ý rằng mỗi vị trí hoán vị của i có i+1 vị trí để đặt số i+1.
Khi đó ta có dp[i+1] = dp[i] * (i+1).
Giải:
Bài toán trên ta sử dụng tư tưởng tương tự.
 Gọi dp[i][j] là số cách để tạo ra hoán vị với độ dài n với chính xác k người không hạnh phúc.
Với tư tưởng như trên, ta giả định tính toán được kết quả với n-1 người,
Bây giờ, đặt người thứ n ở đâu không quan trọng. Chỉ có 2 kết quả xảy ra,
+ Số người không hạnh phúc giữ nguyên ( Khi đó ta sẽ đặt người n vào bên trái hoặc phải người không hạnh phúc)
+ Và số người không hạnh phúc + 1.
Do đó ta có công thức quy hoạch động sau:
dp[n][k] = dp[n-1][k] * 2 * k + dp[n-1][k-1] * (n - 2*(k-1) ) ;
Độ phức tạp thuật toán là O(n*k) .
Bài toán 2: Maximal GCD
Tóm tắt đề: Cho n,k (n , k <= 10^10) . Tìm 1 cách để tạo ra k số phân biệt sao cho tổng của chúng = k và ước chung lớn nhất của chúng là lớn nhất có thể.
Giải:
-  Bây giờ bắt đầu với bài toán nhỏ hơn, cho n hãy kiểm tra xem n có thể viết thành tổng của k số phân biệt hay không.
+ với n < k*(k+1)/2 thì sẽ không tồn tại kết quả nào hết (vì 1 + 2+ ... + k là kết quả nhỏ nhất có thể)
+ n>= k*(k+1)/2 ta sẽ cho k-1 số là 1 --> k-1 và số còn lại là n - k(k-1)/2 sẽ thỏa mãn đề bài.
- Gọi GCD (a1,a2,...ak) = x .
Ta có a1 + a2 + ... + ak = x * (a1' + a2' + ... +ak')
Ta thấy chỉ cần a1' + a2' + ... + ak' >= k(k+1)/2 thì sẽ tìm được kết quả thỏa mãn .
Do đó x <= n * 2/ ( k*(k+1))
(với ai' = ai/ x) .
Việc cần làm bây giờ là tìm x bằng cách xét tất cả các ước của n. Ta kiểm tra việc này trong O(sqrt(n)). ( n = a.b thì sẽ có ít nhất 1 số <= sqrt(n) ) .
Bây giờ ta có code:

Một bài toán tương tự : thay vỉ tổng của k số thì ta thay bằng : a1  + a2*2 + ... + ak*k = n.
Bài toán 3: Minimum number of steps
Tóm tắt đề: Cho 1 xâu chỉ gồm 2 chữ cái 'a' và 'b' . Mỗi bước ta sẽ đổi 1 xâu con con liên tiếp 'ab' --> 'bba'. Bài toán đặt ra: Tìm số bước nhỏ nhất biến đổi xâu thành 1 xâu không thể biến đổi nữa.
Giải:
Ta nhận ra rằng xâu không thể biến đổi là xâu có dạnh bbb...baaa...a
Ta có cảm nhận rằng thao tác 'ab' --> 'bba' thực ra là 1 thao tác đẩy chữ cái b về trước chữ cái a. Do đó ta có thể thấy rằng số bước là cố định.
- Bây giờ giải quyết bài toán đơn giản hơn : 'ab' --'ba'.
+ Bây giờ để đưa b về vị trí đúng của nó, ta phải đưa nó đi chính xác bao nhiêu bước ??
Giả sử các chữ cái b trước đó đã về đúng vị trí, thì xâu sẽ có dạng  bbbb..baaa..ab ....
Bây giờ số bước chính là số chữ cái a liên tiếp. (mà ở đây chính là số chữ cái a năm trước b) .
Bây giờ ta đã giải quyết bài toán phụ, bài toán chính xin nhường bạn đọc,
Dưới đây là code của bài toán:

Tôi xin kết thúc bài viết số 1 tại đây, hi vọng các bạn thấy thông tin này hữu ích. Hãy ấn like để động viên mình viết tiếp nhé =))