Vào 23:00 tối nay 05/08/2015 Codeforces Round #Pi (Div. 2) sẽ diễn ra.

Thời gian kết thúc đăng ký: 22:55

Mọi người có thể cùng vào đây thảo luận sau khi cuộc thi kết thúc.

Bài E code double Hash, ko ngờ có thánh vẫn hack đc :'( so sad

Hướng dẫn giải Codeforces Vòng #Pi

567A – Gửi thư ở mảnh đất thẳng

Ta đánh số \(n\) thành phố từ \(0\) đến \(n-1\)

Ta thấy rằng chi phí lớn nhất để gửi thư từ thành phố thứ \(i\) bằng giá trị lớn nhất giữa khoảng cách từ thành phố đầu tiên đến thành phố \(i\) và khoảng cách từ thành phố \(i\) đến thành phố cuối cùng (\(max(abs(x_i-x_0),abs(x_i-x_{n-1}))\)). Mặt khác, chi phí nhỏ nhất để gửi thư từ thành phố \(i\) bằng giá trị nhỏ nhất giữa khoảng cách từ thành phố \(i\) đến hai thành phố lân cận (\(min(abs(x_i-x_{i-1}),abs(x_i-x_{i+1}))\)). Lưu ý thành phố đầu tiên có chi phí gửi thư nhỏ nhất là \(abs(x_0-x_1)\)và thành phố cuối cùng có chi phí gửi thư nhỏ nhất là \(abs(x_{n-1}-x_{n-2})\)

Sai lầm cần tránh

Không được gán \(x_{-1} = x_n = \pm\infty\) vì:

- Nếu để kiểu \(longint\) thì sẽ bị tràn số

- Nếu để kiểu \(int64\) thì sẽ bị \(TLE\)

567B - Thư viện Quốc gia Berland

để trả lời các truy vấn một cách chính xác, ta cần biết những người còn ở trong thư viện. đầu tiên ta khởi tạo một mảng \(in\) kiểu \(boolean\). Ngoài ra ta cần thêm hai biến để lưu trữ đáp án và số người đang ở trong thư viện. Hãy gọi hai biến này lần lượt là \(ans\) và \(state\).

Trường hợp \(1\), nếu ta nhận được truy vấn \(+\) \(a_i\) thì ta tăng biến \(state\), đánh dấu người này đang ở thư viện ​(\(in[a_{i}] = true\)) và cập nhập đáp án (\(ans=max(ans,state)\)).

Trường hợp \(2\), ta nhận được truy vấn \(-\) \(a_i\). Nếu ta ghi nhận người đó đang ở thư viện, ta chỉ cần giảm biến \(state\) \(1\) đơn vị. Ngược lại nếu ta không ghi nhận người đó đang ở thư viện \(in[a_i]=false\), nghĩa là người đó đã vào trước khi ta bắt đầu đếm, vậy là ta phải tăng biến \(ans\) lên \(1\) đơn vị. Lưu ý không ​cập nhập \(in[a_i]=true\)

567C - Cấp số nhân

Hãy giải bài toán này bằng cách kiểm tra khả năng \(a_{i}\) có phải là phần tử giữa của một dãy thoả mãn điều kiện hay không. \(a_i\) là phần tử giữa khi thoả mãn cả hai điều kiện:

- \(a_i \vdots k\)

- Dãy \(a\) tồn tại các phần tử \([\frac{a_i}{k}] \leq a_i\) và \(a_i.k \geq a_{i}\)

Điều kiện \(1\) đễ kiểm tra rồi, để kiểm tra điều kiện \(2\) bạn cần xây dựng một cấu trúc cây nhị phân để tìm hai giá trị trên (mình dùng \(Treap\)) và tính số dãy thoả mãn điều kiện từ ba số này bằng các công thức Toán học Tổ hợp. Tổng các số tính được là kết quả.

Cập nhập 1: Cảm ơn bạn AresGod đã góp ý, mình đã sửa lại một số phần cho hợp lí hơn :)

(Bài này mình dựa vào ý hiểu của mình nên có gì không ổn thì nhắn lại)

Dựa vào bản Google Translate từ Editorial tiếng Nga (nên có thể bị sai lệch)

567D - Thủy chiến một chiều

