Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
De Contest 2 - Solutions (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 6
CHỦ ĐỀ - De Contest 2 - Solutions
#69747
winterwolf94 (Thành viên)
winterwolf94+34
Biết code binary-indexed tree
Bài viết: 42
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
De Contest 2 - Solutions 8 năm trước   (+3)
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)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69748
winterwolf94 (Thành viên)
winterwolf94+34
Biết code binary-indexed tree
Bài viết: 42
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: De Contest 2 - Solutions 8 năm trước   (+3)
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 .
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69757
meodorewan (Thành viên)
meodorewan+5
Super fast coder
Bài viết: 68
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: De Contest 2 - Solutions 8 năm trước   (+0)
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 ạ.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69758
royalsilver16 (Thành viên)
royalsilver16+1
Super fast coder
Bài viết: 78
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: De Contest 2 - Solutions 8 năm trước   (+0)
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
 
Đã lưu IP Đã lưu IP  
 
I do what I like
I like what I do
  Đã khóa chức năng gửi bài.
#69761
vodanh9x (Thành viên)
vodanh9x+14
Nhắm mắt code không bug
Bài viết: 233
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: De Contest 2 - Solutions 8 năm trước   (+0)
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
 
Đã lưu IP Đã lưu IP  
 
Hahaha
  Đã khóa chức năng gửi bài.
#69763
loiprovd123 (Thành viên)
loiprovd193-
Super fast coder
Bài viết: 72
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: De Contest 2 - Solutions 8 năm trước   (+0)
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 ^^
 
Đã lưu IP Đã lưu IP  
 
YM: mai_mang_mot_bong_hjnh
Mong được làm quen với mọi người
  Đã khóa chức năng gửi bài.
#69765
winterwolf94 (Thành viên)
winterwolf94+34
Biết code binary-indexed tree
Bài viết: 42
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: De Contest 2 - Solutions 8 năm trước   (+2)
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
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69766
winterwolf94 (Thành viên)
winterwolf94+34
Biết code binary-indexed tree
Bài viết: 42
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: De Contest 2 - Solutions 8 năm trước   (+0)
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 ạ.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69824
HelloSirius (Thành viên)
hellosirius+10
Nhắm mắt code không bug
Bài viết: 138
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: De Contest 2 - Solutions 8 năm trước   (+0)
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.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS