THÔNG BÁO: Đợt huấn luyện tăng cường cho đội tuyển OLP tin học SV 2017

[17520490]

Bàn thêm về ACM/ICPC khu vực phía Nam năm 2017
ý tưởng Problem G: Robot
g.png
em nghĩ nó có liên quan đến tiếp tuyến 1 chút có robot(0,0) với các cặp trong xanh, đỏ, đen.
VD cặp đỏ, đen cho nhìn gần giống đề so sánh đoạn đường xa nhất rồi nối lại(xanh, đen đường màu đen ) nếu chưa đi qua cái còn lại thì từ tâm cái còn lại hạ vuông góc, lấy giao điểm giữa đường vuông góc và đường tròn sau đó robot đi từ vị trí đầu ---> giao điểm ---> tâm xa nhất ̣(cặp đỏ, đen đường màu đỏ); còn đường xanh nước biển thì đi đến gần hơn sau đó ̣đi theo đường nối tâm. Mà so sánh lớn hơn bé hơn nhớ trừ bán kính nữa, kết quả cũng phải trừ. Không xét trường hợp nằm trong nó dễ rồi. Đây là ý tưởng của em về mặt đồ thị còn code thì em không biết viết.

[sonnt]

Chiều T7 4/11/2017 - Luồng cực đại và các bài toán liên quan

Chào các bạn!
Theo kế hoạch huấn luyện tăng cường, BHL tổ chức buổi về chủ đề Luồng cực đại cho các bạn SV (vào cửa tự do) như sau:

1. Bài toán Luồng cực đại
2. Thuật toán Ford–Fulkerson & thuật toán Edmonds–Karp
3. Thuật toán Dinic's blocking
4. Một số dạng mở rộng:
   • Cặp ghép
   • Luồng nhiều đỉnh phát, nhiều đỉnh thu
   • Luồng bị chặn dưới
   • Luồng trên đồ thị với đỉnh có khả năng thông qua

GV: Nguyễn Thanh Sơn
Phòng: A217
Thời gian: 13g00 ngày 4/11/2017

[17520490]

Chào các bạn!
Để khởi động cho ngày thi 5/11 thì Trường có mở thêm 1 buổi về chủ đồ Luồng cực đại cho các bạn SV (vào cửa tự do) như sau:

1. Bài toán Luồng cực đại
2. Thuật toán Ford–Fulkerson & thuật toán Edmonds–Karp
3. Thuật toán Dinic's blocking
4. Một số dạng mở rộng:
   • Cặp ghép
   • Luồng nhiều đỉnh phát, nhiều đỉnh thu
   • Luồng bị chặn dưới
   • Luồng trên đồ thị với đỉnh có khả năng thông qua

GV: Nguyễn Thanh Sơn

Dạ thầy vẫn phòng A217 phải không ạ?

[sonnt]

Đúng vậy, vẫn là 13g00 tại phòng A217

[17520180]

Diem_Fermat.svg.png

https://vi.wikipedia.org/wiki/%C4%90i%E1%BB%83m_Fermat

...điểm Fermat?... T_T là điểm có tổng tới 3 đỉnh tam giác là nhỏ nhất (Bài E ạ)

[14520903]

Lời giải của tất cả các bài ACM ICPC Vietnam National Round 2017 mà mình tìm được trên http://vnoi.info:

https://docs.google.com/document/d/1cDQEaf_YabpefiG7PiQZErHbr7AJIFjt7IIiDv9n4N4/edit#heading=h.a28bh1vzxh07

[truonganpn]

Lời giải của tất cả các bài ACM ICPC Vietnam National Round 2017 mà mình tìm được trên http://vnoi.info:
https://docs.google.com/document/d/1...h.a28bh1vzxh07

Hình như Thông đang để chế độ tài liệu private quên share cho mọi người ròi

[14520903]

Hình như Thông đang để chế độ tài liệu private quên share cho mọi người ròi

Tác giả của file này là nhóm ra đề và đã chuyển sang chế độ private. Em cũng chưa kịp copy lại.
Hy vọng bạn nào đã lưu lại file này thì share lại thôi thầy.

[sonnt]

Buổi học chiều thứ Bảy 11/11

