NGÀY THỨ NHẤT
Bài 1 : BCHESS
Ý tưởng bài này bắt nguồn từ bài QBSQUARE
Ta cần tính hình vuông lớn nhất giống bàn cờ (0 1 xen kẽ) và số lượng hình vuông như vậy với tính chất
- độ dài chẵn
- độ dài lẻ, góc phải dưới là 0
- độ dài lẻ, góc phải dưới là 1
Gọi F[i,j] và G[i,j] là độ dài hình vuông lớn nhất có góc phải dưới ở ô [i,j] lần lượt với A[i,j]=0 và A[i,j]=1.
Nếu A[i,j] = 0 thì
- G[i,j]=0
- F[i,j]=min(F[i-1,j-1],G[i-1,j],G[i,j-1])+1
Tính tương tự với A[i,j]=1.
Duyệt hết bảng, mỗi lần tính được F[i,j], G[i,j] ta cập nhật vào kết quả. Lưu ý cần cập nhật cho cả độ dài chẵn và độ dài lẻ.
Độ phức tập : O(M*N). Có thể chỉ dùng 1 mảng F[i,j] là độ dài hình vuông lớn nhất có góc phải dưới ở ô [i,j] nhưng phần xét sẽ phức tạp hơn 1 chút.

Bài 2 : DGOLD
Đây là một bài liên quan đến bitmask và chia thành 2 tập con.
Solution 1 : Xem mỗi bit biểu hiện một cách chọn (bit k = 1 nghĩa là có chọn thỏi vàng k+1). F[i] = tổng khối lượng vàng nếu chọn theo dãy bit i.
Duyệt 2^N dãy bit. Với dãy i duyệt các dãy con j của i (i or j = i) Nếu F[i] = F[j] * 2 thì cập nhật F[j] vào kết quả.
Cách duyệt nhanh các dãy bit con của dãy bit S (kể cả S và 0 )
A = S;
while (A>0)
begin
A = S and A; -> lúc này A là dãy bit con của S, dùng A để tính toán
A = A – 1;
end;
Độ phức tập : thoạt nhiên tưởng lả (2^N)^2 = 4^N nhưng trên thực tế chỉ là 3^N (có thể chứng minh bằng toán hoặc viết chương trình vét trâu) => ăn được trên 50% số điểm.
Solution 2 : Giả sử với N=24
Chia 12 thỏi vàng đầu vào tập 1 và 12 thỏi cuối vào tập 2. Ta cần chọn A và C gam trong tập 1, B và D gam trong tập 2 sao cho :
A + B = C +D <=> A – C = D – B = K => A + B = C + D = A + D – K;
Với tập 1, ta xét tất cả các cách chọn A và C biểu diễn bằng dãy H trong cơ số 3.
- H[i]=1 : chọn thỏi i vào A
- H[i]=2 : chọn thỏi i vào C
- H[i]=0 : không chọn
Có tất cả 3^12 cấu hình -> lưu 3^12 phần tử vào 1 mảng F[i] gồm 2 giá trị x và y
F[i].x = abs (A[i]-C[i])
F[i].y = max ( A[i],C[i] )
Nếu F[i].x = F[j].x ta chỉ cần lưu lại F[i] nếu F[i].y > F[j].y
Tương tự ta tạo mảng G từ 12 thỏi cuối cùng.
Sort lại F và G theo chiều tăng dần của x. Giờ ta duyệt kiếm tất cả các cặp i, j mà F[i].x = G[j].x
Mỗi lần tìm được 1 cặp i,j ta cập nhật ( F[i].y + G[j].y – F[i].x ) cho kết quả.
Độ phức tạp : (3^12) * log (3^12) => ăn 100% số điểm.
Nhận xét : bài này để ăn 100% thì khá khoai nhưng trên 50% thì hoàn toàn dễ dàng .

