KEBA2 - Kết bạn (OLP Không chuyên 2009)

Theo quan niệm của người Á Đông cổ, mỗi cá nhân khi sinh ra đều ứng với một ngôi sao, được gọi là sao chiếu mệnh. Các hoạt động của cá nhân đều bị chi phối bởi ngôi sao này, kể cả quá trình kết bạn – hẹn hò. Theo thuyết Âm dương – Ngũ hành, hai người chỉ có thể tạo lập mối quan hệ bền vững khi các sao chiếu mệnh của họ không có các thuộc tính tương khắc. Qua hàng nghìn năm quan sát và chiêm nghiệm, các chiêm tinh gia đã ghi nhận được n sao và hầu hết các tính chất tương sinh – tương khắc giữa chúng. Để có thể nhanh chóng đáp ứng nhu cầu kiểm tra độ tương hợp của các sao, hiệp hội ABS (Association of Broker for Single) tạo lập cơ sở dữ liệu ghi nhận tính chất của tất cả các sao đã khảo sát được. Trong cơ sở dữ liệu này, các sao được đánh số từ 1 tới n; sao thứ i có một giá trị s_i thể hiện khả năng thích nghi của sao gọi là độ thích nghi. Hai sao khác nhau có thể có cùng độ thích nghi. Thông qua độ thích nghi của các sao, người ta xác định khả năng tương hợp của chúng. Khả năng tương hợp của 2 sao được tính bằng tổng 2 độ thích nghi của chúng.

Bài toán: Cho số nguyên dương n, dãy s₁, s₂, …, s_n là độ thích nghi của các sao và số nguyên B. Hãy xác định số lượng T các cặp sao (i, j) mà s_i + s_j = B,với 1 ≤ i< j ≤ n.

Ví dụ: trong 5 sao với độ thích nghi là 3, 5, 6, 5, 3 thì có 4 cặp có khả năng tương hợp bằng 8.

Dữ liệu nhập:

- Dòng thứ nhất là hai số nguyên n và B (2 ≤ n ≤ 10⁵, |B| ≤ 10⁹).

- Dòng thứ hai là n số nguyên s₁, s₂, …, s_n  mỗi số cách nhau một khoảng trắng (|s_i| ≤ 10¹⁵)

Dữ liệu xuất:

- Là số nguyên T.

Ví dụ

• input
  5 8
  3 5 6 5 3
  output
  4

Lần 1:

Đương nhiên là cách đầu tiên nghĩ đến sẽ là duyệt i, j tìm ra bộ phù hợp rồi!

Nhưng như đã nó nói là O(n2), không mảy may có cơ hội AC với độ phức tạp này!

We have to find another way!

Chỉ đơn giản là dùng map để đếm số lượng B-a[i] trước nó là ra!

Code: http://ideone.com/VUUgzj
#namlunoy

AGAR - Agar.io

Giới hạn thời gian: 0.5 giây

Agar.io là một trò chơi nhiều người chơi tương tự như trò cá lớn nuốt cá bé vốn đã rất quen thuộc với trẻ em Việt Nam. Mục tiêu của trò chơi là tìm cách điểu khiển tế bào của mình ăn các tế bào khác để lớn hơn. Luật chơi đơn giản như sau:

 - Tế bào A (của người chơi A) có thể ăn tế bào B (của người chơi B) khi và chỉ khi kích thước của A lớn hơnB. Khi va chạm nếu A>B thì A ăn B, nếu A<B thì B ăn A.
 - Nếu A ăn B, kích thước của A sẽ tăng lên đúng bằng B.
 - Khi tế bào bị ăn, người chơi đó ngay lập tức bị thua cuộc.
 - Kích thước càng lớn thì di chuyển càng chậm.
 - Hai tế bào chỉ có thể ăn nhau khi chúng va chạm vào nhau.