Chào các bạn, tiếp tục chương trình huấn luyện tăng cường, BHL mời các bạn tham gia buổi tập huấn chiều thứ Bảy 11/11 tại phòng A217 với nội dung:

1. Thảo luận về đề thi ACM Vietnam-national17
2. Chuyên đề Hình học tính toán
   • Biểu diễn các đối tượng hình học cơ bản
   • Hợp nhất các đoạn thẳng trên trục hoành
   • Tính diện tích đa giác không tự cắt
   • Xác định chiều của đa giác
   • Kiểm tra đa giác có phải là đa giác lồi
   • Tìm trọng tâm của đa giác lồi
   • Tìm bao lồi tập điểm
   • Kiểm tra điểm nằm trong đa giác
   • Tìm cặp điểm gần nhất
   • Xác định hình tròn nhỏ nhất bao phủ tập điểm
   • Các tâm của tam giác
3. Xác định các thành viên, đội tuyển chính thức của UIT

Giảng viên:

1. Phạm Nguyễn Trường An
2. Nguyễn Thanh Sơn

[17520144]

Thứ 7 học quân sự r thầy :3

[16521257]

Em tìm được sol của mỗi bài A trên newsfeed: trích nguyên văn như sau ạ:
Bài này mình làm như sau: Với mỗi truy vấn update dạng 1 x y (truy vấn 2 x y làm tương tự), a_i sẽ được cộng thêm (i-x+1)*(i-x+2)*(i-x+3) với i<=y. Đặt t1 = -x+1, t2 = -x+2, t3 = -x+3, khai triển cái trên, ta thấy a_i tăng thêm i^3 + (t1+t2+t3)*i^2 + (t1*t2 + t2*t3 + t3*t1)i + t1*t2*t3.
Sử dụng một cây phân đoạn (sử dụng lazy update), khi update đoạn (l, r), nếu (l, r) nằm trong đoạn (x, y), ta cập nhật giá trị nút quản lý đoạn (l, r) lên ps_3(r) - ps_3(l-1) + (t1+t2+t3)*(ps_2(r) - ps_2(l-1) + (t1*t2+t2*t3+t3*t1)*(ps_1(r)-ps_1(l)) + t1*t2*t3 với ps_i(j) là tổng 1^i + 2^i + ... + j^i. Truy vấn lấy tổng làm tương tự trên cây phân đoạn thông thường.

Ngoài ra, có bạn làm buffer j đó nữa ạ

[16521170]

Sol của bài G, em đã làm lại thử và đã AC:
- Xem xét lại công thức L^2 + alpha*K, do a >= 10^6, nên chỉ cần a tăng 1 đơn vị thì kq sẽ tăng 2.000.001, trong khi đó, K max = N = 10^5 , nhân thêm alpha 20 = 2.000.000
=> Kết quả chỉ phụ thuộc độ dài cạnh mà thôi. Như vậy bài toán trở thành tìm chu trình có chứa cạnh lớn nhất (trong chu trình đó) là nhỏ nhất trong các chu trình là được
=> Ta dùng thuật toán Kruskal tìm cây khung nhỏ nhất và Tarjan tìm chu trình
- Sort cạnh lại, ta thêm dần từ nhỏ đến lớn các cạnh này vào cây khung (vừa thêm vừa đánh dấu các đỉnh,cạnh này vào 1 đồ thị vô hướng G)
- Khi cạnh cuối cùng thêm vào mà tạo thành chu trình, đây chính là L lớn nhất trong chu trình cần tìm --> Tìm được L
- Duyệt lại bằng thuật toán Tarjan trên đồ thị G ta xây dựng lúc nãy, ta chắc chắn sẽ tìm được chu trình (hay có thể xem là Thành phần liên thông mạnh) có phần tử đảm bảo chứa cạnh L
--> Đếm số phần tử của Thành phần liên thông mạnh này --> tìm được K , xong

[truonganpn]

Thứ 7 học quân sự r thầy :3

Em hỏi lại thử nha, tại thầy Toàn liên hệ với bên quốc phòng họ nói chiều thứ 7 được nghỉ á.

[17520144]

bữa trc mấy thầy dạy QP có nói đc nghỉ sớm chứ k biết mấy h ạ

[14520903]

Solution chính thức đây các bạn:

https://www.facebook.com/acmicpc.vietnam/posts/929280877222411