Editorial for Bedao Mini Contest 08 - TRIANGLE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask 1: ~t \le 10, k \le 8~

Nhận xét: mỗi giá trị xuất hiện trong dãy không quá 2 lần, vì nếu có 3 giá trị giống nhau thì luôn dựng được 1 tam giác đều.

  • Nếu ~n > 2k~ thì theo định lý dirichlet luôn có ~1~ giá trị xuất hiện trong dãy ~\ge~ 3 lần ~\Rightarrow~ kết quả là no.

  • Vì có tối đa 8 giá trị phân biệt và chúng xuất hiện trong dãy ko quá 2 lần, ta dễ dàng duyệt backtrack với độ phức tạp là ~\mathcal{O}(3^k)~ rồi duyệt qua mọi bộ 3 trong dãy vừa sinh để kiểm tra. Thuật toán có độ phức tạp là ~\mathcal{O}(t \times 3^k \times k^3)~.

Subtask 2:

Nhận xét : không mất tính tổng quát, giả sử bộ 3 ta đang xét là ~(a, b, c)~ và ~a \le b \le c~. Bộ 3 này không tạo thành các cạnh tam giác khi và chỉ khi ~a+b \le c~.

  • Xét dãy ~s[1..n]~ thoả mãn yêu cầu đề bài và có ~s[i] \le s[i+1]~, ta xây dựng ~s[1..n]~ theo thuật toán tham lam để số lớn nhất trong dãy là ~s[n]~ có giá trị tối thiểu:

    • Nếu ~i > 2~ và ~s[1..i-1]~ là các số đã biết thì ~s[i]~ tối ưu để thêm vào dãy mà vẫn không thỏa mãn bất đẳng thức tam giác là ~s[i] = s[i-1]+s[i-2]~.
    • Dễ thấy nếu ~i \le 2~ thì tốt nhất là đặt ~s[i] = 1~. Nói cách khác, dãy ~s[1..n]~ tối ưu gồm sẽ ~n~ phần tử đầu của dãy fibonacci, ta chỉ cần so sánh số thứ ~n~ trong dãy fibonacci với ~k~ để biết kết quả.
  • Dễ thấy ~s[i+2] > 2s[i]~ mà ~s[n] \le k \le 10^{18}~ nên một dãy thỏa mãn có nhiều nhất ~2\log_2(10^{18})~ phần tử. Vì vậy thuật toán cuối cùng có độ phức tạp là ~\mathcal{O}(t \times \log_2(10^{18}))~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.