--Ares-- vì muốn gây ấn tượng với bạn gái của mình rằng mình không chỉ giỏi lập trình mà còn chơi game giỏi nên đã quyết tâm thắng được Theghost2 là một đàn anh của --Ares-- và cũng đang là một trong những người chơi xuất sắc nhất hiện tại của trò chơi này. Nghĩ rằng tự mình khó có thể thắng được Theghost2 nên --Ares-- quyết định nhờ đến sự giúp đỡ của bạn mình. Cậu có N người bạn cùng chơi, kích thước thước hiện tại của N người bạn trên là S₁, S₂, ..., S_N. Một số người bạn sẽ hy sinh va chạm với Ares để --Ares-- trở nên lớn hơn và sau đó --Ares-- ăn được Theghost2. Mặc dù các bạn của --Ares-- rất tốt và sẵn sàng giúp đỡ bạn bè nhưng chắc chắn chẳng ai vui vẻ gì khi thấy mình thua cuộc cả nên --Ares-- muốn ăn càng ít bạn càng tốt. Hãy giúp --Ares-- tính xem cậu ta cần ăn ít nhất bao nhiêu người bạn để sau đó chiến thắng Theghost2 nhé.

Dữ liệu nhập:

 - Dòng đầu tiên chứa 3 số nguyên dương N, A, G (N ≤ 10⁵, 1 ≤ A ≤ 10⁹, 1 ≤ G ≤ 2*10⁹) lần lượt là số bạn của --Ares--, kích thước hiện tại của --Ares-- và kích thước hiện tại của Theghost2.

- Dòng thứ hai chứa N số nguyên dương S₁, S₂,..., S_N (1 ≤ S_i ≤ 10⁹).

Dữ liệu xuất:

- Nếu không có cách để ăn được Theghost2, in ra -1.

- Nếu có cách để ăn được Theghost2:
   + Dòng đầu tiên là số nguyên K - số lượng người bạn ít nhất mà --Ares-- cần phải ăn.
   + Nếu K > 0, dòng thứ hai là K số nguyên là chỉ số của những người bạn được chọn để --Ares-- ăn đúng theo thứ tự (người bị ăn trước xuất trước), mỗi số cách nhau một khoảng trắng. Nếu có nhiều cách ăn, chỉ cần in ra một cách bất kỳ.

Ví dụ

• input
  3 10 15
  1 5 10
  output
  2
  2 3
• input
  7 15 1000
  1 2 3 4 5 6 7
  output
  -1

Trong test 1, kích thước của --Ares-- lần lượt là 10 -> 15 ->  25, lúc này ăn được Theghost2 (kích thước 15)

Lần 1:

*Đặc điểm:
- n = 10^5.

* Ý tưởng đầu tiên:

- Thì theo lỗi suy nghĩ thông thường thôi, đầu tiên là sắp xếp theo kích thước của dãy a (nlogn), sau đó mỗi lần duyệt B-search, tìm ra phần tử lớn nhất nhỏ hơn A lúc hiện tại và loại bỏ nó ra khỏi danh sách (logn)!

* Chú ý:

Cái cần chú ý ở đây là cấu trúc dữ liệu sử dụng phải có đặc điểm sau đây:

- Hỗ trợ random access: tức là có khả năng truy cập tức thì vào phần từ thứ i của mảng. (a[i])

- Có khả năng remove một phần tử trong mảng

=> Sau khi điều tra thì có kiểu deque phù hợp với miêu tả.

*Test:

Code: http://ideone.com/JY0oyy

Bị TLE ở test số 28.

Lần 2: 

* Review:

Như vậy là cách 1 đã bị TLE ở đâu đó.

* Sau khi đi tham khảo bài làm của các bạn, thì mọi người chủ yếu tìm cách xử lý tinh tế chỗ sử dụng B-search để tìm kiếm và cách remove phần tử đã tìm được trước đó.

* Sau khi được gọi ý là sử dụng Stack thì cũng biết cách làm thì ra nó cũng dễ!

- 1 stack tên smaller: chuyên chứa các phần tử nhỏ hơn A theo thứ tự từ nhỏ đến lớn, mà đỉnh của nó là phần tử lớn nhất.

- 1 stack tên bigger: chuyên chứa các phần tử lớn hơn A cũng theo thứ tự, mà đỉnh của nó là phần tử nhỏ nhất.

-> Tức là ta đã chia dãy a thành 2 stack, 1 cái nhỏ hơn và 1 cái lớn hơn.

Công việc của chúng ta như sau:

