em xin chia sẻ cách làm một vài bài team e làm dc :D :D

B: xây dựng gần giống tam giác pascal rồi nhân ma trận (C11CAL-vnoi :D )

vì sao xây dựng gần giống tam giác pascal thì mn có thể tham khảo tại link: http://lbv-pc.blogspot.com/2012/05/summing-up-powers.html

C: Dijkstra :D :D

E: duyệt trâu

F: sinh hết các số thỏa mãn đề bài rồi chặt nhị phân :D :D

G: cây khung trên đồ thị có hướng, sử dụng thuật toán chu liu (https://en.wikipedia.org/wiki/Edmonds%27_algorithm )

H: rời rạc hóa và chia BLOCK (KQUERY2) :D

Có thể bạn ko tin nhưng bài H duyệt trâu :))

mình thì cứ thắc mắc sao bài khó vãi mà các đội ăn như đúng rồi :3 :3, buồn quá, hóa ra là test yếu :3

Bài I bạn làm thế nào @@

bài I team m ko làm dc :D :D

Bài H đánh lừa lúc đầu tưởng là interval tree, sau 1 hồi đọc đề quyết định đề bài bảo thế nào làm y sì thế đó =>Yes

Bài G mình tìm cây khung nhỏ nhất trên đồ thị có hướng mà submit báo sai @_@
 

Bài H ý tưởng của problem setter là chia thành block sqrt(N).

Tuy nhiên vì code các bạn được dịch với -O2 và máy chấm hơi bị quá mạnh so với quy định nên là duyệt trâu vẫn ăn :(

A: thay vì tìm S phủ, mình cần xây dựng hàm tìm S giao của 1 tập các tam giác (đa giác lồi). ==> Sau khi làm được bước này thì dùng inclusion exclusion. Ví dụ S phủ (1, 2, 3) = Sgiao(1) + Sgiao(2) + Sgiao(3) - Sgiao(1,2) - Sgiao(2,3) - Sgiao(1,3) + Sgiao(1,2,3)

B: như bạn cdsht 

C: dijkstra 4 lần từ 1 và N đi bằng đi bộ / xe đạp. Sau đó duyệt điểm đổi, tính min max cộng trừ 1 chút thì ra kq. Một số đội hiểu lầm rằng đi xe đạp luôn nhanh hơn đi bộ ==> sai.

D: duyệt mọi giao điểm của 2 hcn, đưa về kiểm tra ax + by = c có nghiệm dương hay không. Tricky: các điểm giao có thể không phải tọa độ nguyên (ví dụ 1 1 2 2 và 2 3 1 1) ==> chỉ cần nhân mọi số trong input với 2 + xử lý như điểm nguyên.

E: quá dễ

F: một số đội hiểu nhầm đề là sau khi lật ngược chỉ cần là số valid là ok. Hiểu đúng phải là sau khi lật ngược thì số trước với số sau giống hệt nhau. Sinh hết các số thỏa mãn rồi chặt nhị phân. Sinh hết thì chỉ cần sinh nửa đầu. Ví dụ số có độ dài 9, chữ số đầu tiên có thể là (2, 5, 6, 8, 9), chữ số thứ 2, 3, 4 có thể là (0, 2, 5, 6, 8, 9). Số ở giữa (0, 2, 5, 8). Sau khi sinh xong, thêm trường hợp đặc biệt, 1, 11, 111, 1111, ....

G: Chu liu - Edmonds

H: duyệt trâu hoặc chia block sqrt(N)

J: sort lại, với max = số số khác 0 + 1, với min thì cứ nhét từ lớn tới bé vào.

Gợi ý I: nếu bài toán là đường thẳng + màu theo thứ tự cầu vồng, bản chất là đếm số cặp (i, j) mà i < j và color[i] xếp sau color[j] theo thứ tự cầu vồng.

Các bạn tự nghĩ cách làm tiếp nhé

Lúc đầu mình cũng định làm IT (mỗi nút lưu 1 BST) nhưng sau ngại cài BST nên chia căn vẫn AC :v

bài B có 1 công thức khá bá đạo tại https://en.wikipedia.org/wiki/Faulhaber's_formula

Điên với bài H quá :'( thấy bài H rõ rắc rối mình ngồi cài interval tree time limit tóe loe mà các đội submit AC ầm ầm không hiểu sao :'( hóa ra duyệt trâu có thể qua :'(

Một hướng giải khác cho bài B:

+) Đầu tiên nhận thấy F(x) = 1^K + 2^K + ... + x^K là một đa thức bậc (K+1) (cái này có thể chứng minh theo công thức Taylor https://en.wikipedia.org/wiki/Taylor%27s_theorem )

=> Đến đây có 2 cách giải:
i) Tính F(0), F(1), ..., F(K) rồi khử Gauss

ii) (Cách của team mình) đặt F(x) = a_K+1x^K+1 + a_Kx^K + ... + a₁x + a₀, ta có F(x) - F(x-1) = x^K, từ đó giải ngược từng hệ số a_K+1, a_K, ..., a₀

Bài K: Có thể hơi hư cấu, nhưng đáp số là:

+ N / (2p - 1) nếu (N > 0 và p > 0.5) hoặc (N < 0 và p < 0.5)

+ inf trong trường hợp còn lại

Giải thích rất đơn giản: Trong trường hợp N dương, gọi giá trị bước tiến là +1, giá trị bước lùi là -1 thì giá trị kì vọng của một lần bước là p - (1 - p) = 2p - 1. Do đó nếu 2p - 1 > 0 thì kì vọng số bước để đến ô N là N / (2p - 1), còn không thì theo kì vọng, con robot không thể đến được ô N. Trường hợp N âm làm tương tự.

Bài A thực ra theo mình thấy cài kiểu inclusion exclusion như anh Khuê nói ở trên khá rối.

1 cách cài khác là dùng chia mặt phẳng. Gọi X = tập tất cả các tọa độ x của (các đỉnh tam giác & tất cả các giao điểm). Với mỗi xi thuộc X, vẽ 1 đường dọc x = xi.

Lúc này mặt phẳng chia thành nhiều dải. Với mỗi dải, tính diện tích phần bị phủ. Cái này khá dễ tính do trên 1 dải, ko có 2 đoạn nào cắt nhau --> chỉ đơn giản là sort lại theo tọa độ y của các đoạn rồi tính diện tích

Ở đây có công thức đơn giản nhất của bài B (và C11CAL) mà mình biết

http://mathforum.org/library/drmath/view/55887.html

\(\sum_{x=1}^{n} x^k = \sum_{p=1}^{k} S[k][p]*p!*{n+1 \choose p+1} \) trong đó \(S[i][j]=S[i-1][j-1] + j*S[i-1][j] \forall j \leq i\)

Klq nhưng cho e hỏi là mấy bài này tác giả có up lên trang nào khác để upsolve ko ạ?

Năm ngoái bọn mình có xin đc test và up lên Codeforces (link)

Năm nay nếu xin đc test thì khả năng cao mình cũng sẽ up lên CF.

Đợt này anh hơi bận nên chưa chuẩn bị được. Khả năng là vòng miền Bắc + miền Trung + National sẽ lên codeforces hoặc kattis.