Đầu tiên, ta cần hiểu khi nào trò chơi kết thúc. Điều đó xảy ra khi trên bảng kích thước \(n\)  không còn có thể đặt được \(k\) tàu có kích thước \(a\) nữa. Với mỗi đoạn có chiều dài \(len\)  ta đếm số lượng tàu lớn nhất có kích thước \(a\) có thể đặt được trên đoạn đó. Mỗi tàu chiếm một đoạn dài \(a+1\), ngoại trừ tàu cuối cùng. Vì vậy, công thức tính số tàu lớn nhất có thể đặt trên một đoạn là \([\frac{len+1}{a+1}]\), và đối với đoạn \([l..r]\) là \([\frac{r-l+2}{a+1}]\).

Để giải bài toán ta cần lưu trữ mọi đoạn \([l..r]\) mà không vị trí nào trong đó bị bắn. Các bạn dùng \(C\) có thể dùng \(std: : set\) để làm điều này. Bằng cách này, ban đầu trước khi bắn ta có một đoạn \([1..n]\) và số tàu tối đa trên bảng là \([\frac{n+1}{a+1}]\)

Với mỗi lượt bắn ta tìm một đoạn có chứa vị trí bị bắn \(x\) (gọi đoạn đó là \([l..r]\)), ta cần cập nhập lại tập hợp các đoạn. Đầu tiên, ta xóa đoạn \([l..r]\) và giảm số lượng tàu tối đa có thể trên toàn bảng \([\frac{r-l+2}{a+1}]\) đơn vị. Tiếp theo, bạn chèn thêm hai đoạn \([l..x-1]\) và \([x+1..r]\) và cập nhập lại số lượng tàu tối đa có thể trên toàn bảng bằng công thức trên. Nếu như số lượng tàu tối đa nhỏ hơn \(k\), đưa ra câu trả lời và thoát. Nếu hết tất cả các lượt đi mà số lượng tàu tối đa vẫn lớn hơn hoặc bằng \(k\), in ra \(-1\).

567E - Chủ tịch và các tuyến đường

Chưa học đến đường đi ngắn nhất nên không hiểu lắm, nên mình sẽ dịch sau.

567F - Lăng

Dùng quy hoạch động

Tài liệu tham khảo

Editorial Codeforces Round #Pi

P/S: Lần sau dịch đề bài chắc sẽ thiết thực hơn :)

Trả lời RR
  Hiện bài gốc

Em nghĩ là MODULO random thì chắc không hack được.

Trả lời ladpro98
  Hiện bài gốc

Cái thằng trong room anh nó có code sinh test để giết từng modulo :p (nhập modulo vào rồi nó sinh test theo modulo đấy ý)

Trả lời RR
  Hiện bài gốc

~:> random mod =))

Trả lời bvd
  Hiện bài gốc

Cho mình góp ý bài của bạn tí xíu:

- Thứ nhất, "Geometric Progression" có nghĩa là Cấp số nhân, nếu bạn chưa biết nghĩa thì mình nghĩ tốt hơn là nên để tên đề bài bằng tiếng Anh , tiện cho việc sau này copy gõ tên bài trên codeforces luôn (với lại bài A bạn dịch "mảnh đất thẳng" nghe hơi bị kì :v)

- Ý tưởng ở bài C của bạn có vẻ đúng rồi, với mỗi ai % k = 0 cần kiểm tra xem nó phải là phần tử giữa của một dãy 3 số tạo thành cấp số nhân ratio k không, đếm số dãy nó thuộc vào bằng cách đếm số phần tử mang giá trị (a/k) đứng trước nó nhân với số phần tử mang giá trị (ai * k) đứng sau nó. Đáp án là tổng của các giá trị nói trên. Đây chỉ là công thức tổ hợp đếm lớp 11 :3 , bạn có thể làm điều này dễ dàng với STL map, unordered_map trong C++.

Trả lời bvd
  Hiện bài gốc

BÀI D:

 theo cách của bạn thì "tìm đoạn [l..r] chứa x"

mình hiểu là tìm đoạn l,r chứa x mà (r-l) nhỏ nhất

mọi người chỉ mình cách tìm l,r với!!!!. mình nghĩ là dùng IT nhưng khá dài. mình thấy code của tác giả rất ngắn.

mà bài này chặt nhị phân cũng ok

Trả lời lecong
  Hiện bài gốc

Chỉ có một đoạn \([l..r]\) duy nhất chứa \(x\) thôi bạn!

Ví dụ ta có một đoạn \([1..5]\)

0 0 0 0 0

Ta bắn vào vị trí \(2\) chẳng hạn

0 1 0 0 0

Ta xóa đoạn \([1..5]\) đi và chèn hai đoạn \([1..1]\)\([3..5]\), sau đó bạn tính số tàu đặt được trong hai đoạn này để cập nhập lại.