- Chừng này đỉnh của dãy smaller vẫn còn nhỏ hơn A và smaller ko bị rỗng, tức là A vẫn còn có cái có thể ăn được.

- Lúc đó A sẽ ăn đỉnh của smaller.

- Sau khi ăn xong, vì giá trị của A bị thay đổi nên phải chuyển hết cách phần tử từ bigger có size nhỏ hơn A sang smaller theo đúng thứ tự đã quy định.

- Cứ như thế cho đến khi A > B hoặc A không thể ăn gì trong smaller nữa!

Code: http://ideone.com/wGJzmX

Bài học:

- Ôn tập lại cách viết B-search (cách ra điều kiện tìm thấy)

- Biết thêm một số kiểu dữ liệu mới (deque,priority_queue)

- Nhớ đến việc sử dụng stack trong trường hợp cần chia một dãy sắp xếp thành 2 dãy, theo một tiêu chí nào đấy.

#namlunoy

DAYSO7 - Dãy số (OLP Không chuyên 2014)

(Giới hạn thời gian: 2.0 giây)

Cho dãy số gồm n số nguyên a₁, a₂, …, a_n. Một đoạn con của dãy đã cho là dãy a_i, a_i+1, …, a_j (1 ≤ i ≤ j ≤ n), dãy có độ dài (j − i + 1) và có trọng số bằng tổng (a_i + a_i+1 + …+ a_j).

Yêu cầu: Tìm hai đoạn con không có phần tử chung, mỗi đoạn có độ dài là một số chia hết cho 3 và tổng trọng số của hai đoạn con là lớn nhất.

Dữ liệu nhập:

- Dòng thứ nhất là số nguyên n (6 ≤ n ≤ 2 x 10⁵).

- Dòng thứ hai là n số nguyên a₁, a₂, …, a_n (|a_i| ≤ 10⁹), mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất:

- Là tổng trọng số của hai đoạn con tìm được.

Ví dụ

• input
  11
  -1 3 -1 -9 -1 1 1 1 1 1 -9
  output
  5

Hai đoạn có tổng lớn nhất là (-1, 3, -1) và (-1, 1, 1, 1, 1, 1)

Lần 1:

* Đặc điểm:

- Dãy con liên tiếp có số phần tử chia hết cho 3 => Sử dụng phương pháp chuyển về tổng 3 số liên tiếp như bài trước.

- Tìm 2 dãy con như vậy.

- n = 10^5 : mà giới gian thời gian 2s => Có thể chấp nhận thuật toán O(n2)

- Đề bài yêu cầu tìm tổng 2 dãy con.

* Ý tưởng ban đầu:

- Tìm T1[i] là tổng lớn nhất dãy con từ đầu đến chứa bộ con t3[i] : O(n)

- Tìm T2[i] là tổng lớn nhất dãy con từ cuối đến chứa bộ con t3[i] : O(n)

- Kết quả cần tìm là max(T[i] + T[j]) với i<j : O(n2)

Let's try! Ăn được đến test 26, như vậy tức là thuật toán đúng, nhưng chưa tối ưu.

Code: http://ideone.com/yTUIIj

Lần 2:

Phần duy nhất chiếm O(n2) chính là phần tìm ra bộ (i<j) max.

Như các bài trước ta đã biết cách để xử lý bài toán tìm bộ (i,j) max này rồi, đó là:

Đầu tiên là tìm fimax[i] = max(0->i) sau đó đi duyệt với j trên fimax đã tính trước đó!

Áp dùng bài toán này!

T1[i] của ta đang có là MAX chưa bộ t3[i], giờ ta tìm T1MAX[i] là tổng lớn nhất tính từ 0->i.

T1MAX[i] = max(T1MAX[i-1],T1[i]); : O(n)

Sau đó, duyệt j trêm T1MAX

kq = max(T1MAX[i] + T2[j]) với i<j : O(n)

*Chú ý: Trong lúc làm bài này sai 2 lần ở chỗ khởi tạo giá trị cho các biến ban đầu của mảng t3, và T1 và T1MAX, giá trị đầu tiên của chúng bắt đầu từ phần tử số 3 (i=2), và khi duyệt chúng ta duyệt bắt đầu từ phần tử thứ 4 (i=3)

Code AC: http://ideone.com/vAuoE8

