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
[VM08] 10th round - Solution (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Ủ ĐỀ - [VM08] 10th round - Solution
#5217
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
[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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#5222
supo (Thành viên)
Đã biết code đệ quy
Bài viết: 11
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: [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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#5234
gerrob (Thành viên)
gerrob+1
Biết code binary-indexed tree
Bài viết: 47
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: [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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#5270
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#5274
gerrob (Thành viên)
gerrob+1
Biết code binary-indexed tree
Bài viết: 47
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: [VM08] 10th round - Solution 12 năm, 4 tháng trước   (+0)
Somewhat it is similar to the sample solution.
First observe that if the midpoint of two points is (xd,yd), then (2*xy,2*yd) is a grid point and |2*xd|,|2*yd|<=2*bound. Let the gradient is (mx,my) (where mx and my is an integer) and normalize it, say gcd(mx,my)=1 and mx>=0 (if mx=0 then my>0), here also |mx|,|my|<=2*bound. So store the (midpoint,gradient) in a linked list, where in each list the midpoints are same. If you've done this for each pair of points then you can now go through on each possible midpoint and count the equal gradients. (mx,my) is perpendicular to (nx,ny) if and only if:
1. if my>=0 then nx=my and ny=-mx
2. if my<0 then nx=-my and ny=mx
[the reason for this that the gradients are normalized].
In O(1) time it is possible to check if the other gradient is already used at this midpoint and if yes, then we add the number of these gradients to the total number of rhombs. [for this I'm using also a check array, it's size (4*bound+1)^2, the same as the count array, (obviously (4*bound+1)^2 is the number of grid points in the larger grid |x|,|y|<=2*bound)].

I'm also counting the number of perpendicular gradients, just one example: if:
(ax,ay) and (bx,by) is perpendicular to (cx,cy) and (dx,dy) and (ex,ey) and say the order in the list is a,c,b,d,e then
1. at "a" we don't find a collision
2. at "c" we find one collision, and 1 to the number of rhombs
3. at "b" we find one collision, add 1
4. at "d" we find two collisions, add 2
5. at "e" we find two collisions, add 2
So we've added 1+1+2+2=6 this is the same number in your method, but you've used multiplication for this 2*3=6.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#5292
minhduc (Admin)
paulmcvn+71
Admin
Bài viết: 1288
graphgraph
Thành viên đang truy cập Click vào đây để xem thông tin về thành viên này
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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#5346
gerrob (Thành viên)
gerrob+1
Biết code binary-indexed tree
Bài viết: 47
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: [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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#5348
supo (Thành viên)
Đã biết code đệ quy
Bài viết: 11
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: [VM08] 10th round - Solution 12 năm, 4 tháng trước   (+0)
thanks
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#5353
Kaiel (Thành viên)
Ra đề chuyên nghiệp
Bài viết: 234
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: [VM08] 10th round - Solution 12 năm, 4 tháng trước   (+0)
 
Đã 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