[Giải thuật] Interval Tree – Segment Tree
11 Chủ Nhật Th10 2015
Posted ACM, Algorithms
in11 Chủ Nhật Th10 2015
Posted ACM, Algorithms
in14 Chủ Nhật Th6 2015
Posted ACM
inThẻ
Dạng: Binary Indexed Tree
Link: http://laptrinh.ntu.edu.vn/Problem/Details/1146
Thuật toán tra cứu: https://namlunoy.wordpress.com/2015/05/17/1-ky-thuat-binary-index-tree/
Cho dãy n số nguyên a1, a2,…, an. Một cặp số (ai, aj) được gọi là nghịch thế nếu i aj. Hãy đếm xem trong dãy trên có bao nhiêu cặp số nghịch thế.
Dữ liệu nhập:
– Dòng đầu tiên là số nguyên n (2 ≤ n ≤ 105)
– Dòng tiếp theo là n số nguyên a1, a2,…, an, mỗi số cách nhau một khoảng trắng (1 ≤ ai ≤ 10^9)
Dữ liệu xuất:
– Là số cặp nghịch thế đếm được.
Ví dụ
input
3
3 1 2
output
2
input
5
7 4 4 3 1
output
9
Với cận nhỏ có thể có thể sử dụng BIT với các node thể hiện giá trị của đó (giống như bài cái túi)!
Nhưng với cận lớn thì phải kết hợp thê kỹ thuật sort, và các node đánh giá trị theo chỉ số của nó!
Nỗi phần tử ở đây ta quy định nó có 2 dữ liệu, đó là value và index!
Sau đó ta sắp xếp giảm dần (hoặc tăng dần thì các bước sau làm ngược lại).
Như vậy, phần tử sau sẽ có value nhỏ hơn phần tử trước!
Nhưng nếu có index lơn hơn phần tử trước tức là nó ở đăng sau (nhưng lại có value nhỏ hơn) nên đó là 1 cặp nghịch thế!
Thuật toán như sau:
*) Ta đi từ đầu đến cuối dãy đã được sắp xếp, ở đây làm giảm dần
*) t[i] là gì?
Gọi t[i] : là số lượng chỉ số nhỏ hơn nó!
Tại sao: tại vì khi duyệt đến vị trí thứ i (nhỏ hơn các vị trí trước), số lượng cặp nghịch thế mà nó có thể tạo ra, bằng số lượng các phần tử lớn hơn (đã được đáp ứng bằng việc sắp xếp giảm dần) và đứng trước nó (chính là cái ta đang định nghĩa ở đây!)
*) t[i] + 1 khi nào?
Khi gặp phần tử có index là k, do t[k] là số phần tử có index nhỏ hơn k, mà index nhỏ hơn k thì nhỏ hơn k+1!
=> Cập nhật lên trên từ vị trí k+1
Ta xét: dãy 7 4 3 2 1
kết quả lần lượt là 1+2+3+4 = 10.
Nhưng với dãy 7 4 4 3 2
Thì nó sẽ có vấn đề!
Do nó vẫn nhận cặp (4,4) là 1 cặp nghịch thế!
Như vậy 2 số giống nhau nó cần có index giống nhau thì làm mới đúng được!
=> Trong quá trình sắp xếp và đặt chỉ số ta nên lưu ý vấn đề này!
Đã tìm ra lỗi sai!
Quan trọng là lúc sắp xếp ta sắp xếp đúng kiểu thì thực hiện phép trên mới đúng được!
Sắp xếp sai là sẽ sai!
07 Thứ Năm Th5 2015
Posted ACM, Algorithms, OLP
in[DFS]
30 Thứ Năm Th4 2015
Posted ACM, Algorithms, OLP
ind
15 Thứ Tư Th4 2015
Posted ACM, Algorithms, OLP
inhttp://laptrinh.ntu.edu.vn/Problem/Details/76
Trên một vùng đất hình vuông các nhà địa chất phát hiện ra có trữ lượng vàng khá lớn. Để tiện việc khai thác, người ta chia vùng đất thành các lô nhỏ, tổng cộng có n x n lô (n dòng, n cột). Ta đánh số các dòng từ 1 đến n theo chiều từ trên xuống dưới, các cột từ 1 đến n theo chiều từ trái qua phải. Tại lô đất ở dòng i cột j, người ta đo được trữ lượng vàng là ai j. Tuy nhiên, do giới hạn về kỹ thuật chỉ cho phép khai thác trong một diện tích nhỏ gồm k x k lô mà thôi. Bạn hãy giúp chọn hình vuông k x k lô nào cần khai thác để có sản lượng vàng là lớn nhất.
Dữ liệu nhập:
– Dòng thứ nhất là 2 số nguyên n, k (1 ≤ k ≤ n ≤ 1000)
– Trong n dòng tiếp theo, mỗi dòng gồm n số ai j xác định trữ lượng tại lô dòng i cột j (0 ≤ ai j ≤ 1000)
Dữ liệu xuất:
– Là một số nguyên duy nhất xác định sản lượng vàng lớn nhất khai thác được.
Giải thích: khai thác trong các lô đánh dấu đỏ
1 9 1 1 9 9 9 9 1 9 9 9 1 9 9 14
Họ làm như sau:
Gọi T[i,j] sẽ là tổng của tất cả a[x,y] với x<i, và y<j.
Muốn tính tổng của khu vực x, ta chỉ cần trừ đi phần phía trên và phần phía trong của nó (cộng lại phần bù vì nó bị trừ 2 lần) là ok!
29 Chủ Nhật Th3 2015
Posted ACM, Algorithms
in1. Download arena:
http://www.topcoder.com/contest/arena/ContestAppletProd.jnlp
2. Unblock it inproperties windows:
3. See the intruction:
http://topblogcoder.com/tutorials/how-to-begin-in-topcoder/#.VRddeXN83q0
26 Thứ Năm Th3 2015
Posted ACM
in14 Thứ Bảy Th3 2015
Posted ACM, Algorithms, OLP
in1. Các bài liên quan đến giai thừa, hoặc lũy thừa thì lên phân tích hẳn nó ra để tìm ra được quy luật. Nếu là tính toán thì luôn có cách tính toán tối ưu (chứ ko được xây đựng hàm tính lũy thừa hoặc giai thừa để gọi lại, vì mỗi lần như thế lại là một vòng lặp, trong khi ta có thể tính từ giá trị trước đó)
2. Các bài liên quan đến chia hết thì nên sử dụng công thức chia hết.
3. Sai lầm có thể đến từ những thuật toán cơ bản nhất như tìn SNT, UCLN, BCNN,… (Do vậy phải thật chắc chắn phần này)!
4. Những bài sử dụng map khi nó cần truy xuất trực tiếp đến phần tử đó thông qua một chỉ số không phải dạng int, còn các trường hợp khác không nên dùng, đặc biệt khi duyệt map sẽ tốn rất nhiều thời gian!
(NTU : KSMA – K số nhỏ nhất)
5. Một bài ACM luôn có những test hiểm, có 2 loại test hiểm: Đó là test ở cận (nhỏ nhất và lớn nhất) 2 là các giá trị đặc biệt!
6. Nên chuyển sang chế độ vào ra file khi làm việc offline để thực hiện test cho nhanh!
7. Khi gặp 1 bài khó, và ngay lúc đó ko nghĩ ra cách gì ngoài cách duyệt thì phải dừng lại và phân tích mấu chốt của bài toán, chứ làm duyệt sẽ không ăn được bài đó nên đừng mất công!
Đây là các bài toán số học điển hình, chỉ cần ta kiên trì nghiên cứu thật nhiều test là có thể suy ra được công thực và cách làm đúng!
8. Đừng lọ mọ bắt tay vào code khi chưa chạy đúng trên giấy! (Đương nhiên là trừ những bài quá dễ! :v )
9. Với bài nhiều trường hợp điều quan trọng là phải nghĩ ra ĐỦ bộ test cho TẤT CẢ các trường hợp đó!
(Điều này rất quan trọng vì nếu không ta sẽ không biết ta sai ở đâu mà sửa, mặc dù thuật toán đúng!)
10. Việc quan trọng nhất trước khi bắt tay vào nghĩ thuật toán/tìm lời giải đó là hiểu đúng bài toán, hiểu đúng test!
11. Khi làm đệ quy đặc biệt chú ý đến điều kiện dừng của nó nếu ko sẽ bị TLE.
Hôm qua vừa bị 1 thằng Hack vì ko kiểm tra kết = 0, mà chỉ kiểm tra kết quả bằng nhau a==b! 😐
(Nếu sai bước này thì tất cả các phần sau trở thành công cốc!)
12. Những bài như bài cái túi thì nên cài đặt kiểu dữ liệu theo cấu trúc của nó, đề phòng trường hợp cần thao tác như vậy! Và stt cũng có thể dùng như là 2 trường!
13.[QHĐ] Kỹ thuật tính cộng dồn!
Trong trường hợp ta cần tính tổng từ a[i] đến a[j] nào đó, nếu nó cho độ lớn của a[i] đủ nhỏ (<1000)!
Để giảm độ phức tạp tính toán (for(k,i,j)), ngay lúc đầu ta có thể tính cộng dồn vào (a[i] += a[i-1]).
Khi đó tổng a[i] đến a[j] = a[j] – a[i]…
(Ap dụng tương tự với việc tính tổng của khu vực K x K trong 1 ma trận)
(http://laptrinh.ntu.edu.vn/Problem/Details/76)
14.[QHĐ] Với bài sử dụng quy hoạch động thì phải nhìn bài toán một cách tổng quát!
Suy ra công thức 1 cách tổng quát và đệ quy!
Chỉ nên liệt kê ra các trường hợp để thử xem kết quả đúng không chứ ko nên liệt kê ra để tìm công thức, vì như thế sẽ mất rất nhiều thời gian mà lại không phải là cách đúng!
(Nhiều khi đơn giản mà ta lại làm cho nó phức tạp lên!)
(http://laptrinh.ntu.edu.vn/Problem/Details/74)
15.[QHĐ] Với bài quy hoạch động, chỉ số có thể chính là cận của nó!
Như bài cái túi 2! Nhưng nó cũng chỉ làm việc trong độ lớn cho phép!
(http://laptrinh.ntu.edu.vn/Problem/Details/1148)
16. [Graph]Phần này hay sử dụng danh sách kề (BFS,DFS). Và map, pair để lưu độ dài các cạnh
(NTU – SUMTREE)
17. Đối với bài mà lượng input và output lớn thì việc sử dụng scanf và printf sẽ nhanh hơn khá nhiều!
(http://vn.spoj.com/problems/MAXARR1/)
1. Khi sử dụng getline(cin,s) nhớ để cin.ignore(1) phía trước để bỏ dấu enter ngay phía trước nó!
2. Kỹ thuật sắp xếp có điều kiện.
3. Kỹ thuật duyệt map.
4. Kỹ thuật duyệt cây.
5. Bao giờ cũng phải khởi tạo giá trị cho biến đã tạo! Khởi tạo giá trị gì cũng phải nghĩ xem có phù hợp với ngữ cảnh bài toán và tiện cho việc đọc code hay không!
6. Nhiều khi i– đặt ở đâu trong vòng for cũng là một cái cần suy nghĩ!
Vừa dính 1 bài ntn xong!
7. Kỹ thuật tìm kiếm nhị phân cho những bài có yếu tố sắp xếp!
1. Việc đầu tiên là cần chia nhau tìm và lọc ra các bài dễ nhất trước.
2. Với cái bài dễ thì mỗi người xử lý 1 bài.
Người được ngồi code là người ra thuật toán trước.
3. Sau khi xử lý xong các bài dễ.
Đến lượt bài khó thì chia làm 2 đội: Đội 2 người tiếp tục xử lý bài tập tiếp theo, người còn lại tiếp tục đọc đề để tìm bài tiếp theo sẽ xử lý!
(Tuyệt đối phải đọc hết các bài! Không được để xót bài nào!
Nhớ nhé! BẮT BUỘC PHẢI ĐỌC HẾT ĐỀ BÀI!)
– Một số lỗi biên dịch như:
+ Sử dụng cin.ignore thì ok nhưng chạy bằng fflush là lỗi
+ Một số máy thì khi khởi tạo 1 mảng nó sẽ có giá trị bằng = 0, nhưng một số máy lại ko, do vậy nếu dùng mảng thì phải memset, còn ko thì dùng vector cho chắc!
+ Nhớ bỏ ONLINE_JUDGE trước khi nộp bài
+ Việc học thuật toán bằng code là rất khó, cần hiểu được thuật toán và chạy được bằng tay (đặc biệt là những bài đồ thị, thì chỉ có thể học bằng cách vẽ hình và chạy bằng tay) từ đó có thể xây dựng lại code!
Tricks trong trường hợp bí quá và sắp hết thời gian
1. Bài YES/NO thì in bừa.
2. Bài số lớn thì dùng java.
05 Thứ Năm Th3 2015
Posted ACM, Algorithms
inCho đơn đồ thị vô hướng N đỉnh và M cạnh, trọng số các cạnh đều nguyên dương. Có 2 loại câu hỏi :
0 u v : Cho biết đường đi ngắn nhất từ u tới v có độ dài là bao nhiêu.
1 u v : Hãy chỉ ra 1 đường đi ngắn nhất từ u => v
Bài cơ bản này nhằm kiểm tra kỹ năng xây dựng các module chương trình con dành cho truy vết 1 cách hợp lý, sử dụng nhuần nhuyễn chương trình con, lời gọi hàm .
Download test và solution tại đây
Dòng 1 : 3 số nguyên N , M , K . ( 1 ≤ N ≤ 100 , 1 ≤ M ≤ N*(N-1)/2 , 1 ≤ K ≤ 1000 )
M dòng tiếp theo , dòng thứ i gồm 3 số nguyên dương u , v , c cho biết cạnh (u,v) có trọng số là c ( 1 ≤ c ≤ 10000 )
K dòng tiếp theo là K câu hỏi , dòng thứ j sẽ có định dạng như đã nêu ở trên .
Ứng với mỗi câu hỏi trong K câu hỏi thì ta phải trả lời trên mỗi dòng như sau .
Câu hỏi 0 u v : Ghi ra 1 số nguyên duy nhất là độ dài đường đi ngắn nhất từ u -> v.
Câu hỏi 1 u v : Ghi ra số đầu tiên là số X là số đỉnh trên đường đi ngắn nhất này , tiếp đó ghi ra X số là chỉ số các đỉnh theo thứ tự xuất hiện trên hành trình .
Input: 3 3 2 1 2 3 2 3 1 1 3 5 0 1 2 1 1 3 Output: 3 3 1 2 3
02 Thứ Hai Th3 2015
Posted ACM
inThe Dole Queue |
In a serious attempt to downsize (reduce) the dole queue, The New National Green Labour Rhinoceros Party has decided on the following strategy. Every day all dole applicants will be placed in a large circle, facing inwards. Someone is arbitrarily (ngẫu nhiên) chosen as number 1, and the rest are numbered counter-clockwise (ngược chiều kim đồng hồ) up to N (who will be standing on 1’s left). Starting from 1 and moving counter-clockwise, one labour official counts off k applicants, while another official starts from N and moves clockwise (cùng chiều kim đồng hồ), counting m applicants. The two who are chosen are then sent off for retraining; if both officials pick the same person she (he) is sent off to become a politician. Each official then starts counting again at the next available person and the process continues until no-one is left. Note that the two victims (sorry, trainees) leave the ring simultaneously, so it is possible for one official to count a person already selected by the other official.
Tạm dịch:
Mỗi ngày, số người đến ăn xin sẽ được xếp vào một vòng tròn lớn, quay mặt vào trong.
Một người ngẫu nhiên sẽ được đánh số 1, tiếp đó đánh đến N theo chiều ngược kim đồng hồ.
Một nhân viên điếm k người ăn xin từ người số 1 theo chiều ngược chiều kim đồng hồ.
Nhân viên thứ 2 đếm m người ăn xin từ người số thứ N theo chiều kim đồng hồ.
2 người ăn xin kia được chọn sẽ được cử đi đào tạo lại, nếu là cùng 1 người thì người đó sẽ được đề cử làm chính trị gia.
Sau đó 2 người nhân viên tiếp tục công việc đó bắt đầu với người tiếp theo, cho đến khi ko con ai.
Chú ý rằng 2 người đen đủi bị đẩy ra khỏi vòng cùng 1 lúc vì vậy có khả năng người được nhân viên này đếm cũng chính là người mà nhân viên kia chọn
Write a program that will successively read in (in that order) the three numbers (N, k and m; k, m > 0, 0 < N < 20) and determine the order in which the applicants are sent off for retraining. Each set of three numbers will be on a separate line and the end of data will be signalled by three zeroes (0 0 0).
For each triplet, output a single line of numbers specifying the order in which people are chosen. Each number should be in a field of 3 characters. For pairs of numbers list the person chosen by the counter-clockwise official first. Separate successive pairs (or singletons) by commas (but there should not be a trailing comma).
10 4 3 0 0 0
4 8, 9 5, 3 1, 2 6, 10, 7
where represents a space.
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=69