Bài học:
- Cho dù là thời gian có cho đến 2s, nhưng với n = 10^5 cũng không thể chơi với O(n2) được.
- Kỹ thuật tìm bộ MAX của bộ (i,j) là một kỹ thuật khá quan trọng, vì chủ yếu O(n2) sẽ rơi vào trường hợp này.
- Một lần nữa ôn lại bài toán dãy số có số lượng phần tử chia hết cho 3.

#namlunoy

Các dạng bài toán thường gặp

Mathematics	Prime Number	Số nguyên tố
	Big Integer	Số lớn
	Permutation	Hoán vị, tổ hợp
	Number Theory
	Factorial	Giai thừa
	Fibonacci
	Sequences	Chuỗi ,  trình tự
	Modulus
Dynamic Programming (Quy hoạch động)	Longest Common Subsequence	Dãy con chung dài nhất
	Longest Increasing Subsequence	Dãy con tăng dài nhất
	Edit Distance	Sửa khoảng cách
	0/1 Knapsack
	Coin Change
	Matrix Chain Multiplication
	Max Interval Sum	Tìm .. lớn nhất
Graph (Đồ thị)	Traversal	Duyệt cây
	Flood Fill	Tô màu
	Floyed Warshal	Tìm đường đi ngắn nhất trong đồ thị có hướng
	MST
	Max Bipertite Matching
	Network Flow
	Aritculation Point
Sorting	-          Bubble Sort -          Quick Sort -          Merge Sort (DAndC) -          Selection Sort -          Radix Sort -          Bucket Sort
Searching	-          Complete Search, Brute Force -          Binary Search (DAndC) -          BST
Simulation	Josephus
String Processing	-          String Matching -          Pattern Matching
Computational Geometry (Hình học)	Convex Hull
AdHoc	Trivial Problems	Mỗi vấn đề 1 kiểu

TITO2 - Tính tổng 2 (OLP Không Chuyên 2014)

Viết chương trình đọc vào hai số thực dương  a và b và tính tổng bình phương tất cả các số
nguyên không nhỏ hơn a và không lớn hơn b.
Dữ liệu nhập: Gồm một dòng chứa hai số thực dương a, b (0 < a  ≤ b ≤ 10⁹)
Dữ liệu xuất: Một số nguyên nhất là phần dư của S chia cho 10⁹+7, trong đó S là tổng cần tìm

Ví dụ

• input
  0.3 2.89
  output
  5

Sẽ có 10 bộ test, tỉ lệ tương ứng với kì thi OLP

 - 5 bộ test đầu có 0 < a ≤ b ≤ 1000

 - 5 bộ test sau có 0 < a ≤ b ≤ 10⁹

^{Nộp bài}

Lần 1:

Bài này thuộc dạng toán học

Cách làm bình thường chỉ ăn được nửa điểm kia thôi!

Code: http://ideone.com/qpBnHG

Lần 2: copied
Sau khi search thì thấy có công thức tính tổng bình phương từ 1 đến n: n(n+1)(2n+1)/6

Kết hợp với xem bài giải của các bạn ta có: Đặt F(n) = n(n+1)(2n+1)/6

Như vậy kết quả bài toán sẽ là F(b) - F(a) % M

Nhưng thế này chỉ đúng thêm 1 test thứ 6 và sai ở test thứ 7. Do vẫn dính phải việc tràn số do số quá lớn.

Code: http://ideone.com/AAOC77

Lần 3: copied

Mặt khác, ta thấy: n(n+1) luôn chia hết cho 2 (vì 1 trong 2 số phải là số chẵn).

Do đó F(n) = [n*(n+1)/2]*(2*n+1)/3 : Tức là vừa nhân, ta vừa chia để giảm kết quả đến nhỏ nhất có thể, nếu nhân 2 lần liên tiếp rồi mới chia kết quả có thể tràn số.

Kết hợp cả công thức tính phần dư nữa ta được:

F(n) = n*(n+1)/2%M*(2*n+1)/3

Tức là ta vừa chia vừa lấy phần dư để kết quả nhỏ nhất có thể.

Và một chú ý khi lấy phần dư nữa là kết quả có thể F(b) < F(a) do đó phải tính đến trường hợp đấy.

