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

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