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
Vòng 2 HSGQG năm 2012 (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Ủ ĐỀ - Vòng 2 HSGQG năm 2012
#61973
coder_1340 (Thành viên)
coder_1340+19
Đã code là AC
Bài viết: 81
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: Vòng 2 HSGQG năm 2012 8 năm, 9 tháng trước   (+0)
Giờ này chắc là mọi người đã thi xong rồi, ai có thể up đề lên để em tham khảo được không ạ!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#61976
R_R_ (Admin)
mr_invincible+213
Admin
Bài viết: 745
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: Vòng 2 HSGQG năm 2012 8 năm, 9 tháng trước   (+4)
Mình có nghe được tóm tắt đề:
Bài 1: Cho N (<= 200 000) số, mỗi số <= 2^16, cần tìm số cặp u, v, u khác v, và u OR v = v

Bài 2: Có N công việc cần hoàn thành trong khoảng thời gian [A,B]. Việc i cần thời gian f(i) để hoàn thành, và có trọng số w(i). Cho một mốc thời gian D. Tại một thời điểm không được làm quá 1 công việc, khi đã bắt đầu làm 1 công việc thì phải làm hết công việc đó (không được dừng lại giữa chừng). Công việc i nếu kết thúc vào thời gian T(i) thì mất chi phí là |D - T(i)| * w(i).
Tìm tổng chi phí nhỏ nhất

Bài 3: Cho N (<= 10^6) điểm trên mặt phẳng). Từ điểm (xi,yi) có thể di chuyển đến điểm (xj, yj) nếu 1 trong 2 điều kiện sau thỏa mãn:
1. xi >= xj và yi <= yj
2. xi <= xj và yi >= yj
Tìm đường đi ngắn nhất từ điểm s đến điểm t

Bài 4: (ko biết đề)

Bài 5: Cho bảng M*N (M, N <= 1000), mỗi ô trên bảng ghi 1 số 0 --> 2. Cho K truy vấn (K <= 10^6). Mỗi truy vấn dạng (p,q) là tìm hình chữ nhật diện tích lớn nhất nằm trong khoảng hàng từ p đến q, và có chênh lệch giữa số lớn nhất và nhỏ nhất không quá 1

Bài 6: Cho đồ thị N đỉnh M cạnh (N <= 100, M <= 10000). Mỗi cạnh có 2 trọng số (a, b). Tìm cây khung có (tổng a)^2 + (tổng b)^2 là lớn nhất
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#61977
R_R_ (Admin)
mr_invincible+213
Admin
Bài viết: 745
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: Vòng 2 HSGQG năm 2012 8 năm, 9 tháng trước   (+2)
Hướng giải của mình cho các bài:
1. Xử lý bit + qhđ thông thường
3. Từ một điểm chỉ cần quan tâm đến việc di chuyển xa nhất về 4 hướng --> đồ thị mới chỉ có 4N cạnh. Sau khi sort lại các điểm thì ta dễ dàng sinh được tập cạnh.
5. Trước hết đổi lại truy vấn thành tìm hình chữ nhật lớn nhất không chứa một số u (u = 0 hoặc u = 2).
Sinh trước tất cả các kết quả có thể có của các truy vấn. Xét lần lượt các hàng i, với mỗi hàng i, ta tìm cách sinh tất cả các kết quả của truy vấn (j,i) với j <= i trong O(N).
Xét j tăng dần từ 1 đến i. Ta quan tâm đến các thời điểm mà trên 1 cột xuất hiện 1 số mới. Tổng số thời điểm này không quá 3N. Với mỗi thời điểm ta chỉ cần update độ dài các đoạn không chứa 1 số, và duy trì đoạn có độ rộng lớn nhất. Chú ý là độ rộng các đoạn tăng lên, nên thao tác update có thể làm trong O(1).

2. (Cách sau ko đảm bảo đạt đc 100% điểm)
Nhận xét: Sort các công việc theo T/W. Trong đáp án tối ưu, nếu ta xét dãy T/W của các công việc được làm thì sẽ thu đc 1 dãy giảm dần rồi tăng dần.
Từ nhận xét đấy, tìm cách qhđ theo thời gian
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#61978
luv_luxury (Thành viên)
luv_luxury-
Biết code binary-indexed tree
Bài viết: 22
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: Vòng 2 HSGQG năm 2012 8 năm, 9 tháng trước   (+2)
Em thêm bài 4 nhé
Bài 4: Cho n xâu t[i] và m xâu s[i]. Với mỗi xâu s[i] đếm xem có bao nhiêu xâu t[i] nhận s[i] là tiền - hậu tố.
VD: xâu aliba là tiền - hậu tố của xâu alibababaliba.
Giới hạn n<=250000; m<=250000. Mỗi xâu s[i] và t[i] dài không quá 60 kí tự, tổng độ dài các xâu s[i]<=1000000, tổng độ dài các xâu t[i]<=1000000
 
