"ta nên chọn một đoạn liên tiếp K thằng để phát quà (và hiển nhiên, mỗi tập nên có ít nhất 1 thằng được phát)" câu này tại sao vậy nhỉ :-? Tại sao lại nên chọn một đoạn liên tiếp K thằng :-?

Nhận xét 1 của em, anh ko hiểu trong kho còn >= K món đồ tức là sao

Trải nửa đường tròn ra đường thẳng nhé, giả sử ta có vị trí \(1;2;3;4\) có đội cần nhận quà, mỗi lần lấy chỉ có \(2\) quà.

Mình phát cho đội ở vị trí \(1;3\) rồi đến \(2;4\) (đi \(6 + 8 = 14 \) đoạn) sẽ lâu hơn phát cho \(4;3\) rồi \(2;1\) (đi \(8+4 = 12\) đoạn) (do phải quay lại vị trí \(0\) để lấy quà)

Bài này khá đơn giản, cái chính là phải cài khéo không TLE (dữ liệu khá lớn, phải khai báo một mảng tầm \(10^{6}\) biến longint ở subtask \(5\) và \(6\), mình cũng theo hướng đấy nhưng vì chưa được tối ưu như cách này nên chỉ làm được \(2\) subtask đầu)

Tự dưng nghĩ ra cách nữa

- Tạo một biến đếm cho biết số quà đang có

Phát cho đội xa điểm \(0\) nhất 

- Lặp liên tục

 + Nếu còn quà thì tìm đường ngắn nhất đến đội tiếp theo để phát

 + Không còn quà thì tìm đường ngắn nhất về \(0\), sau đó phát cho đội ở xa điểm \(0\) nhất

Cho đến khi hết đội cần phát quà thì về \(0\) (nếu đề bài yêu cầu)

Dùng danh sách vòng tròn (\(Queue\) thì phải) để hỗ trợ việc tìm đội gần nhất

Có vẻ không khả thi lắm vì độ phức tạp khoảng \(O(n^{3})\)

Thường thi Quốc tế thì \(O(n^{2})\) là cùng!

Mà bạn đối phó với test này thế nào đây?

\(n=4; k=2; l=200\)

\(pos = [1; 98; 102; 199]\) (không biết kí hiệu thế này có đúng không)

Thì phát cho \(1; 199\) rồi phát cả vòng tròn thì sẽ ra \(203\)

Thuật toán của bạn ra \(98.2+98.2\)

(do phát từng nửa vòng tròn một)

"ta nên chọn một đoạn liên tiếp K thằng để phát quà (và hiển nhiên, mỗi tập nên có ít nhất 1 thằng được phát)" câu này tại sao vậy nhỉ :-? Tại sao lại nên chọn một đoạn liên tiếp K thằng :-?

Trải nửa đường tròn ra đường thẳng nhé, giả sử ta có vị trí \(1;2;3;4\) có đội cần nhận quà, mỗi lần lấy chỉ có \(2\) quà.

Mình phát cho đội ở vị trí \(1;3\) rồi đến \(2;4\) (đi \(6 + 8 = 14 \) đoạn) sẽ lâu hơn phát cho \(4;3\) rồi \(2;1\) (đi \(8+4 = 12\) đoạn) (do phải quay lại vị trí \(0\) để lấy quà)

Bài này khá đơn giản, cái chính là phải cài khéo không TLE (dữ liệu khá lớn, phải khai báo một mảng tầm \(10^{6}\) biến longint ở subtask \(5\) và \(6\), mình cũng theo hướng đấy nhưng vì chưa được tối ưu như cách này nên chỉ làm được \(2\) subtask đầu)

Tự dưng nghĩ ra cách nữa

- Tạo một biến đếm cho biết số quà đang có

Phát cho đội xa điểm \(0\) nhất 

- Lặp liên tục

 + Nếu còn quà thì tìm đường ngắn nhất đến đội tiếp theo để phát

 + Không còn quà thì tìm đường ngắn nhất về \(0\), sau đó phát cho đội ở xa điểm \(0\) nhất

Cho đến khi hết đội cần phát quà thì về \(0\) (nếu đề bài yêu cầu)

