Hướng dẫn cho SGAME10

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: vinhntndu

\(\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


Bình luận


  • -1
    vinhntndu    8:15 p.m. 4 Tháng 8, 2020

    có ai biết hay nghe về Aliens trick chưa 🙂


    • 0
      TCA_Khoa    8:42 p.m. 4 Tháng 8, 2020

      chưa


      • -1
        vinhntndu    8:44 p.m. 4 Tháng 8, 2020

        nghi vấn bài này vài năm sau có người làm 🙂


        • -1
          THOANGLQDT    8:53 p.m. 30 Tháng 10, 2020

          anh vinhntndu cho em toàn bộ code để em tham khảo được ko

    1 bình luận nữa