Đã lưu IP Đã lưu IP  
 
Cộng mình cho mình hết bị trừ lào
  Đã khóa chức năng gửi bài.
#61980
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: Vòng 2 HSGQG năm 2012 8 năm, 9 tháng trước   (+0)
Bài 6: tìm ( ΣA )^2 + ( ΣB )^2 max tương đương tìm ΣAΣB min -> có vẻ giống bài timeismoney Balkan OI 2011.

Edit: mình nhầm, thật ra ΣA + ΣB thay đổi nên không tương đương.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#61981
quocbao66 (Thành viên)
quocbao66+4
Super fast coder
Bài viết: 69
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: Vòng 2 HSGQG năm 2012 8 năm, 9 tháng trước   (+1)
Bài 4 hay quá nhỉ . Có ai có ý tưởng không? Em chỉ nghĩ ra mỗi cách là với mỗi xâu s[i] và t[j] ta tạo mảng prefix dùng Z function cho t[j], sau đó kiểm tra và tăng đếm. DPT khoảng n*m*60.

Edit: Mình ngốc thật, sao lại không nghĩ tới hash table nhỉ
 
Đã lưu IP Đã lưu IP  
 
Hamlet:
" Tồn tại hay không tồn tại. Đó mới là vấn đề "
  Đã khóa chức năng gửi bài.
#61982
Heo mập (Admin)
phaleq+44
Admin
Bài viết: 680
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: Vòng 2 HSGQG năm 2012 8 năm, 9 tháng trước   (+1)
luv_luxury viết:
QUOTE:
Em thêm bài 4 nhé :)
Bài 4: Cho n xâu t[i] và m xâu s[i]. Với mỗi xâu s[i] đếm xem có bao nhiêu xâu t[i] nhận s[i] là tiền - hậu tố.
VD: xâu aliba là tiền - hậu tố của xâu alibababaliba.
Giới hạn n<=250000; m<=250000. Mỗi xâu s[i] và t[i] dài không quá 60 kí tự, tổng độ dài các xâu s[i]<=1000000, tổng độ dài các xâu t[i]<=1000000 :D


Bài này có thể dùng KMP (hoặc Z-Function) + hash.

Với mỗi xâu T[i] thì tìm giá trị L max để đoạn đầu L kí tự của T[i] trùng với đoạn cuối L kí tự của T[i]. Thế thì các xâu có thể là tiền-hậu tố của T[i] phải nằm trong số L xâu tiền tố của nó. Hash các xâu này thành số rồi dùng map để đếm.

Sau bước này thì với mỗi xâu S[i] chỉ cần hash nó và truy vấn trong map đã tạo để ra kết quả.

Edit: Cách chuẩn hơn cho đoạn truy vấn là dùng Trie (Zero_sharp )
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#61987
lionwithwings (Thành viên)
lion_it+11
Nhắm mắt code không bug
Bài viết: 174
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: Vòng 2 HSGQG năm 2012 8 năm, 9 tháng trước   (+0)
@anh R_R: bài 3 đề bài hỏi gì thế ạ ? :-/
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#61989
phanhanh (Thành viên)
mliafol
Đã biết code đệ quy
Bài viết: 17
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: Vòng 2 HSGQG năm 2012 8 năm, 9 tháng trước   (+0)
lionwithwings viết:
QUOTE:
@anh R_R: bài 3 đề bài hỏi gì thế ạ ? :-/

Cho 2 đỉnh s,t.Tìm đường đi từ s,t mà qua ít điểm nhất
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#62011
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: Vòng 2 HSGQG năm 2012 8 năm, 9 tháng trước   (+0)
các anh cho em hỏi là bài 2 thời gian bắt đầu tính từ 1 hay là bắt đầu tính từ A ạ
 
Đã lưu IP Đã lưu IP  
 
Hahaha
  Đã 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