Dùng danh sách vòng tròn (\(Queue\) thì phải) để hỗ trợ việc tìm đội gần nhất

Có vẻ không khả thi lắm vì độ phức tạp khoảng \(O(n^{3})\)

Thường thi Quốc tế thì \(O(n^{2})\) là cùng!

Mà bạn đối phó với test này thế nào đây?

\(n=4; k=2; l=200\)

\(pos = [1; 98; 102; 199]\) (không biết kí hiệu thế này có đúng không)

Thì phát cho \(1; 199\) rồi phát cả vòng tròn thì sẽ ra \(203\)

Thuật toán của bạn ra \(98.2+98.2\)

(do phát từng nửa vòng tròn một)

Nhận xét 1 của em, anh ko hiểu trong kho còn >= K món đồ tức là sao

Đến tận hôm nay vừa mới ngồi làm đề ngày 1 nên giờ mới chém gió đc :))

Cái nhận xét 2 của em thì đúng rồi, và theo anh thấy đây là mấu chốt để làm bài này, nhưng nhận xét 1 thì ko rõ tại em phát biểu ngu hay tại em nghĩ sai thật :)). Ví dụ: K = 2, sau khi chia thành 2 tập, 1 bên có {1, 2, 3} và 1 bên có {4, 5} thì rõ ràng là nếu em đi tập 1 trước thì các lần phát là {1} và {2, 3}, chứ ko thể phát đủ K cái được.

Đoạn sau của em thì đọc ko hiểu gì lắm, nhất là tại sao chia thành 2 tập theo "tùy theo đi từ 0 theo hướng nào đến nó gần hơn" ?

Đoạn sau anh làm như này:

• Đặt f(i) = chi phí nhỏ nhất để phát quà cho thằng 1 --> i (và luôn đi theo chiều 0 --> 1 --> x). f(i) = f(i-K) + 2*p(i)
• Đặt g(i) = chi phí nhỏ nhất để phát quà cho thằng i --> N (và luôn đi theo chiều L --> L-1 --> x). g(i) = g(i+K) + 2*(L - p(i))

Sau khi có mảng f và g, cả 2 trường hợp có 1 lần đi hết và không đi hết vòng tròn đều rất đơn giản:

• Không có lần nào đi hết vòng tròn --> min( f(i) + g(i+1) )
• Nếu có đi hết vòng tròn 1 lần --> min( f(i) + g(i+K) + L )

Bài 2 ngồi nháp 1 hồi chỉ mò ra đc cách dùng tối đa 8 lần cân --> 55.55 điểm :'( theo như thảo luận trên Codeforces thì nếu tối đa dùng 7 lần cân --> ~ 70 điểm và có vẻ là dùng 6 lần --> 100 điểm :v ko biết có bạn nào đã làm thử chưa :))

Bài 3 thì làm đc mỗi 2 subtask đầu nên xin phép ko đả động đến =))

Đến tận hôm nay vừa mới ngồi làm đề ngày 1 nên giờ mới chém gió đc :))

Cái nhận xét 2 của em thì đúng rồi, và theo anh thấy đây là mấu chốt để làm bài này, nhưng nhận xét 1 thì ko rõ tại em phát biểu ngu hay tại em nghĩ sai thật :)). Ví dụ: K = 2, sau khi chia thành 2 tập, 1 bên có {1, 2, 3} và 1 bên có {4, 5} thì rõ ràng là nếu em đi tập 1 trước thì các lần phát là {1} và {2, 3}, chứ ko thể phát đủ K cái được.

Đoạn sau của em thì đọc ko hiểu gì lắm, nhất là tại sao chia thành 2 tập theo "tùy theo đi từ 0 theo hướng nào đến nó gần hơn" ?

Đoạn sau anh làm như này:

• Đặt f(i) = chi phí nhỏ nhất để phát quà cho thằng 1 --> i (và luôn đi theo chiều 0 --> 1 --> x). f(i) = f(i-K) + 2*p(i)
• Đặt g(i) = chi phí nhỏ nhất để phát quà cho thằng i --> N (và luôn đi theo chiều L --> L-1 --> x). g(i) = g(i+K) + 2*(L - p(i))

