1 năm, 1 tháng trước

Kỳ thi VOI 2016 đã kết thúc và chắc chắn là để lại nhiều kỉ niệm đau buồn trong lòng tất cả mọi người. Tuy vậy, gác quá khứ qua 1 bên, dù sao các bạn cũng gắn bó với môn Tin khá lâu rồi, tuy thọt lần này nhưng hi vọng các bạn vẫn đam mê môn Tin học, và đam mê giải bài. Hôm nay ta thọt nhưng ngày mai ta đứng lên sẽ mạnh mẽ và khủng khiếp hơn.

Nói tóm lại mình xin đi tiên phong tổng kết các thảo luận các bài VOI 2016:

Bài 1:

Nhận xét:

  • Có thể sort lại dãy
  • Có thể chọn tất cả các số bằng nhau.

Như vậy đầu tiên chúng ta có thuật N*2^10 hồn nhiên như sau:

  1. Sort lại, gộp các số bằng nhau lại thành 1.
  2. Đặt F(i, mask) = độ dài dãy lớn nhất nếu ta chọn các số từ A1 --> Ai, mask là dãy bit độ dài 10. Trong 10 số Ai, A(i-1), A(i-2)... thì ta chỉ chọn các số có trong mask. Gọi tập các số đc chọn trong 10 số đó là S(mask). Từ F(i, mask) ta tính đc F(i+1, mask'). Để kiểm tra thỏa mãn tính chất đề bài thì ở trạng thái (i+1, mask') cần xét xem có 2 số nào trong S(mask') mà có hiệu là 1, 8 hoặc 9 hay không.

Bài 2:

(Theo bạn bvd);

Nhận xét:

  • Cách vận chuyển tiết kiệm xăng nhất là vận chuyển toàn bộ lượng xăng có thể ở bể chứa trước đến bể chứa sau

Từ đó thu đc thuật toán với độ phức tạp L/D

Bài 3:

-_-

Bài 4:

Chia hình thoi thành 4 tam giác vuông.
F1(i, j) = độ dài cạnh lớn nhất của tam giác vuông có đỉnh góc vuông là (i, j) và 2 cạnh của nó hướng lên trên và sang trái.
Như vậy:

  • F1(i, j) = 0 nếu ô (i, j) và (i-1, j) hoặc (i, j-1) có cọc.
  • Ngược lại F1(i, j) = 1 + max(F1(i-1, j), F1(i,j-1))

Tương tự tính 4 tam giác 4 hướng: F1, F2, F3, F4.

Sau đó ở (i, j) thì hình thoi lớn nhất có tâm ở (i, j) là min(F1(i,j), F2(i,j), F3(i,j), F4(i,j))

Bài 5:

Với mỗi biểu thức sinh tất cả các giá trị có thể có ra. Sau đó làm cặp ghép.

Để ko phải xử lý số lớn thì cứ tính tràn số 64 bit. Nếu sợ sai thì tính thêm giá trị MOD 10^9 + 7.

Bài 6:

(Lời giải bởi Kiên IOI 2015)

Bài này có 2 bước:

  1. Với mỗi cây, cần tính xem là nếu nó đổ sang trái (hoặc sang phải), thì đổ đến tối đa là bao nhiêu. Đặt 2 cái này là Fright(i) và Fleft(i).
  2. Sau khi có Fleft(i) và Fright(i), xét 2*N đoạn: [Fleft(i), i] và [i, Fright(i)]. Bài toán đưa về chọn ra ít đoạn nhất sao cho phủ đc tất cả 1..N và ko có 2 đoạn nào có điểm chung (để tránh chọn cả 2 cái left và right của i).

Bước 1:

  • Với mỗi i, Fright(i) = max(Fright(i+1).. Fright(i+Hi)). 
  • Như vậy có thể tính đc bằng BIT hoặc IT --> O(N*logN)
  • Ngoài ra có thể tính O(N) dùng stack như sau:
    • Ở i ta duy trì 1 stack chứa tất cả các giá trị có thể dùng để cập nhật cho Fright(i).
    • Rõ ràng, nếu i < j và Fright(i) > Fright(j) thì j vô dụng, nên ta có thể vứt ra khỏi stack.
    • Như vậy, trong stack, nếu có i < j thì Fright(i) < Fright(j)
    • Ở i, đầu tiên loại những j ở đỉnh của stack, vừa loại vừa cập nhật Fright(i). Quá trình này dừng lại khi có Fright(i) < đỉnh stack < Fright(đỉnh stack). Cuối cùng ta thêm i vào stack, thì vẫn đảm bảo tính chất nêu trên.
    • Mỗi đỉnh vào stack và ra khỏi stack 1 lần, nên đpt là O(N).

Bước 2 thì các đoạn rời nhau, nên ta có thể QHD trong O(N) khá đơn giản.

1 năm, 1 tháng trước

Bạn Đức (Nghệ An) + Việt (IOI 2014) sẽ sinh test để add lên VOJ.

1 năm, 1 tháng trước
Trả lời khuebeo
  Hiện bài gốc

(comment hộ)

Lê Xuân Mạnh: 

Em thấy sol b6 có vẻ ko đúng khi chọn các đoạn phủ 1..N sao cho ko có 2 đoạn trùng nhau

Ví dụ 6 1 1 1 1 1 1 1 6 sol là đổ 2 con 6 về 2 phía

Nhưng 2 cái đoạn này giao nhau mà

1 năm, 1 tháng trước
Trả lời RR
  Hiện bài gốc

Uhm, như vậy mình đề xuất lại thuật N*log cho bước 2:

f(i) = số cây cần chặt nhỏ nhất để đổ hết từ i..N

Đặt u = Fright(i) + 1

Tìm v sao cho f(v) nhỏ nhất và Fleft(v) <= i. Đoạn này có thể dùng CTDL kiểu IT

f(i) = min(1 + f(u), 1 + f(v))

1 năm, 1 tháng trước
Trả lời RR
  Hiện bài gốc

Em nghĩ bài 4 lúc tính qhđ là phải tính min của hai bên chứ tại sao lại là max v anh.

1 năm, 1 tháng trước
Trả lời RR
  Hiện bài gốc

f(i) = số cây cần chặt nhỏ nhất để đổ hết từ i..N , nhưng lỡ như sau khi làm đổ các cấy i...n thì 1 số cây i-1,i-2,... cũng đổ theo thi sao anh

 

1 năm, 1 tháng trước

Em ôn đại học đây

1 năm, 1 tháng trước

Mình có một lời giải O(n^2) cho bài 4 như sau, mọi người thử xem:
Trước tiên ta có nhận xét với mỗi tâm (i, j), hình thoi ta xét đến luôn là hình thoi lớn nhất mà không chứa 2 cọc trùng cạnh.
Gọi f[i, j] là bán kính lớn nhất của hình thoi thỏa mãn ở tâm [i, j]. Dễ dàng nhận thấy f[i, 1] = 0. Ta có một nhận xét khác: |f[i, j] - f[i, j - 1]| <= 1. (Chứng minh cái này không khó, vẽ ra là thấy). 
Để kiểm tra f[i, j] = f[i, j - 1] - 1, f[i, j - 1] hay f[i, j - 1] + 1 trong O(1) ta có thể sử dụng các mảng cộng dồn đường chéo lưu số cọc có cọc chung cạnh bên trái và bên trên (tương tự như bài C Goodbye 2015). 
Khi đã có các f[i, j] mình có thể tịnh tiến và cộng trừ các mảng đường chéo để tính tổng ô các hình thoi trong O(1).

1 năm, 1 tháng trước

Trong giờ mình cài bài 3 tham như sau:

Lưu một set (cây nhị phân cân bằng)  S các đỉnh có Q[i] "có phần tử nhưng chưa đc khóa" và so sánh theo thứ tự:
 - Trước tiên là Q[i] theo thứ tự từ điển
 - Nếu Q[i] bằng nhau thì là bậc các cạnh chưa xét deg[i]
 - Nếu deg bằng nhau thì xét chỉ số gốc của 2 đỉnh (để đảm bảo 2 đỉnh không bị coi là bằng nhau thôi)
Đồng thời ta có một mảng ans[] trống. Khi bắt đầu thì S chứa 1.

Ta làm như sau:
while (S còn phần tử):
  lấy phần tử nhỏ nhất (theo phép so sánh trên) của S, gọi là u.
  đưa u vào mảng ans[]. "Khóa" Q[u]. Vị trí của u trong ans[] chính là đánh số mới của u.
  với mỗi cạnh (u, v) với v chưa "khóa":
    Nếu Q[v] rỗng ta thêm (đánh số mới của) u vào Q[v], giảm deg[v] đi 1 rồi thêm v vào S
    Nếu Q[v] không rỗng ta xóa v khỏi S, thêm (đánh số mới của) u vào Q[v], giảm deg[v] đi 1 rồi thêm lại v vào S

Với cách làm này các phần tử được đưa vào mảng ans[] sẽ có Q[] xếp theo thứ tự từ điển. Độ phức tạp là O(MNlogN) nên cố ăn 60% và cắn thêm mấy test random sub cuối :D còn nếu sol này đúng ta có thể cài mảng Q[] là IT hash động thì có thể hạ đpt xuống O(M log^2 N), chắc là ăn được sub cuối.

UPD: mình lấy sol này đưa vào trình sinh random của anh ladpro98 trên VNOI, chạy 10000 test đúng cả 10000. Có thể là nó đúng thật chăng?

1 năm, 1 tháng trước
https://onedrive.live.com/redir?page=view&resid=3C934227A4855802!72276&authkey=!AM56hZJf7eZbJ68

Lời giải của mình cho một số bài. Hi vọng không quá khó hiểu vì mình không có kinh nghiệm viết lời giải. Mong mọi người góp ý

1 năm, 1 tháng trước
Trả lời vuonghy2442
  Hiện bài gốc

cảm ơn

1 năm, 1 tháng trước
Trả lời anh
  Hiện bài gốc

Theo yêu cầu của đề là trong khu đất được chọn không có 2 cọc chung cạnh. Có nghĩa là phải xét tất cả không được bỏ bất kì cọc nào. Theo mình hiểu là vậy

1 năm, 1 tháng trước
Trả lời RR
  Hiện bài gốc

anh ơi cho em hỏi thuật toán của e như này thì có đúng ko ạ:

B1: Tạo 2 mảng trai[i] và phai[i] là đổ sang trái và phải xa nhất là bao nhiêu. ( bước này e dùng interval để tính).

B2: Em qhđ F[i] là số cây cần chặt nhỏ nhất đoạn từ 1 đến i.

  -Trường hợp 1: là có 1 cây đổ từ phải và làm đổ cây i thì ta chọn j sao cho f[j] nhỏ nhất và phai[j]>=i

  -Trường hợp 2: là cây i đổ sang trái thì f[i]:=min(f[i], f[trai[i]-1]+1).

Bước này em dùng BIT.

Thuật toán độ phức tạp O(n log n).

Thuật toán này có đúng ko ạ và nếu đúng thì ăn được khoảng mấy sub ạ ? Cảm ơn a.

 

1 năm, 1 tháng trước

anh oi? Bài 1 VOI em làm thế này dc không?Ban đầu sort dãy tăng dần rồi khởi Tạo mảng L[1..m] với mọi L[i]=1

tiếp theo ta qhd for i=1 đến m-1 

    for j=i+1 den m if (a[j]-a[i])<>(1,8,9) then L[j]=max(L[i]+1,L[j]);

kq la m-max(L[1..m]);

1 năm, 1 tháng trước
Trả lời gocholau156
  Hiện bài gốc

Ban dau e sort lai day tang dan

1 năm, 1 tháng trước

không biết bài 2 L có chia hết cho D không nhỉ?

1 năm, 1 tháng trước
Trả lời gocholau156
  Hiện bài gốc

Thuật của em chả có tí chặt chẽ nào về mặt Toán học cả, dĩ nhiên là sai rồi.

1 năm, 1 tháng trước
Trả lời RR
  Hiện bài gốc

Bài đốn cây :

Em nghĩ u phải là chưa chắc đã phải là Fright(i) + 1 mà phải chọn u sao cho f[u] nhỏ nhất và u trong khoảng  i + 1 <= u <=Fright(i) + 1 (cái này có thể dùng IT)

test 

10

8 1 1 1 1 1 4 1 1 1

upd : em hiểu sai đề :v

 

1 năm, 1 tháng trước
Trả lời RR
  Hiện bài gốc

Theo Lăng Trung Hiếu thì test này ra 2 là sai & cách của Kiên đúng, tất cả mọi người đều hiểu sai đề :))

(cây bị đổ theo chỉ đc đổ 1 hướng. Nếu 2 cây khác hướng cùng đổ vào nó --> nó bị đổ theo 2 hướng --> lỗi)

1 năm, 1 tháng trước
Trả lời RR
  Hiện bài gốc

Em nghĩ là ra 2 là đúng chứ ạ. việc đổ cây 4 sang phải xong thì làm gì con cây 4  1 1 1 1 nữa ạ. nên đổ 8 sang phải tiếp đc chứ ạ :)). em nghĩ thế :))