Bài 3 : NSRAIL
Nhận xét 1 : ta có thể bỏ đi chiều từ Nam-Bắc bằng cách đặt A[i,j] = A[i,j] + A[j,i] với i>j.
Thay vì kiếm số khách được ăn nhiều nhất ta có thể tiếp cận bài toán dễ dàng hơn nếu tính số khách không được ăn ít nhất.
Gọi dãy X = (x0, x1, x2, ... , xm, xm+1) là 1 cách chọn cách đặt trạm ăn. Mặc định có 1 trạm ăn đặt trước ga 1 (x0=0) và 1 trạm đặt sau ga N (xm+1 = n).
Nhận xét 2 : Chỉ có các khách lên tàu ở ga y1 > xi và ở ga y2 <= xi+1 mới không có phiếu ăn. Ta tính mảng B[i,j] = tổng các A[y1, y2] với i <= y1 <= y2 <= j. Mảng B có thể tính bằng QHĐ nhanh chóng trong O(N^3) : B[i,j] = B[i,j-1] + A[k,j] với (i <= k < j). Có thể cải tiến thành O(N^2) bằng cách tính trước A[k,j] trong O(N^2)
Tìm dãy X sao cho tổng các B[xi+1, xi+1] nhỏ nhất. Gọi mản F[i,j] = kết quả tối ưu khi đã chọn xong j trạm ăn trong i ga đầu tiên. Công thức QHĐ :
F[i,j] = min (F[k,j-1] + B[k+1,j]) với (1 <= k < i)

NGÀY THỨ HAI
Bài 1 : SDRIVE
Một bài QHĐ. Giả sử có M làn đường đánh số từ trái qua phải (theo hướng ban đầu là đi lên chả hạn). Gọi F[i,j] là độ dài quãng đường ngắn nhất khi đã đi đến i đoạn đường đầu tiên và đang đứng ở chính giữa làn đường thứ j.
Nếu Li = 0 thì F[i,j] = min(F[i-1,k] + Dk,j) với Dk,j = sqrt (Si + (j-k)*10 ) là độ dài đường thẳng từ chính giữa làn đường k đến làn đường j trên đoạn đường thẳng i. Lưu ý là abs(k-j) <= Si / 100.
Nếu Li > 0 thì F[i,j] = F[i-1,j] + Rj với Rj là độ dài cung tròn thứ j ở khúc quẹo i ( = ¼ chu vi đường tròn thứ j). Nếu Li = 1 thì các cung tròn lớn dần từ 1->M còn Li = 2 thì các cung tròn nhỏ dần từ 1->M.
Kết quả là min(F[N,i]) với 1<= i <= M.
Độ phức tạp : O(N*M^2) => ăn 100% số điểm. Một số ít bạn cài Djikstra nhưng thực ra vậy phức tạp và tốn công hơn rất nhiều :P.

Bài 2 : JUPI
Là bài toán đếm số đường đi ngắn nhất trên đồ thị. Bài tham khảo : QBSCHOOL http://vn.spoj.com/problems/QBSCHOOL/
Trong bài này chỉ cần cài đặt BFS. Một đỉnh u được kí hiệu bởi 3 tham số :
x : tọa độ dòng
y : tọa độ cột
z : hướng hiện tại. Quy định z=0,1,2,3 tương ứng với hướng N,W,S,E.
Từ đỉnh u(x,y,z) có cạnh nối đến đỉnh v1(x’,y,z), v2(x,y’,z), v3(x,y,z-1), v4 (x,y,z+1).
Gọi D[u] và Q[u] là độ dài đường đi ngắn nhất từ đỉnh ban đầu st đến đỉnh u. Nếu có cạnh nối từ u đến v và D[v] >= D[u]+1 thì cập nhật :
D[v] > D[u]+1 then S[v] = S[u] else S[v] = S[v] + S[u];
D[v] = D[u]+1;
Có M*N*4 đỉnh. Mỗi đỉnh tối đa (M+N) cạnh
=> Độ phức tạp M*N*(M+4)*4. Để ăn 100% số điểm cần cài thêm xử lý số lớn (bignum), thật ra rất nhanh chóng nếu dùng operator trong PASCAL hoặc C++.