Sau khi có mảng f và g, cả 2 trường hợp có 1 lần đi hết và không đi hết vòng tròn đều rất đơn giản:

• Không có lần nào đi hết vòng tròn --> min( f(i) + g(i+1) )
• Nếu có đi hết vòng tròn 1 lần --> min( f(i) + g(i+K) + L )

Bài 2 ngồi nháp 1 hồi chỉ mò ra đc cách dùng tối đa 8 lần cân --> 55.55 điểm :'( theo như thảo luận trên Codeforces thì nếu tối đa dùng 7 lần cân --> ~ 70 điểm và có vẻ là dùng 6 lần --> 100 điểm :v ko biết có bạn nào đã làm thử chưa :))

Bài 3 thì làm đc mỗi 2 subtask đầu nên xin phép ko đả động đến =))

Đến tận hôm nay vừa mới ngồi làm đề ngày 1 nên giờ mới chém gió đc :))

Cái nhận xét 2 của em thì đúng rồi, và theo anh thấy đây là mấu chốt để làm bài này, nhưng nhận xét 1 thì ko rõ tại em phát biểu ngu hay tại em nghĩ sai thật :)). Ví dụ: K = 2, sau khi chia thành 2 tập, 1 bên có {1, 2, 3} và 1 bên có {4, 5} thì rõ ràng là nếu em đi tập 1 trước thì các lần phát là {1} và {2, 3}, chứ ko thể phát đủ K cái được.

Đoạn sau của em thì đọc ko hiểu gì lắm, nhất là tại sao chia thành 2 tập theo "tùy theo đi từ 0 theo hướng nào đến nó gần hơn" ?

Đoạn sau anh làm như này:

• Đặt f(i) = chi phí nhỏ nhất để phát quà cho thằng 1 --> i (và luôn đi theo chiều 0 --> 1 --> x). f(i) = f(i-K) + 2*p(i)
• Đặt g(i) = chi phí nhỏ nhất để phát quà cho thằng i --> N (và luôn đi theo chiều L --> L-1 --> x). g(i) = g(i+K) + 2*(L - p(i))

Sau khi có mảng f và g, cả 2 trường hợp có 1 lần đi hết và không đi hết vòng tròn đều rất đơn giản:

• Không có lần nào đi hết vòng tròn --> min( f(i) + g(i+1) )
• Nếu có đi hết vòng tròn 1 lần --> min( f(i) + g(i+K) + L )

Bài 2 ngồi nháp 1 hồi chỉ mò ra đc cách dùng tối đa 8 lần cân --> 55.55 điểm :'( theo như thảo luận trên Codeforces thì nếu tối đa dùng 7 lần cân --> ~ 70 điểm và có vẻ là dùng 6 lần --> 100 điểm :v ko biết có bạn nào đã làm thử chưa :))

Bài 3 thì làm đc mỗi 2 subtask đầu nên xin phép ko đả động đến =))

Bài 3 em cũng chỉ nghĩ được 2 sub đầu làm kiểu tạo cái đồ thị kiểu 2 phía mà có thêm một đỉnh nguồn và một đỉnh thu. Một phía là gồm các thí sinh và phía còn lại là các bài tập. Thí sinh thứ i em sẽ tạo canh nối tới các bài tập có K thuộc đoạn \([A_i, B_i] \) với trọng số mỗi cạnh là 1. Đỉnh nguồn S sẽ nối tới các thí sinh với trọng số là 1 và đỉnh thu T sẽ nối tới các bài tập, nối tới bài tập thứ i thì cạnh sẽ có trọng số là \(K_i\) . Sau đó tìm luồng cực đại trên đồ thị này. Mà nếu theo hướng này thì 2 sub sau em thấy kiểu "bất khả thi" thế nào ấy. Nên chắc hóng cao nhân vào giải đáp. *hóng*

Bài 1

Mình nhận xét là nếu đoạn cần đi nằm giữa tức là không chạm đến vị trí 0 hoặc k- 1 thì sẽ có độ dài là k. Từ đấy ta chỉ cần for 2 vòng for(i, 0, k - 1) for(j = i, j < n - 1, j += i) trong đó i là vị trí bên phải đoạn đầu tiên tức là mình sẽ đi từ 0 đến i còn j là vị trí bên phải từng đoạn tiếp theo.

