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 - Solutions (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 4
CHỦ ĐỀ - De Contest - Solutions
#69489
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 - Solutions 8 năm trước   (+4)
ROUND 1
Bài 1 : TRILAND
Ở đây có một cái bẫy là phần xét tam giác đều. Trên thực tế trong mặt phẳng thì 3 điểm tọa nguyên không thể tạo thành tam giác đều (phần chứng minh xem ở đây http://vnoi.info/index.php?option=com_fireboard&Itemid=26&func=view&id=69301&catid=13&limit=10&limitstart=10#69342).
Ta duyệt từng điểm trong N điểm. Gỉa sử chọn đỉnh k. Tính mảng f[i]=(x[i]-x[k])^2 + (y[i]-y[k])^2 (bình phương khoảng cách từ đỉnh i tới đỉnh k). Sắp xếp lại mảng f theo chiều tăng dần. Nếu giá trị A xuất hiện B lần trong mảng f thì sẽ có B*(B-1)/2 tam giác cân tại k mà độ dài cạnh bên bình phương là A.
Độ phức tạp : O(N^2 * log(N) )
Bài 2 : Grape
Đầu tiên ta đảo ngược bảng lại theo hàng ngang cho dễ nhìn. Sau khi đảo thì tính chất của bảng là tăng dần trên mỗi hàng từ 1..N và mỗi cột từ 1..N => trong mỗi hình vuông mà ô trên trái là (x1,y1) và ô dưới phải là (x2,y2) thì số nhỏ nhất là A[x1,y1] và A[x2,y2].
Do (x1,y1) và (x2,y2) cùng nằm trên một đường chéo nên ta chỉ cần xét các đường chéo. Với mỗi truy vấn L,R ta xét M+N-1 đường chéo. Gọi B là mảng lưu các giá trị trên đường chéo đang xét. Ta chặt nhị phân trên B tìm u nhỏ nhất sao cho B[u]>=L và v lớn nhất sao cho B[v]<=R. Cạnh hình vuông trên đường chéo này là B[v]-B[u]+1.
Độ phức tạp O(q*(m+n)*log(m)) -> ăn được hơn 80% số test.
Cải tiến : Duyệt các đường chéo theo thứ tự từ dưới lên theo hàng (bắt đầu ở cột 1), sau đó đến các đường chéo trái qua theo cột (bắt đầu ở hàng 1). Gọi Ui, Vi là 2 cận trên đường chéo i giống như chặt nhị phân thì theo tính chất của bảng ta thấy được chênh lệch giữa U(i+1) và U(i) cũng như giữa V(i+1) và V(i) không quá 1 -> ko cần chặt nhị phân.
Độ phức tạp O(q*(m+n)) -> ăn hết test.
Bài 3 : SOCCER
Đầu tiên ta tham lam, cho đội 1 thắng hết tất cả các trận còn lại. Sau đó tìm 1 cách "dàn xếp" tỉ số các trận đấu để tất cả các đội khác đều thua điểm đội 1. Một số bạn tham lam rất hay ăn nhiều hoặc trọn điểm . Còn ở đay mình bàn cách ko tham :P.
Gọi P[i] là số điểm hiện tại của đội i sau khi đã tham lam cho đội 1. Từ nhận xét kết quả 1 trận đấu K giữa 2 đội a, b ra sao thì tổng điểm của N đội sau khi hết M vòng đấu không thay đổi, ta xây dựng thuật toán luồng :
- Đỉnh phát st, đỉnh thu fn
- Có N đỉnh, mỗi đỉnh thể hiện một đội (giả sử k). Cho 1 cung nối từ st đến k với độ thông qua P[1]-P[k]-1
- Có N*(N-1)/2 đỉnh, mỗi đỉnh Q thể hiện 1 cặp đấu (a, b) . Cho 3 cung : từ a->Q, từ b->Q, từ Q->fn cùng với độ thông qua = (số trận còn lại của cặp đấu a, b) x 2
Tìm 1 luồng cực đại F từ st đến fn. Nếu F + 2G = M*N*(N-1) thì Việt Nam có thể vô địch (G là số trận đã đấu)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69490
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 - Solutions 8 năm trước   (+4)
ROUND 2
Bài 1 : BILL
Bài đơn giản nhất trong 2 round và phần lớn các bạn đều AC .
Ta viết 2 hàm
+ amount(x) là số kWh tương ứng với số tiền là x
+ money(y) là số tiền tương ứng với dung lượng tiêu thụ y kwh
Ta chặt nhị phân kết quả. Tính F(Z) = money(amount(Z) + amount(Z+Y)). Kết quả là Z nhỏ nhất thỏa F(Z) >= X.
Độ phức tạp : log(X)*5
Bài 2 : MECUNG
Tương đối khoai để ăn 100% bài này . Đầu tiên ta BFS từ đỉnh N. Gọi d[i] = độ dài đường đi ngắn nhất từ i đến N.
Sau đó ta BFS lần 2 theo lớp từ 1 đến N. Trong lần này
- chỉ xét các cạnh (u,v) mà d[u]=d[v]+1.
- pre[i] = đỉnh ngay trước i trên đường đi từ 1 đến i
- color[i] = màu của cạnh nối từ pre[i]-i
Giả sử đang trong lớp K. Trong các đỉnh thuộc lớp K ta kiếm 1 đỉnh z nhỏ nhất theo hàm so sánh sau :

function behon(longint a,b)
begin
exit (color[pre[a]]<color[pre[b]]) or (color[pre[a]]=color[pre[b]] and color[a]<=color[b])
end;

Bây giờ trong lớp K ta chỉ chọn các đỉnh u mà behon(u,z)=true. Với mỗi cạnh (u,v) ta chỉ cập pre[v]=u nếu
+ đỉnh v chưa được đến -> bỏ đỉnh v vào lớp K+1
+ hoặc v đã đến và color[v] > màu của cạnh (u,v)
Xong xuôi rồi thì phần truy vết khá đơn giản .
Độ phức tạp : O( 2*(N+M) )
Bài 3 : PERC
Đây là bài mình tâm đắc nhất . Từ một hoán vị (a1,a2,..,an) sau khi biến đổi k lần sẽ trở lại như cũ.
Tinh ý 1 chút thì ta thấy phần tử thứ i trong dãy hoán vị sẽ được thay bằng phần tử ai trong hoán vị đó nên xem như có 1 cạnh 1 chiều từ i-> ai. Do mỗi đỉnh i có đúng 1 cung ra và 1 cung vào nên đồ thị này chắc chắn có chu trình. Bằng 1 phép duyệt đơn giản ta sẽ biết được có tất cả bao nhiêu chu trình (m) và độ dài mỗi chu trình L[j]
Với chu trình thứ j, sau L[j] phép biến đổi thì thứ tự các phần tử trong chu trình này trở về đúng như trong hoán vị ban đầu.
=> Số phép biến đổi để cả m chu trình trở về ban đầu là bội chung nhỏ nhất (BCNN) của L[1], L[2], … L[m].
Đến đây ta có thể đưa ra 1 phép tính đơn giản để ăn khoảng 50% số điểm bằng công thức
BCNN(a,b) = a*b / UCLN(a,b). Lưu ý để tránh tràn số ta lấy a chia cho ucln(a,b) trước rồi mới nhân cho b :P.
Cải tiến : dùng sàng nguyên tố. Gọi P[i] là số nguyên tố thứ i trong dãy 1,2,…N và G[i] = số mũ lớn nhất của P[i] trong L[1],L[2],…,L[m]. Sau khi đã duyệt hết các Lj và phân tích ra thừa số nguyên tố, ta dựa vào mảng G để tính kết quả Res = P[1]^G[1])* P[2]^G[2] * … * P[q]^G[q] (q là số lượng số nguyên tố từ 1->N)
Độ phức tạp ~ N*log10(N)
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69500
dhkhtn (Thành viên)
dhkhtn+2
Biết code binary-indexed tree
Bài viết: 49
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 - Solutions 8 năm trước   (+0)
Bài PERC là lý thuyết cơ bản của hoán vị. Liên quan đến phần phân rã hoán vị thành các chu trình rời rạc.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69501
manhung95 (Thành viên)
askgfqf123+2
Super fast coder
Bài viết: 50
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 - Solutions 8 năm trước   (+0)
Uổng ghê. Bài soccer em cài tư tưởng y như vậy mà vẫn sai 1 test. Đến h chưa hiểu tại sao :-s
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69504
thitgaluoc (Thành viên)
thitgaluoc-
Đã biết code đệ quy
Bài viết: 14
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 - Solutions 8 năm trước   (+1)
em nghĩ bài bill phải là money ( amount(z) + amount(z + y) ) chứ ạ ?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69505
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 - Solutions 8 năm trước   (+0)
cái tội mình ngu đọc không kĩ đề bài 3 nên không mod kq cho 10^9+7 thành ra từ 100->34 @@
 
Đã lưu IP Đã lưu IP  
 
Hahaha
  Đã khóa chức năng gửi bài.
#69506
iamnhvt (Thành viên)
iamnhvt123-
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 - Solutions 8 năm trước   (+0)
mấy anh cho em hỏi bài MECUNG em dùng disktra + heap , trong lúc duyệt mình dùng mảng lưu màu để xét và cập nhật kết quả không biết cách này có bị sai hay quá thời gian không ạ??
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69509
amydolly (Thành viên)
amydolly+3
Đã biết code đệ quy
Bài viết: 18
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 - Solutions 8 năm trước   (+0)
PS cho e hỏi bài MECUNG e WA hay TLE với ạ. account e là amydolly
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69513
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 - Solutions 8 năm trước   (+0)
@amydolly : bạn bị WA
Các bạn xem solution mình đưa rồi so sánh nhé. Nếu chắc chắn không TLE thì WA. Mình sẽ không trả lời những câu hỏi này nữa .
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#69518
phamanhtu (Thành viên)
phamanhtu1996-
Biết code binary-indexed tree
Bài viết: 20
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 - Solutions 8 năm trước   (+0)
Bài GRAPE mình làm đpt O(q*m*log(min(n, m))) vẫn qua hết test, time 0,2s.
 
Đã 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