Announcement

Collapse
No announcement yet.

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

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • #16
    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.
    Last edited by 17520490; 29-10-2017, 16:52.

    Comment


    • #17
      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
      Attached Files
      Last edited by sonnt; 04-11-2017, 10:46. Reason: Thêm slidé

      Comment


      • #18
        Originally posted by sonnt View Post
        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 ạ?

        Comment


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

          Comment


          • #20
            Diem_Fermat.svg.png

            ...đ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 ạ)

            Comment


            • #21
              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:

              Comment


              • #22
                Originally posted by 14520903 View Post
                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

                Comment


                • #23
                  Originally posted by truonganpn View Post
                  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.

                  Comment


                  • #24
                    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
                    Attached Files
                    Last edited by sonnt; 11-11-2017, 13:56. Reason: Thêm slides

                    Comment


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

                      Comment


                      • #26
                        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 ạ

                        Comment


                        • #27
                          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

                          Comment


                          • #28
                            Originally posted by 17520144 View Post
                            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ỉ á.

                            Comment


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

                              Comment


                              • #30
                                Solution chính thức đây các bạn:
                                Hướng dẫn giải cho các bài thi ở vòng thi quốc gia vừa qua: https://docs.google.com/document/d/1cDQEaf_YabpefiG7PiQZErHbr7AJIFjt7IIiDv9n4N4/edit?usp=sharing Source code của BGK...

                                Comment

                                LHQC

                                Collapse
                                Working...
                                X