Code: http://ideone.com/3gyNmz

Bài học: Có thể không nghĩ ra được cách giải đúng, nhưng với cách giải hiện tại phải tìm mọi cách để tối ưu bài toán, ví dụ ở trên ngta làm thêm từng bước nhỏ để giảm nhỏ tối thiểu kết quả của phép nhân.
^#namlunoy

DAYSO6 - Dãy số (OLP Không chuyên 2009)

Cho dãy số gồm n số nguyên a₁, a₂, …, a_n. Tìm giá trị lớn nhất của hàm f(i, j, k) = a_i + 2×a_j + 3×a_k với 1≤ i < j < k ≤ n.
Ví dụ: với dãy gồm 5 số -1, 2, -2, -3, 5 thì f(1, 2, 5)= -1 + 2×2 + 3×5 = 18 là lớn nhất.

Dữ liệu nhập:

- Dòng thứ nhất là số nguyên n (3 ≤ n ≤ 10⁵).

- Dòng thứ hai là n số nguyên a₁, a₂, …, a_n  mỗi số cách nhau một khoảng trắng (|a_i| ≤ 10⁹)

Dữ liệu xuất:

- Là giá trị lớn nhất của hàm f(i, j, k) tìm được.

Ví dụ

• input
  5
  -1 2 -2 -3 5
  output
  18

Nộp bài

Lần 1:
- Liệt kê ra các đặc điểm:
   +) 3 số có thứ tự trước sau i<j<k
   +) n^5 nên thuật toán O(n^2) ko được
   +) Để f(i,j,k) có giá trị lớn nhất thì a[k] > a[j] > a[i] càng tốt.

=> Bài toán có thể quy về tìm bộ i<j<k sao cho a[i] < a[j] < a[k]. Tức là một dãy tăng dần.
Xuất hiện yếu tố tăng dần => Thử nghĩ xem kỹ thuật sắp xếp có áp dùng gì vào được bài toán này không?

Giả sử nếu áp dụng thuật toán sắp xếp, lúc này ta có một dãy tăng dần.
Lúc này ta cần tìm từ cuối dãy trở về lấy bộ 3 có chỉ số giảm dần là được?

=> Đã thử và sai ngay ở test #3 
Code: https://ideone.com/aCki1o

Xem lại test...

Input

5
5 4 3 2 1

Output

15

Đáp án

22

Như vậy nếu như phần tử đầu tiên là phần tử lớn nhất thì, khi sắp xếp nó sẽ xuống cuối , và khi tìm ngược về sẽ không có phần tử nào có chỉ số nhỏ hơn nó cả, tức là không đủ 3 số!
Như vậy đây là sai sót do kỹ thuật, chưa làm được đúng theo như ban đầu đã yêu cầu!

=> Đổi về tên bài toán như thế này sẽ dễ làm hơn: (Giả sử đã sắp xếp xong) Duyệt từ đầu đến cuối, tìm bộ 3 phần tử phía cuối cùng có chỉ số tăng!
=> Nhưng vẫn có trường hợp không có, do nếu dãy ban đầu là giảm dần, và khi sắp xếp nó lại thành tăng dần, và không thể tìm ra một bộ nào có chỉ số tăng cả!

5 tiếng sau...
Do thời gian có hạn nên đành chuyển sang việc nhìn đáp án để tiết kiệm thời gian, vì thời gian không còn nhiều!

Lần 2: [copied]
Do mục tiêu trong thời gian này làm xem nhiều bài nhất có thể nên, xin phép được sử dụng cách giải quyết của các bạn khác trong phần này!

Ta có 3 hàm f,g,h, trong đó:
f[i] = max(a[1]....a[i]) : Giá trị lớn nhât từ a[1] đến a[i].
g[i] = max(2*a[i] + f[j<i]) : Giái trị lớn nhất trước đó của f() + 2*a[i]. Tức là kết quả của bài toán tìm max cho biêu thức F = a[i] + 2*a[j] với i < j.
h[i] = max(3*[i] + g[j<i]) : Giá trị lớn nhất trước đó của g() + 3*a[i]. Tức là kết quả của bài toán tìm max cho biểu thức F = g() + 3*a[i] = f() + 2*a[j] + 3*a[i] = a[k] + 2*a[j] + 3*a[i].

