1 năm, 7 tháng trước

Sáng nay vừa diễn ra ACM VN national

Các bạn vào đây thảo luận nhé :D

1 năm, 7 tháng trước

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

1 năm, 7 tháng trước
Trả lời cdsht
  Hiện bài gốc

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

1 năm, 7 tháng trước
Trả lời Junior_K
  Hiện bài gốc

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

1 năm, 7 tháng trước
Trả lời cdsht
  Hiện bài gốc

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

1 năm, 7 tháng trước
Trả lời minhthuan274
  Hiện bài gốc

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

1 năm, 7 tháng trước

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

1 năm, 7 tháng trước
Trả lời cdsht
  Hiện bài gốc

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

1 năm, 7 tháng trước
Trả lời Hieu2703
  Hiện bài gốc

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

1 năm, 7 tháng trước
Trả lời cdsht
  Hiện bài gốc

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.

 

1 năm, 7 tháng trước
Trả lời khuebeo
  Hiện bài gốc

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é

1 năm, 7 tháng trước
Trả lời Hieu2703
  Hiện bài gốc

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

1 năm, 7 tháng trước

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

1 năm, 7 tháng trước
Trả lời thienvamai
  Hiện bài gốc

Đ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 :'(

1 năm, 7 tháng trước

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) = aK+1xK+1 + aKxK + ... + a1x + a0, ta có F(x) - F(x-1) = xK, từ đó giải ngược từng hệ số aK+1, aK, ..., a0

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ự.

1 năm, 6 tháng trước

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

1 năm, 6 tháng trước

Ở đâ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\)

1 năm, 6 tháng trước

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 ạ?

1 năm, 6 tháng trước
Trả lời abcdef6199
  Hiện bài gốc

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.

1 năm, 6 tháng trước
Trả lời RR
  Hiện bài gốc

Đợ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.