RR
user-avatar

Nguyen Thanh Trung

Đóng góp: 509

Ngày sinh: 23/06/1992

Đăng ký: 03/07/2015

Lần đăng nhập cuối: 17/07/2016

Kết nối tài khoản

VOJ: mr_invincible (588.01 điểm)

Topcoder: Chưa kết nối

Có bạn nào có input bài VMCOUNT?

Có 1 điều rất đáng buồn là bọn mình (admin) đã để mất input bài VMCOUNT :(. Nếu có bạn nào giữ thì up lên cho bọn mình xin lại nhé.

Bài này thuộc dạng chỉ nộp output, nên nếu ko có input thì ko thể làm đc.

 

Lời giải VMSINCOS

Bài này mình ra đề cho VNOI Marathon 2013 :D. Hôm nay lục lại máy thấy solution mình viết nên đăng lại lên forum :D

Kiến thức cần biết:

  • Các hàm lượng giác cơ bản

  • Interval tree hoặc Splay tree

  • Maclaurin series / Taylor expansion

 

Các cách giải:

  • 20% test đầu tiên (N, Q <= 5000).

    • Với N và Q nhỏ, cách làm chỉ đơn giản là brute force.

    • Mỗi truy vấn Modify có thể thực hiện trong O(1).

    • Mul, Sin, Cos và Reverse có thể thực hiện trong O(N).

  • 20% test tiếp theo: (ko có Mul & Reverse)

    • Nhận xét:

      • sin(a + b) = sina*cosb + cosa*sinb

    • Như vậy, việc tính tổng sin(Ai + x) có thể dễ dàng được thực hiện nếu ta tính nhanh được tổng sin(Ai). --> có thể dùng interval tree cơ bản để xử lý.

  • 20% test tiếp theo: (ko có Reverse)

    • Để giải quyết được truy vấn dạng Mul, các bạn cần phải biết về Taylor Expansion, hoặc 1 trường hợp đơn giản hơn của nó là Maclaurin Series. https://en.wikipedia.org/wiki/Taylor_series#List_of_Maclaurin_series_of_some_common_functions

    • Từ đó có được công thức xấp xỉ để tính sin (tương tự cho cos) :

      • sin(x) = x - x^3/3! + x^5/5! - x^7/7! + …

    • Với sai số yêu cầu của bài toán, bạn chỉ cần tính khoảng 20 - 30 giá trị đầu.

    • Vì không có thao tác dạng Reverse, bạn chỉ cần một interval tree, lưu lại tổng x^k với mọi k <= 20. Từ đó có thể nhanh chóng tính được tổng trên.

  • 20% test tiếp theo: (ko có Mul)

    • Cách làm giống như 20% thứ 2, nhưng bạn phải cài đặt Splay Tree cho thao tác Reverse.

  • 20% cuối cùng:

    • Kết hợp Splay Tree & Maclaurin Series.

 

Lời giải BUBBA2

Bài này mình ra đề từ thời thi VNOI Marathon 2012, hôm nay lục lại máy tính thấy có lời giải, nên đăng lại lên đây để các bạn tham khảo.

Tóm tắt đề bài:

  • Cho một cây gồm N đỉnh, trên mỗi đỉnh có 1 nhãn.
  • Với u là một đỉnh lá, gọi dãy số thu được khi di chuyển từ gốc đến u là T(u).
  • Cho Q truy vấn, mỗi truy vấn có dạng một dãy số A = (a1, a2, ..., ak). Hỏi là có đường đi từ gốc đến lá nào chứa A là dãy con không.

Lời giải:

30% test đầu tiên:

Với N, Q và K không quá 100, ta có thể giải bài toán với độ phức tạp O(Q*N*K).

Nhận xét là ta cần xét không quá N đường đi: mỗi đường đi có dạng từ một đỉnh đi ngược về gốc của cây. Vì vậy, với mỗi truy vấn, ta có thể duyệt qua tất cả các đường đi này, với mỗi đường đi ta mất O(K) để kiểm tra 2 xâu giống nhau.

Đáng tiếc là có nhiều bạn để mất điểm do duyệt đường đi từ gốc xuống (có quá nhiều đường đi) hoặc cài đặt sai.

 

20% test tiếp theo:

Để giải được 20% tiếp theo, vì K nhỏ, nên ta chỉ cần quan tâm đến O(N*K) đường đi. Bằng việc tiền xử lý, tính trước hash value của các xâu này, ta có thể so sánh các xâu trong O(1). Nhờ vậy, ta dễ dàng có được thuật toán O(N*K + Q*K).

 

20% test tiếp theo:

Với cây có dạng đường thẳng, ta có thể dùng suffix array:

Nối tất cả các truy vấn cùng với xâu đường đi từ gốc đến lá của cây. Tính mảng suffix array và lcp. Kết hợp với một cấu trúc dữ liệu (chẳng hạn interval tree) để tìm giá trị nhỏ nhất giữa một suffix thể hiện truy vấn và một suffix thể hiện một đường đi của cây, ta có thể giải được bài toán trong O((N+sumK) log(N+sumK))

 

30% test cuối cùng:

Để giải quyết trọn vẹn bài toán, có 3 hướng đi: hash, suffix array và Aho-corasick. Ở đây mình chỉ trình bày cách giải dùng hash và suffix array. Các bạn muốn học về Aho-corasick có thể tìm hiểu trên wiki.

 

Hash:

Nhận xét: chỉ có tối đa sqrt(Q), tức là khoảng 200 giá trị khác nhau của K. Vì vậy, nếu xử lý offline, ta chỉ cần tính trước O(sqrt(Q) * N) giá trị khác nhau của hash, khá nhỏ, tuy nhiên vẫn vô cùng khó để có thể qua được hết test với time limit 3s. (Lời giải của yenthanh132 được 75 điểm do bị quá thời gian 5 test). Tuy nhiên để qua toàn bộ test với hash không phải là điều không thể, do giới hạn thời gian khá lỏng. Để qua được các test lớn, các bạn cần có một số heuristic tốt (và cách đánh giá thời gian với các truy vấn đó) giúp trả lời nhanh các truy vấn.

Một số heuristic có thể dùng:

  • Thay vì duyệt tất cả các đường đi từ các đỉnh, chỉ duyệt từ những đỉnh có nhãn bằng với số thứ nhất trong truy vấn.

  • Với các truy vấn có số không xuất hiện trên cây, hoặc số lần xuất hiện của một số lớn hơn tổng số lần xuất hiện trên cây, kết quả luôn là không giống. Có thể làm mạnh hơn heuristic này bằng việc kiểm tra thêm khoảng cách giữa 2 lần xuất hiện của một số, khoảng cách từ lá và gốc đến số đó trên cây.

Nếu cài đặt tốt, kết hợp hash với 2 heuristic trên, các bạn có thể đạt trọn vẹn 100 điểm.

 

Suffix array:

Tư tưởng chính vẫn giống như cách làm với 20% trước: Các bạn cần sort lại các suffix của truy vấn cùng với các đường đi trên cây. Tuy nhiên các bạn cần hiểu tương đối rõ về suffix array.

Mấu chốt của thuật toán suffix array là từ việc sắp xếp các xâu độ dài L, ta có thể sắp xếp các xâu độ dài 2L. Với một mảng quy hoạch động lưu lại cha thứ 2^j của đỉnh i (giống như cách làm LCA), ta có thể tìm kiếm nhanh chóng cha của các đỉnh trong O(logN). Các thao tác so sánh để sắp xếp ta có thể làm tương tự thuật toán suffix array thông thường. Từ đấy thu được một thuật toán áp dụng tư tưởng suffix array trong O((N+sumK)logNlog(N+sumK)). Để tính mảng lcp, cách trực quan nhất là chặt nhị phân kết hợp với hash.

 

Nhận xét của tác giả

Bài này là một bài khá khó, được ra với mục đích kiểm tra xem các bạn sẽ xoay sở thế nào khi không nghĩ được thuật toán tốt. Nếu cài đặt kết hợp được nhiều heuristic tốt, các bạn cũng có thể đạt được khá nhiều điểm cho bài này. Đáng tiếc là không có bạn nào đi theo con đường này.

Lời giải BUBBA1

Bài này mình ra đề từ thời thi VNOI Marathon 2012, hôm nay lục lại máy tính thấy có lời giải, nên đăng lại lên đây để các bạn tham khảo.

Tóm tắt lại đề bài:

Cho N điểm, điểm thứ i có tọa độ (xi, yi).

Cho Q truy vấn, mỗi truy vấn thuộc 2 dạng:

  • Đổi vị trí điểm thứ i

  • Cho điểm (X, Y). Yêu cầu tính sum( max( X-xi, Y-yi ) ).

Với a1, a2 khác 0, bài toán trở nên khó hơn một chút, do các bạn buộc phải trả xử lý online.

Hướng giải:

Bài này được mình cải tiến từ bài VNOI - POINT. Thông thường, với bài toán chứa dấu giá trị tuyệt đối, cách làm là tách riêng theo từng thành phần tọa độ, rồi phá dấu trị tuyệt đối bằng cách xét tính âm dương của biểu thức. Trong bài này, phần khó nhất là không thể tách được hàm sum(max(X-xi, Y-yi)) riêng theo từng trục x, y. Lời giải của ban tổ chức và các thí sinh được lớn hơn 50 điểm đều dùng phương pháp chuyển hệ tọa độ (x, y) thành (x+y, x-y), từ đó thu được hàm khoảng cách mới có thể tách theo từng thành phần tọa độ.

Cụ thể hơn:

30% test đầu tiên

Để qua được 30% test đầu tiên, bạn chỉ cần viết 1 chương trình duyệt thông thường với độ phức tạp O(N*Q). (Giới hạn thời gian khá lớn, nên bạn cũng có thể được 40% test).

50% test tiếp theo

Để qua được 50% test tiếp theo, trước hết cần giải bài toán đơn giản hơn:

  • N người đứng im
  • Heo chỉ di chuyển theo 4 hướng (không di chuyển chéo).

Trong bài toán đơn giản hơn này, khoảng cách giữa 2 điểm (x1, y1) và (x2, y2) là:

|x1 - x2| + |y1 - y2|.

Gọi vị trí của heo là (X,Y), vị trí N người là (xi, yi). Ta cần tính tổng:

sum( |X - xi| + |Y - yi| ), i = 1..N

= sum( |X - xi|) + sum( |Y - yi| )

--> Ta có thể xử lý riêng từng chiều x, y.

Xét chiều x, sau khi phá dấu giá trị tuyệt đối, bài toán được đưa về chặt nhị phân thông thường: Cho mảng tọa độ x, với một số nguyên X, bạn cần tính tổng các số nhỏ hơn X, tổng các số lớn hơn X, số lượng số nhỏ hơn X và số lượng số lớn hơn X.

Bằng việc nhận xét rằng việc di chuyển theo đường chéo thường tốt hơn theo đường thẳng, các bạn có thể chuyển bài toán 8 hướng về 4 hướng sau khi quay điểm (x,y) thành (x+y, x-y).

Để thực hiện thao tác di chuyển người & truy vấn, cần chú ý rằng a1 = a2 = 0, do đó ta có thể tính trước tọa độ tất cả các điểm, từ đó có thể rời rạc hóa & dùng 1 cấu trúc dữ liệu, chẳng hạn interval tree để lưu trữ thông tin của N người.

 

10% test tiếp theo

Để qua được 10% tiếp theo, vì tọa độ <= 10^6, nên dù không cần rời rạc hóa, bạn vẫn có thể dùng interval tree (hoặc các cấu trúc tương tự) để lưu trữ thông tin của N người.

 

10% test cuối cùng

Để qua được 10% test cuối cùng, có 2 cách chính:

1. Dùng Cây tìm kiếm nhị phân cân bằng để lưu trữ thông tin.

2. Dùng interval tree, với cấp phát bộ nhớ động. Chú ý là số nút trên cây cần truy cập vào là O(Nlog(BASE)), nên bộ nhớ cần cấp phát cũng chỉ là O(Nlog(BASE)).

 

2 test cuối có giới hạn N, Q nhỏ hơn. Lý do: interval tree và một số loại cây nhị phân có tốc độ chạy chậm, khó có thể qua được giới hạn 10^5. Mình cố tình đặt giới hạn thời gian để code interval tree và splay tree bị mất từ 2 - 4 test (Lời giải của bạn darksabers dùng interval tree bị mất 4 test). Muốn chắc chắn qua được 100% test với cấu trúc dữ liệu (CTDL) chậm, bạn cần cài cả cách offline và online cho bài này. Tuy nhiên, 1 số CTDL có tốc độ nhanh hơn có thể qua được tất cả các test, ví dụ: treap (yenthanh132), red black tree (langtrunghieu (nick thi VM12 là heroes) - khá tiếc là bạn này cài red black tree vô cùng kỹ thuật nhưng do bị quên mod 1 chỗ nên bị tràn số và sai 2 test)

 

Báo cáo lỗi diễn đàn - submit / đọc đề VOJ

Hiện tại, phần submit & tính điểm VOJ còn khá nhiều lỗi.

Vì vậy, mình lập riêng topic này để các bạn có thể comment lỗi mà các bạn gặp phải vào đây:

  • Đề hiển thị sai / xấu
  • Không submit được
  • Không được cộng điểm (chú ý hiện giờ bọn mình chỉ tính điểm bài ACM và OI).

 

Nhân ma trận

Bài viết đã được chuyển đến Thư viện VNOI mới.

 

Trie

Bài viết đã được chuyển sang thư viện VNOI mới

[ACM] Review về Lăng Trung Hiếu

Giới thiệu:

  • Lăng Trung Hiếu: Topcoder (là người có max rating cao thứ 2 VN sau Khúc Anh Tuấn), Codeforces
  • Cựu học sinh ĐH FPT, từng đi ACM WF năm 2014
  • #2 VNOI

 

Bài này trước mình post lên FB của mình, mà thấy được ủng hộ nên post lại vào đây, hi vọng việc đọc về những "người nổi tiếng" sẽ phần nào giúp các bạn có động lực học Tin hơn :3

 

Nói về tính cách thì 1 điều không thể phủ nhận là anh Hiếu thuộc dạng quái dị nhất trong đống quái dị ngồi thi ACM, với kiểu ngồi đặc biệt giúp tăng cường máu lên não (xem hình), những phát ngôn không thể tin được như "Lăng Trung Hiếu là của Việt Nam" và quan điểm không sợ bố con thằng nào (vd như thằng target kia gà vãi).

Mình "phát hiện" ra anh Hiếu từ cách đây lâu lắm rồi, thời nick hieult trên VNOI còn có màu blue nhưng đã nhảy vào làm ngay bài khó 1 cách rất đầu gấu, khẳng định quan điểm với anh tất cả các bài đều là bài dễ. Lần đầu gặp nhau là ở ACM regional, 2 đứa đã tình cờ đập vào nhau (anh Hiếu kể thế, ko biết có hư cấu không). Trong vòng 1 năm trở lại đây thì anh Hiếu là người có ảnh hưởng nhất với tính cách và quan điểm thi ACM của mình :)) (ví dụ như quan điểm bài nào cũng là bài dễ hoặc không thể làm đc). Anh Hiếu cũng là 1 trong rất ít người có thể cùng ngồi xem đánh nhau với mình (ngồi xem bảng rank ACM suốt 5h), và cũng là người có cùng 1 vài quan điểm với mình như "bố thích thi ACM thì thi" hoặc "không làm mấy bài khó ACM thì cuộc sống tẻ nhạt vãi".

Nói về trình độ thì sau khi Khúc Tuấn về hưu, anh Hiếu đã nổi lên và trở thành vô địch VN :)). Điều này mình thấy vô cùng hư cấu vì tính cách éo thích thì éo làm, vào thi 1 lúc chán thì bỏ luôn, hoặc thậm chí vừa xem phim (hoặc hentai gì đó) vừa code. Những cái này trái ngược hẳn với những gì mình nghe đc về Khúc Tuấn (cũng là quan điểm của mình) là đã train thì phải nghiêm túc và đã làm bài thì phải quyết tâm.

Để kết bài, chúc anh Hiếu sớm đỏ target Topcoder để anh em còn ăn mừng :v

Báo cáo lỗi diễn đàn / Mong muốn tính năng mới

Vì diễn dàn mới ra mắt, không thể tránh khỏi lỗi.

Các bạn nếu tìm ra lỗi / mong muốn có tính năng gì hãy post vào đây để bọn mình biết & sửa sớm nhất nhé :3

 

Khi báo lỗi, các bạn cố gắng chụp màn hình (screenshot) lại nhé :D