Vòng loại phía Bắc của ACM Việt Nam vừa diễn ra :D Bạn nào vừa thi vào đây trao đổi nhé.

Cho những ai chưa biết:

Đội mình làm đc 10 bài (trừ B, bọn mình làm 3^14 nhưng TLE suốt :'( ), không biết các đội làm như nào :D

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

À, thì là đa đồ thị, 2 đỉnh có nheièu cạnh nối, cũng không ảnh hưởng đến dijkstra :D

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

oh nghĩa là bài J này chỉ đơn thuần duyệt qua 10 đỉnh gần nhất mà không quan tâm là Q đỉnh cho trước hả bạn? Nếu thế thì mình bỏ phí bài J này rồi.

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

Bài A mình ngồi xem lại xác suất thống kê thì tính ra được kỳ vọng của A và B đúng như phần ví dụ, cài đặt được nhưng nghĩ đến tổ hợp với số phần tử 10^6 thì next luôn :D

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

Không.

Q <= 10.

Dijkstra từ Q đỉnh này.

Bài B có thể duyệt nhánh cận (Cái này chạy nhanh nhất). Hoặc chia tập match thành 2 phần rồi 3^14log, hoặc 3^14 (nếu hash) Nhưng không hiểu sao đội RR bị TLE :)

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

F: Interval tree,

Bản chất 2 thao tác A, B đều cùng 1 loại: Cộng phần tử đầu tiên 1 lượng X, các phần tử phía sau cộng thêm 1 lượng Y tăng so với phần tử phía trước cùng 1 lượng. (A là cộng 1, B là cộng -1)

Vì thế mỗi nút của IT sẽ lưu các tham số gồm, Lượng cộng X của phần tử đầu tiên, lượng cộng tăng dần Y của các phần tử phía sau, tổng hiện tại, giá trị gán của truy vấn C, và 1 biến boolean để biết truy vấn cuối cùng nên nút là A/B hay C. => Update các kiểu hơi phức tạp 1 tẹo.

I: thực chất đồ thị là 1 tập các đồ thị con, trong đó mỗi đồ thị con sẽ có 1 nhân là vòng tròn , sau đó mỗi đỉnh của vòng tròn sẽ tõe ra các kiểu => tính số cách cho vòng tròn, mỗi đỉnh từ vòng tròn tõe ra sẽ có K-1 cách.

J: 1 vài submission bị TLE, là do tính nhầm độ phức tạp nên dùng sai cách. Dijktra không phải NlogN mà là MlogN.

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

Bài A:

+) Phần tính kì vọng số loại phần quà được phát ra khá đơn giản. Đầu tiên, kì vọng để một phần quà bất kì KHÔNG được phát ra là ((M-1) / M) ** N. Do đó, kì vọng số phần quà được phát ra là M * (1 - ((M-1) / M) ** N).

+) Để ý một chút sẽ thấy tổng bình phương của số lần mỗi phần quà được phát ra kì thực chính là số cặp (i,j) (chú ý, (i,j) phân biệt với (j,i) nếu i != j) mà lượt chơi i nhận được phần quà giống lượt chơi j. Chẳng hạn, lượt chơi 2, 3 và 5 ra cùng một phần quà thì ta sẽ có 9 cặp là (2,2), (2,3), (2,5), (3,2), (3,3), (3,5), (5,2), (5,3), (5,5). Vì vậy, câu hỏi 2 chuyển về tính kì vọng số cặp (i,j) thỏa mãn.

Xét cặp (i,j) bất kì, kì vọng để chúng có chung phần quà là: 1 / M nếu i != j (có N * (N - 1) cặp như thế), và 1 nếu i == j (có N cặp). Từ đây dễ dàng tính ra kết quả là (N * (N - 1) * (1 / M)) + (N * 1) = N * (N + M - 1) / M.

Anh RR lam bai I the nao vay? 

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

Bài I ở trên có người nói rồi mà :v

Có phải bài K là thay hình tròn thành hình vuông với cạnh = 2R phải không nhỉ?

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

Không.

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

Anh RR giúp em hướng giải bài K với ạ :D Em nghĩ là QHĐ đúng không ạ?

Bài K chỉ cần sắp xếp các hình chữ nhật theo chiều dài cùng với việc sắp xếp hình tròn sau những hình nó có thể chứa được là đưa về dạng dãy con tăng dài nhất có đúng không nhỉ?

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

Sort tất cả các hình theo diện tích rồi tìm dãy con tăng là đc (chính xác là dãy mà 2 phần tử liên tiếp có thể đặt trong nhau)

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

sau khi mình dijkstra q thành phố đó thì mình sẽ có 1 danh sách d[i][j] ma trận kề đến đây mình duyệt đồ thị ma trận kề này và mỗi khi nó qua đủ q đỉnh rồi về điểm xuất phát thì mình sẽ update lại giá trị min của chu trình đó. Mình làm như vậy có đúng không?