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

[16521170]

Các thầy cho em hỏi thêm về bài ACM-miền Bắc này ạ. https://vietnam-north17.kattis.com/p...placementroads . Bài về đường đi ngắn nhất. Do có liên quan đường đi ngắn nhất của cặp đỉnh bất kỳ nên em nghĩ là dùng Floyd. Nhưng do có thêm điều kiện cập nhật khi Cạnh bị "chặn", nên Time chạy không đáp ứng được. Không biết là bài này có thêm kiến thức gì nữa không ạ ?

[truonganpn]

Gửi các bạn một số bài tập sử dụng 02 thuật toán tìm đường đi ngắn nhất là https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm và https://en.wikipedia.org/wiki/Floyd%...hall_algorithm
Các bài này khá đơn giản, chỉ đòi hỏi hiểu rõ cách cài đặt thuật toán và có một số điều chỉnh nhỏ so với các cách cài đặt thông thường.

Bài 1: http://www.spoj.com/problems/SAMER08A/
Bài này thuần thúy là tìm đường đi ngắn nhất nhưng phải chịu khó đọc đề để làm theo đúng yêu cầu. Ráng đừng google dịch nhé.

Bài 2: http://codeforces.com/problemset/problem/757/F
Bài này sau khi tìm đường đi ngắn nhất xong cần thêm một bước xây dựng Dominator tree. Hướng dẫn xây dựng Dominator trên có thể xem ở đây: https://tanujkhattar.wordpress.com/2...irected-graph/ còn không thì dùng cách duyệt thông thường tìm LCA cũng được

Bài 3: http://codeforces.com/contest/295/problem/B
Bài này hỏi về đường đi ngắn nhất giữa tất cả các cặp điểm trong đồ thị nên sẽ phải dùng giải thuật Floy-Warshall

[sonnt]

Chào các bạn,
Mời các bạn tiếp tục chương trình huấn luyện chiều T7 18/11 với nội dung:
1. Trao đổi thêm về hình học tính toán
2. Các thuật toán tìm đường đi ngắn nhất và ứng dụng
Thời gian và địa điểm vẫn như cũ, 13g00 - phòng A217
Nhớ tham dự đầy đủ và đúng giờ nhé.

[sonnt]

Đã thêm slides bài giảng của buổi học nhé các bạn

https://forum.uit.edu.vn/threads/67497-THONG-BAO-Dot-huan-luyen-tang-cuong-cho-doi-tuyen-OLP-tin-hoc-SV-2017?p=375710&viewfull=1#post375710

[toannv]

Chào các bạn!
Tôi đã xin thầy Diễn - Trưởng phòng Đào tạo bên Quốc phòng để 3 bạn sau được nghỉ học ngày mai rồi nhé. Thầy Diễn thông tin sẽ xin ý kiến BGĐ và phản hồi lại: nhưng chắc 99% là được.

MSSV	Họ và tên	Khoa
17520015	Nguyễn Hữu Phong	Khoa Khoa học Máy tính
17520144	Trần Kim Sen	Khoa Mạng Máy tính và Truyền thông
17520180	Lê Thủy Triều	Khoa Khoa học Máy tính

[truonganpn]

Solution chính thức đây các bạn:
https://www.facebook.com/acmicpc.vie...29280877222411

Bài L troll ác thật, tui cũng hông nhận ra được. Câu đó hay

[sonnt]

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

Ô, sao tui được thông báo là thứ 7 không học mà, để tui kiểm tra lại nhé.

[14520903]

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

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

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

[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ỉ á.

[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

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

[17520144]

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

[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

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