\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <20%>}}\)

gọi dp[i][j] là số tiền tối đa có thể mà người chơi có thể giành được trong trò chơi với i vòng và j đối thủ ở đầu, chia cho 100000.

dp[i][j] = min(dp[i-1][j-k]+k/j), với k \(\in\) \([1;j]\)

\(\color{orange}{\text{Hint 2 <50%>}}\)

• Để đạt được 50%, ta cần nhìn nhận một vài vấn đề.

Đặt \(a_{1}\), \(a_{2}\), ..., \(a_{k}\) là số người bị out trong mỗi vòng. Không khó để chứng minh rằng \(a_{1}\) \(\geq\) \(a_{2}\) \(\geq\) ... \(\geq\) \(a_{k}\).

Ngoài ra \(a_{1}\) + \(a_{2}\) + ... + \(a_{k}\) = n nên suy ra ta có được \(a_{i}\) \(\leq\) n/i, vì nếu không, ta sẽ có \(a_{1}\) + \(a_{2}\) + ... + \(a_{1}\)> n.

Do đó dp[i][j]=min(dp[i-1][j-k]+k/j), vì k \(\in\) \([1;n/i]\) nên tổng độ phức tạp bây giờ là \(n^2\)log(k)

\(\color{orange}{\text{Hint 3 <100%>}}\)

• Để có được 100% bạn phải thấy rằng dp[i][j+1]-dp[i][j]<=dp[i][j]-dp[i][j-1] có nghĩa là chúng ta có thể sử dụng thuật toán Aliens trick

Aliens trick: link or link

\(\color{orange}{\text{Funny Hint}}\)

• Ta có thể loại bỏ yếu tố logarit.

dp[i][j]=min(j×dp[i-1][k]-k)/j+1, do đó, đây là một vấn đề kinh điển trong việc tìm ra hàm chặn y tối thiểu của hàm dp[i-1][k]×x-k, còn gọi là convex hull trick