Mất mật khẩu? | Đăng ký Nhập các thuật ngữ tìm kiếm của bạn Web VNOI Nộp mẫu đơn tìm kiếm ### Đ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
Forum  Thảo luận chung  English corner
[VM08] 10th round - Solution (1 đang xem) ,(1) Khách  Được ưa thích: 0
CHỦ ĐỀ - [VM08] 10th round - Solution
#5217
paulmcvn+71  Bài viết: 1288    [VM08] 10th round - Solution 12 năm, 5 tháng trước (+0) HINHTHOI A four-sided polygon is a rhomb if and only if it has two perpendicular diagonals intersecting each other at their mid-points. From this observation we have the following O(n^2logn) algorithm: We maintain a list of segments, each segment is a diagonal formed by a pair of points in our set. In particular, for each pair (x1, y1) and (x2, y2) we store two segments with 3 information: - Coordinates of mid-point: ((x1 + x2) / 2, (y1 + y2)/2) (we can store (x1+ x2, y1 + y2) instead to avoid floating-point numbers). These coordinates are the same for both segments. - Gradient: one segment has gradient (x2 - x1) / (y2 - y1) while the other has gradient (y1 - y2) / (x2 - x1) - Type: the former has type 1 while the latter has type 2 After that, we sort all segments according to their (mid-point coordinates , gradient). For each interval that has equal (mid-point coordinates , gradient) values in the list, the number of rhomb is number of type-1 segments * number of type-2 segments. Finally, we have to divide the result by 2 because each rhomb is counted twice in our algorithm. DIGIT0 Let N be the length of our string and f[c] is the number of occurence of character c in our string. The number of different permutations is n! / (f['a']! * f['b]! * ... f['z']!). To count the number of trailing zeroes, we have to count the number of divisor 2 and divisor 5 of the above number. The number of divisor d of k! is: divisor(k, d) = floor(k / d) + floor(k / (d^2)) + floor(k / (d^3)) + ... The number of trailing zeroes is: min(divisor(n, 2) - divisor(f['a'], 2) - ... - divisor(f['z'], 2), divisor(n, 5) - divisor(f['a'], 5) - ... - divisor(f['z'], 5)) Đã lưu IP
Đã khóa chức năng gửi bài.
#5222
(Thành viên) Đã biết code đệ quy Bài viết: 11    Trả lời: [VM08] 10th round - Solution 12 năm, 5 tháng trước (+0) Regarding the problem DIGIT0, can you please check if there is an endline character at the end of the input string? I think that this is common practice and it should be there, even if it is not mentioned in the problem statement. The way it is now, my solution gets 0 points. Đã lưu IP
Đã khóa chức năng gửi bài.
#5234
(Thành viên)
gerrob+1 Biết code binary-indexed tree Bài viết: 47    Trả lời: [VM08] 10th round - Solution 12 năm, 5 tháng trước (+0) minhduc wrote: QUOTE: HINHTHOI... From this observation we have the following O(n^2logn) algorithm: There is also an O(n^2+bound^2) algorithm for the problem if for all (x,y) points |x|,|y|<=bound is true (bound=50 in our problem). Đã lưu IP
Đã khóa chức năng gửi bài.
#5270
paulmcvn+71  Bài viết: 1288    Trả lời: [VM08] 10th round - Solution 12 năm, 4 tháng trước (+0) @supo: The test cases have been added with endline character and the submissions are rejudged. @gerrob: Could you describe your algorithm? Đã lưu IP
Đã khóa chức năng gửi bài.
#5274
(Thành viên)
gerrob+1 Biết code binary-indexed tree Bài viết: 47     Đã lưu IP
Đã khóa chức năng gửi bài.
#5292
paulmcvn+71  Bài viết: 1288    Trả lời: [VM08] 10th round - Solution 12 năm, 4 tháng trước (+0) I guess the first part of your algorithm should be O(n^2log(bound)) since we have to call GCD to normalize the fraction. Memory requirement is O(bound^2). For small bound it is faster than the solution. At first I generated the points in [-10^9, 10^9] range but the number of rhombs is so small so I reduced it to 50. Đã lưu IP
Đã khóa chức năng gửi bài.
#5346
(Thành viên)
gerrob+1 Biết code binary-indexed tree Bài viết: 47    Trả lời: [VM08] 10th round - Solution 12 năm, 4 tháng trước (+0) No. You can precompute all possible gcd(x,y) values for |x|,|y|<=2*bound in O(bound^2*log(bound)) time by 3 loops, or optimize it to reach O(bound^2*loglog(bound)). But I think this can be done also in O(bound^2) using Farey sequence or Stern Brocot tree. Đã lưu IP
Đã khóa chức năng gửi bài.
#5348
(Thành viên) Đã biết code đệ quy Bài viết: 11    Trả lời: [VM08] 10th round - Solution 12 năm, 4 tháng trước (+0) thanks  Đã lưu IP
Đã khóa chức năng gửi bài.
#5353
(Thành viên) Ra đề chuyên nghiệp Bài viết: 234    Trả lời: [VM08] 10th round - Solution 12 năm, 4 tháng trước (+0) http://vn.spoj.pl/ranks/HINHTHOI/ Đã lưu IP
Đã khóa chức năng gửi bài.
 Mục lục diễn đàn Thảo luận chung English corner