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
C11 contest round 14 (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 0
CHỦ ĐỀ - C11 contest round 14
#67411
yenthanh132 (Thành viên)
yenthanh132+36
Đã code là AC
Bài viết: 117
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: C11 contest round 14 8 năm, 2 tháng trước   (+3)
Solution bài C11SEVEN

**Bài này có thể giải bằng cây chứa khoảng – Interval Tree (IT). Tư tưởng là ta sẽ dùng một cây IT, mỗi nút của cây chứa:
- Một mảng giá trị val[0..6], val[k] là kết quả của truy vấn “3 k” cho đoạn mà nút hiện tại quản lí.
- Một biến size là số lượng các phần tử trong đoạn mà nút hiện tại quản lí.
**Ban đầu với các nút quản lí 1 phần tử duy nhất. Ta sẽ cập nhật cho giá trị của nút đó như sau: val[0]=<giá trị của phần tử đó>; val[i]=1, với i từ 1 đến 6; size = 1;
**Như vậy với các nút cha, ta sẽ cập nhật giá trị của nút đó như sau:
- IT[i].val[k] =IT[i*2].val[k] * IT[i*2+1].val[(k – (IT[i*2].size mod 7) + 7) mod 7];
- IT[i].size = IT[i*2].size + IT[i*2+1].size;
**Về phần xử lí các truy vấn ta làm như sau:
- Với truy vấn 1, ta sẽ cập nhật lại giá trị size của nút chứa phần tử bị xóa thành 0 và cập nhật lại các nút cha như đã nêu trên.
- Với truy vấn 2, ta sẽ thay đổi giá trị val[0] của nút chứa phần tử bị thay đổi và tiến hành cập nhật lại các nút cha.
- Với truy vấn 3, ta chỉ cần đơn giản xuất ra giá trị val[k] của nút góc (quản lí tất cả các phần tử).
- Lưu ý với truy vấn 1, 2, ta cần cập nhật lại đúng vị trí của phần tử đó trên mảng ban đầu (lúc chưa có phần tử nào bị xóa). Để tìm được đúng vị trí của phần tử mà ta cập nhật trên mảng ban đầu, ta có 2 cách để làm điều này: Dùng một cây BIT kết hợp chặc nhị phân (mất log(n)^2 cho mỗi lần tìm kiếm); Hoặc ta có thể tìm trực tiếp dựa trên mảng size trên cây IT (mất log(n) cho mỗi lần tìm kiếm).

Vậy đpt của bài toán này là: O(n*7*log(n)) cho cách tìm kiếm trực tiếp dựa vào mảng size, hoặc O(n*7*log(n)) cho cách tìm kiếm bằng BIT + chặc nhị phân.
 
Đã lưu IP Đã lưu IP  
 
I accept the failure, but will never give up...
While (i <= you) i++;
  Đã khóa chức năng gửi bài.
#67412
vietthaitink21 (Thành viên)
vietthaitink21-
Đã code là AC
Bài viết: 85
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: C11 contest round 14 8 năm, 2 tháng trước   (-1)
1/3 số test <=5000 mà, nếu bạn không làm với độ phức tạp O(N) thì 30,77 là đúng rồi mà
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67413
vietthaitink21 (Thành viên)
vietthaitink21-
Đã code là AC
Bài viết: 85
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: C11 contest round 14 8 năm, 2 tháng trước   (-1)
thanghungkhi viết:
QUOTE:
iamquang95 viết:
QUOTE:
25 bạn ạ

Mình cám ơn, mình cũng ra 25, không biết sai chỗ nào mà cứ bị 30,77 mãi ^^


1/3 số test <=5000 mà, nếu bạn không làm với độ phức tạp O(N) thì 30,77 là đúng rồi mà
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67414
thanghungkhi (Thành viên)
thanghungkhi+1
Biết code binary-indexed tree
Bài viết: 21
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: C11 contest round 14 8 năm, 2 tháng trước   (+0)
vietthaitink21 viết:
QUOTE:
thanghungkhi viết:
QUOTE:
iamquang95 viết:
QUOTE:
25 bạn ạ

Mình cám ơn, mình cũng ra 25, không biết sai chỗ nào mà cứ bị 30,77 mãi ^^


1/3 số test <=5000 mà, nếu bạn không làm với độ phức tạp O(N) thì 30,77 là đúng rồi mà


Anh xem qua Code của em với ạ, em nghĩ là O(N) mà ^^

top:=1;
num:=n-1;
stack[top]:=a[1];
id[top]:=1;

for i:=2 to n do begin
if a[i]>stack[top] then begin

while (stack[top]<a[i]) and (top>0) do begin
if id[top]<i-1 then inc(num);
dec(top);
end;

inc(top);stack[top]:=a[i];id[top]:=i;
if (stack[1]<>stack[top]) and (id[1]<>id[top]) then inc(num);

end else if a[i]=stack[top] then begin
top1:=top;

while stack[top1]=a[i] do begin
if id[top1]<i-1 then inc(num);
dec(top1);
end;

inc(top);stack[top]:=a[i];id[top]:=i;
if (stack[1]<>stack[top]) and (id[1]<>id[top]) then inc(num);

end else if a[i]<stack[top] then begin
inc(top);stack[top]:=a[i];id[top]:=i;
end;

PS: Để thẻ code khó đọc quá nên e để như vậy ạ ^^
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67416
flashmt (Admin)
flash_mt+99
Admin
Bài viết: 417
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: C11 contest round 14 8 năm, 2 tháng trước   (+0)
Mình nghĩ viết 1 đoạn code 2 vòng lặp + sinh test check chắc là dễ hơn code đúng bài này mà sao một số bạn có vẻ ngại làm thế. Trong contest mình cũng làm thế nên mới debug được lỗi khi có nhiều độ cao bằng nhau.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67417
shiningstar_193 (Thành viên)
shiningstar193+3
Nhắm mắt code không bug
Bài viết: 222
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: C11 contest round 14 8 năm, 2 tháng trước   (+1)
http://pastebin.com/RKY9q53k
Đây là bài của bạn franco1 cho mình để test.
Các bạn lấy bài này mà test nhé.
N=500000 vẫn chạy rất nhanh.
 
Đã lưu IP Đã lưu IP  
 
Dù chỉ là 1 ngôi sao nhỏ, không thể sánh bằng ánh trăng rực rỡ ở bên cạnh, nhưng cũng không vì thế mà cam chịu cuối đầu, vẫn ngày ngày vươn mình chiếu sáng khắp nhân gian
  Đã khóa chức năng gửi bài.
#67426
warriorz (Thành viên)
warriorz
Đã biết code đệ quy
Bài viết: 16
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: C11 contest round 14 8 năm, 2 tháng trước   (+0)
Mình nghĩ bạn nên tự tạo test rồi post lên để tránh copy code
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#67428
shiningstar_193 (Thành viên)
shiningstar193+3
Nhắm mắt code không bug
Bài viết: 222
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: C11 contest round 14 8 năm, 2 tháng trước   (+1)
Yên tâm code này chỉ dc 60% số test và không thể nâng cấp thêm nữa.
 
Đã lưu IP Đã lưu IP  
 
Dù chỉ là 1 ngôi sao nhỏ, không thể sánh bằng ánh trăng rực rỡ ở bên cạnh, nhưng cũng không vì thế mà cam chịu cuối đầu, vẫn ngày ngày vươn mình chiếu sáng khắp nhân gian
  Đã khóa chức năng gửi bài.
#67438
blackstart (Thành viên)
blackstart+40
Không code nữa rồi
Bài viết: 362
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: C11 contest round 14 8 năm, 2 tháng trước   (+0)
@yenthanh132: anh Thanh ơi có solution cho cách dùng BST không tại em thấy với máy chấm Cube thì chắc dùng BST vẫn có thể (có gì sai mong mọi người đừng quăng đá )
 
Đã lưu IP Đã lưu IP  
 
"Nothing is impossible; impossible itself says "I m possible"..."


Là Nam Nhi gõ phím bình thiên hạ...
Thân Anh Hùng click chuột định giang sơn...
  Đã khóa chức năng gửi bài.
#67449
yenthanh132 (Thành viên)
yenthanh132+36
Đã code là AC
Bài viết: 117
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: C11 contest round 14 8 năm, 2 tháng trước   (+0)
blackstart viết:
QUOTE:
@yenthanh132: anh Thanh ơi có solution cho cách dùng BST không tại em thấy với máy chấm Cube thì chắc dùng BST vẫn có thể (có gì sai mong mọi người đừng quăng đá:) )

Bài C11SEVEN thực tế có thể dùng BST nhưng cách cài đặt sẽ rất khó khăn (anh cũng không dám dùng), dùng IT là đơn giản nhất rồi em ạ
 
Đã lưu IP Đã lưu IP  
 
I accept the failure, but will never give up...
While (i <= you) i++;
  Đã 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