Như vậy, bài toán giải bằng cách quy về bài toán nhỏ hơn là tìm max cho biểu thức F = a[i] + 2*a[j] với i<j.

=> Công việc chỉ là xây dựng các hàm f,g,h và kết quả chính là h[n].
Code: http://ideone.com/pk36t5

#namlunoy

DAYSO2 - Dãy số 2 (OLPCĐ 2014)

Cho dãy số gồm n số nguyên a₁, a₂, ..., a_n. Một đoạn con của dãy đã cho là dãy a_i,..., a_j (1 ≤ i ≤ j ≤ n), dãy có độ dài (j - i + 1) và có trọng số bằng tổng (a_i + ... + a_j).

Yêu cầu: Tìm đoạn con có độ dài là một số chia hết cho 3 và có trọng số lớn nhất.

Dữ liệu nhập:

- Dòng đầu ghi số nguyên n (3 ≤ n ≤ 100.000).

- Dòng thứ hai ghi n số nguyên a₁, a₂, ..., a_n (|a_i| < 10⁹).

Dữ liệu xuất:

- Giá trị trọng số của đoạn con tìm dược.

Ví dụ

• input
  11
  1 1 1 -9 1 1 1 1 -1 1 -9
  output
  4
• input
  3
  1 2 3
  output
  6
• input
  4
  -1 5 -10 1
  output
  -4

Nộp bài

Lần 1:

Hoạt đầu nhìn có vẻ dễ, và cách đầu tiên nghĩ đến là đặt T[i] là tổng từ a[0] tới a[i], tổng từ a[i] đến a[j] chính là T[j] - T[i-1].
Nhưng cách này độ phức tạp vẫn là O(n^2) vì phải duyệt i và j để tính theo cặp!
Mặt khác n = 10^5 => Độ phức tạp ko để n^2 được.

Thực nghiệm chạy theo cách này sẽ bị TLE tại test 27!
Code: http://ideone.com/a85pBF

Lần 2: [copied]
Sau khi đi đọc bài giải của các bạn khác thì đã biết được cách làm! 
Như vậy là trong bài này cần thêm một mẹo nhỏ!
Nhớ lại cách trên thì việc mất thời gian nhất là duyệt 2 vòng for để tìm ra cặp (i,j) phù hợp!

Dựa vào yêu cầu đề bài là dãy này là dãy con liên tiếp và có số phần tử chia hết cho 3 ta có một số nhận xét như sau:
==> Dãy con này có số lượng phần tử chia hết cho 3 => Nó là tổng của các dãy con liên tiếp có 3 phần tử. Ví dụ: [1,6] = [1,3] + [4,6]

Từ nhận xét trên ta đi đến phương án QHĐ mới như sau:
Gọi t3[i] là tổng của 3 phần tử liên tiếp t3[i] = a[i] + a[i-1] + a[i-2].
Gọi T[i] là tổng lớn nhất của dãy con liên tiếp có số phần tử chia hết cho 3.
Như vậy kết quả cần tìm là max(T[i]).

(Note: ở đây ta đánh số từ 1 cho nó thuận miệng!)*Cơ sở QHĐ
- Dãy t3 đã được tính.
- T[1] = 0, T[2] = 0 (Do số lượng phần tử của nó chưa đủ), T[3] = t3[3] = a[1] + a[2] + a[3].

* Thử tiếp để ra công thức:
Vậy với T[4] = t3[4] (tổng liên tiếp 4-3-2) + T[4-3 = 1] (T[1] : tổng lớn nhất của bộ tìm được trước đó) 

*Công thức truy hồi: T[i] = max(t3[i], t3[i] + T[i-3])

Code [AC] : http://ideone.com/qe9igU

Bài học:
Bài học lần này là, kết quả quy hoạch động ko nhất thiết phải dựa vòa thằng trước nó, mà có thể dựa vào kết quả trước đó vài bước, và 1 phần tử có thể biểu diễn kết quả của một số phần tử trước đó chứ không phải tất cả!

Cần tập trung phân tích vào những dữ kiện đặc biệt của bài toán!

#namlunoy