Bài 3

- subtask 1 có thể làm bằng luồng

- subtask 2 sort lại các giá trị của mỗi người theo a[i] và mảng k tại mỗi k[i], add thêm những người có a[i] <= k[i] <= b[i] vào một multiple_set các giá trị b[i](trong C++), thao tác thêm dùng con trỏ tịnh tiến và xử lý với set nên mất nlogn rồi việc đẩy ra k[i] thằng ta sẽ đẩy từ các giá trị có b[i] nhỏ cho đến b[i] lớn ra ngoài mất Slogn để thực hiện.

- subtask 3 là một subtask khá khó (mặc dù thuật toán không khó đối với những bạn giỏi về ctdl nhưng đòi hỏi việc cài cực kỳ cẩn thận bởi vì có rất nhiều trường hợp khi phân tich). Mình thực hiện thao tác sort tương tự subtask 2 nhưng đến đây chúng ta gặp một vấn đề là số lượng các phần tử quá lớn không thể đẩy vào set được, vì vậy ta phải tính trực tiếp ở mỗi k[i] có còn k[i] người để phủ điểm k[i] không, tại bước thứ i mình sẽ lưu một giá trị need là số lượng đoạn đi qua k[i] mà cần phải trừ đi vì những thằng trước i đã dùng mất. Khi đến vị trí thứ i dễ dàng tính được số lượng đoạn đi qua i bằng số đoạn u có a[u] <= k[i] - số đoạn v có b[v] < k[i]. Tiếp đó ta tính đến những đoạn đi qua cả k[i] và k[i + 1], cái này có thể tính bằng cách dùng bit2D sử dụng lower bound và upper bound trên các cây bit. Những đoạn mà qua i chứ không qua i + 1 lại được chia thành 2 phần những đoạn chỉ qua i và những đoạn qua cả i - 1. Từ các giá trị trên ta có thể tính được xem là có thể có đủ k[i] đoạn qua k[i] không và cần bao nhiêu đoạn nữa để bù đắp lại khi tính đến i + 1. Thuật toán nlognlogn + qlognlogn

- subtask4, từ subtask 3 là có thể gần đủ để AC rồi nếu cài Bit2D khéo nếu thêm một thao tác nữa là sau khi chèn các vị trí vào các cây bit ta không phải sort lại nhờ đã sắp xếp b[i] trước đó thì thuật toán giảm xuóng còn nlogn + qlognlogn nhưng vì số điểm trên mỗi cây bit trung bình chỉ là logn nên thuật chạy rất nhanh (<1s)

Nhận xét: Bài 3 này là một bài đòi hỏi kỹ thuật tốt và sự cẩn thận (Hạnh bị WA 1test chắc là do chưa xét đủ trường hợp), mình cũng đã thử code và debug khá nhiều, mất gần 1h để giả lập test và sau 10000 bộ test đã tìm thấy trường hợp sai và AC sau đó. Những bạn học lực khá giỏi có thành tích cao trong các kỳ thi làng xã như cubeslove, TooSimple, ecnerwal, haghani... cũng phải sau rất nhiều điểm 0 và sau > 10 lần submit mới AC.

Bài 2: 

- Khá đơn giản để thử tay với Q = 8

- Q = 7, có nhiều cách làm, có thể làm bằng tay tầm 15,20 phút chỉ cần lưu ý là để cả A, B, C cùng có thể xảy ra thì sẽ chia được nhỏ và dùng các query getNextLight một cách hợp lý. Cách giải của Tâm teamate RR là một ví dụ, bạn chia trường hợp khá tốt, sau 3 bước đã có được thứ tự của A, B, C, D là 24 trường hợp trong khi đó 3 bước thì số bộ mã hoá tối đa được là 3^3 = 27. Vì vậy Tâm rất dễ dàng để đạt được kết quả như ý muốn sau 4 bước còn lại vì 6!/24 = 30 nhỏ hơn rất nhiều so với 3^4 = 81.