Bài 3 : SUBD
Nhận xét : với N=1 thì đây chính là bài CAR : http://vn.spoj.com/problems/CAR/
Giả sử trong trình tự viết tốt nhất, 2 report 1 và 2 được làm kế nhau và làm report 1 trước lợi hơn về thời gian. Ta chỉ cần so sánh a1*t1 + a2*(t1+t2) < a2*t2 + a1*(t1+t2) do nếu đổi chỗ 1 và 2 cũng không ảnh hưởng đến thời gian của các report được viết trước 1,2 và sau 1,2.
<=> a2*t1 < a1*t2 <=> t1/a1 < t2/a2.
Vậy cách sắp xếp tốt nhất là t[i]/a[i] tăng dần (nếu t[i]/a[i]=t[j]/a[j] thì sắp theo thứ tự xuất hiện).
Với N>1, ta nhận thấy thứ tự các report trong 1 môn vẫn phải đảm bảo tính chất trên (viết công thức tổng quát ra sẽ thấy ). Ta chỉ cần chọn trình tự viết của môn.
Xét môn thứ i được viết. Ta nhận thấy thời gian viết của tất cả các report j của môn này sẽ tăng thêm 1 lượng = tổng thời gian viết các môn trước i. Tính trước kết quả = tổng thời gian viết report của môn i nếu viết môn i đầu tiên (i từ 1->N) như sau
kq=0;
foru i:=1 to n do
begin
sumt=0;
for j:=1 to Mi do
begin
sumt:=sumt+t[i,j];
kq:= kq + sumt * a[i,j];
end;
end;
Ta thay thế B[i].t = t[i,1] + t[i,2] + ... t[i,Mi] và B[i].a = = a[i,1] +at[i,2] + ... a[i,Mi]. Sắp xếp dãy B theo tăng dần của t/a. Duyệt như sau :
sumt=0;
for i:=1 to n do
begin
kq := kq + sumt * b[i].a;
sumt = sumt + b[i].t;
end;
Độ phức tạp : O(P*log(P)) với P là tổng số report của N môn. Để ăn 100% số điểm bài này cũng cần cài đạt bignum .

CHo e hỏi bài SUBD nếu không cài bignum thì tối đa được bao nhiêu điểm ạ, em cảm ơn ạ.

meodorewan viết:

QUOTE:
CHo e hỏi bài SUBD nếu không cài bignum thì tối đa được bao nhiêu điểm ạ, em cảm ơn ạ.

Hình như là 60 mình k để ý bignum nộp toàn 60 k hiểu tại sao lol

thanks anh winterwolf94 vì 2 đợt contest vừa rồi, nhận ra mình còn nhiều thứ sai sót, thiếu sót quá!!!! mong là thi quốc gia có thể rút kinh nghiệm để không mắc phải nữa
P/S: sau anh up solution thì 6 bài up 6 post cộng điểm cho thích :P

Anh winterwolf94 có thể cho em hỏi bài DGOLD của em chưa AC vì WA hay TLE không ạ????

Code:

ID mã code : 8425072

Thanks anh ^^

vodanh9x viết:

QUOTE:
thanks anh winterwolf94 vì 2 đợt contest vừa rồi, nhận ra mình còn nhiều thứ sai sót, thiếu sót quá!!!! mong là thi quốc gia có thể rút kinh nghiệm để không mắc phải nữa :D
P/S: sau anh up solution thì 6 bài up 6 post cộng điểm cho thích :P

em kiếm mấy post cũ của anh cộng điểm cho anh đi vậy

loiprovd123 viết:

QUOTE:
Anh winterwolf94 có thể cho em hỏi bài DGOLD của em chưa AC vì WA hay TLE không ạ????

Code:

ID mã code : 8425072

Thanks anh ^^

TLE em ạ.

Bài JUPI mình làm như sau:
Gọi
- F[x,y] là số câu lệnh tối thiểu để đi từ ô bắt đầu đến ô (x,y).
- G[x,y] là số cách để đi đến ô (x,y) qua F[x,y] bước.

Và mình thấy có một điều như sau:
- Từ một hướng, nếu muốn đổi sang hướng khác thì cần thêm 2 lệnh và số cách sẽ bằng số cách ở ô đó nhân thêm 2. Ví dụ đang di chuyển từ ô (x1+k,y1) đến ô (x1,y1) (di chuyển theo hướng Bắc), khi đến ô (x1,y1) muốn đổi hướng đi sang các ô bên hướng Đông (x1,y1+k) thì F[x1,y1+k]=F[x1,y1]+2 và G[x1,y1+k]=G[x1,y1]*2.

Từ đó dễ dàng thấy bài toán trở về bài toán loang trên ma trận đơn giản và chỉ phụ thuộc vào hướng ban đầu.