- Q = 6, Thử đặt một câu hỏi làm như Tâm ở 3 bước đầu xong mò bằng tay hoặc chạy máy duyệt vét cạn các bước sau có được không. Câu trả lời là không bởi vì sau 3 bước làm của Tâm thì ta sẽ chia ra được 24 tập khác nhau mỗi tập có 30 phần tử chưa xác định mà với 3 câu hỏi thì có thể mã hoá tối đa 3^3 = 27 phần tử nên chắc chắn làm 3 bước đầu như Tâm thì sẽ không bao giờ ra được kết quả tốt nhất. Ta có thể thấy 3^6 = 729 rất gần với 6! = 720 vì vậy với mỗi bước cân ta phải nghiêm ngặt chia các tập ra gần như phải là chia 3, khi đến các bước cân thứ 3 trở đi bắt buộc phải là chia 3 ta sẽ có dãy 80,27,9,3,1 các phần tử trong tập lần lượt sau khi ta chia xong các bước thứ 2, 3, 4, 5, 6 (80 có thể là 81). Một thuật toán khả thi là duyệt đặt cận và tại mỗi bước ta có một bộ các hoán vị khác nhau mà số lượng thì không được lớn hơn giá trị có thể, vì vậy sau khi đặt cận thì ta có thể chạy thuật toán khá nhanh ( mình chưa thử code nhưng nghĩ có thể chạy được. Cách thứ 2 mình đưa ra là ngay ban đầu lấy luôn 2 lần cân cho (A, B, C) và (D, E, F) bởi vì các số thuộc 2 bộ này đang độc lập nên sau 2 bước này ta sẽ có 9 bộ 80 phần tử rồi duyệt đặt cận độ sâu 4 cho từng bộ một. Đây là bài khó để AC nhất ngày 1 nhưng mình nghĩ cũng là bài thú vị nhất và dễ kiếm điểm mà không quá nhiều thuật toán nhất. Chúc các bạn AC hết các bài này :))

Anh nghĩ bài 3 làm thô thiển như em chỉ ăn đc subtask 1 thôi :)) subtask 2 số cạnh là N^2 mà.

Trải nửa đường tròn ra đường thẳng nhé, giả sử ta có vị trí \(1;2;3;4\) có đội cần nhận quà, mỗi lần lấy chỉ có \(2\) quà.

Mình phát cho đội ở vị trí \(1;3\) rồi đến \(2;4\) (đi \(6 + 8 = 14 \) đoạn) sẽ lâu hơn phát cho \(4;3\) rồi \(2;1\) (đi \(8+4 = 12\) đoạn) (do phải quay lại vị trí \(0\) để lấy quà)

Bài này khá đơn giản, cái chính là phải cài khéo không TLE (dữ liệu khá lớn, phải khai báo một mảng tầm \(10^{6}\) biến longint ở subtask \(5\) và \(6\), mình cũng theo hướng đấy nhưng vì chưa được tối ưu như cách này nên chỉ làm được \(2\) subtask đầu)

Tự dưng nghĩ ra cách nữa

- Tạo một biến đếm cho biết số quà đang có

Phát cho đội xa điểm \(0\) nhất 

- Lặp liên tục

 + Nếu còn quà thì tìm đường ngắn nhất đến đội tiếp theo để phát

 + Không còn quà thì tìm đường ngắn nhất về \(0\), sau đó phát cho đội ở xa điểm \(0\) nhất

Cho đến khi hết đội cần phát quà thì về \(0\) (nếu đề bài yêu cầu)

Dùng danh sách vòng tròn (\(Queue\) thì phải) để hỗ trợ việc tìm đội gần nhất

Có vẻ không khả thi lắm vì độ phức tạp khoảng \(O(n^{3})\)

Thường thi Quốc tế thì \(O(n^{2})\) là cùng!

Mà bạn đối phó với test này thế nào đây?

\(n=4; k=2; l=200\)

\(pos = [1; 98; 102; 199]\) (không biết kí hiệu thế này có đúng không)

Thì phát cho \(1; 199\) rồi phát cả vòng tròn thì sẽ ra \(203\)

Thuật toán của bạn ra \(98.2+98.2\)

(do phát từng nửa vòng tròn một)