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
Trả lời: [VM08] 12th round (final) - Solution (1 đang xem) ,(1) Khách  Được ưa thích: 0
CHỦ ĐỀ - Trả lời: [VM08] 12th round (final) - Solution
#6029
paulmcvn+71  Bài viết: 1288    [VM08] 12th round (final) - Solution 12 năm, 4 tháng trước (+0) DANCING We restate the problem: Given a sequence a1, a2, ..., an (ai > 0) and the following operation: choose any three consecutive numbers (ai-1, ai, ai+1), change them into (ai-1 + ai, -ai, ai + ai+1). After some operations, we obtain the sequence (b1, b2, ..., bn). Given (b1, b2, ..., bn), find the initial sequence. Solution: Let Si=a1+a2+...+ai To change (ai-1, ai, ai+1) into (ai-1 + ai, -ai, ai + ai+1) in a is equivalent to change (Si-1, Si) into (Si, Si-1) in S, that is exchange the ith and (i+1)th element. Sn's position is never changed. So we have the following algorithm: • Calculate Si = b1 + b2 + ... + bi for 1 <= i <= n-1 •Then we sort Si increasingly. Suppose the new order of S is S1, S2, ..., Sn-1. • Let S0 = 0 and Sn = b1 + b2 + ... + bn, we have ai = Si - Si-1 for all 1 <= i <= n. This is the initial sequence a1, a2, ..., an. Ta thu được dãy ban đầu a1, a2, ..., an • If the initial sequence does not satisfy ai > 0 for all i (because Si is sorted increasingly, we already have ai >= 0 for all 2 <= i <= n-1), print -1. Otherwise sequence a is exactly the solution of the problem. Algorithm complexity: O(nlogn) KINGDOM This problem can be solved by using dynamic programming in a tree. Let f[u, t] be the maximum value obtained from the subtree root u when we have a budget of t. Suppose u have k child nodes v1, v2, ..., vk. So: f[u, t] = V(u) + max{ f[v1, t1] + f[v2, t2] + ... + f[vk, tk] | t1 + t2 + ... + tk = t - C(u) } To computemax{ f[v1, t1] + f[v2, t2] + ... + f[vk, tk] | t1 + t2 + ... + tk = t - C(u) }, we use dynamic programming once again in the child nodes of u. That is:g[i, t] = max{ f[v1, t1] + f[v2, t2] + ... f[vi, ti] | t1 + t2 + ... + ti = t} Analysis: Let N(u) be the number of child nodes of u. To compute g, at each node we need about N(u)*t^2 steps. To compute f we need n*t steps. So the algorithm complexity is about: n*t + t^2sum(N[u]|u=1..n) = O((t^2).n) Solution for WIFI and BINLADEN will be posted later.  Đã lưu IP
Đã khóa chức năng gửi bài.
#6037
beo_chay_so+62  Bài viết: 294    Trả lời: [VM08] 12th round (final) - Solution 12 năm, 4 tháng trước (+0) BINLADEN It's quite easy to find the solution. You just need to find the shortest way between 2 nodes in a graph. This graph doesn't have too many edges so there are 2 possible solutions: - Dijkstra with heap (run faster) - Ford Bellman with queue (you should optimize your code or you will get Time limit exceed) WIFI This problem has 2 approaches and both are expected to get full score. First approach: maximum bipartite matching. This approach are used by most of the competitors. Here you have 2 sets, access points (set A) and computers (set B ). First, you need to find a number K that K >= N and K can be divided by M. With each access point in set A, duplicate it (K/M)-1 times so there are K each access points of each. With set B, add K - N computers. Remember that these extra computers are far far away (the cost of them to all the access points are infinity). Now use maximum bipartite matching. Second approach: minimum cost flow with both lower & upper bound (I'm sorry that I can't have a good translation) Let's define: if N % M = 0 then cmin = cmax = N div M if N % M <> 0 then cmin = N div M, cmax = cmin + 1 First build a graph like this: Remember that if edge from U to V has cost of X then edge from V to U will have cost of -X. Flow with lower and upper bound: To handle this, if you have a graph G=, you should make the graph G'= (each edge in G' will have only one bound): - V' = V. - Add 2 extra nodes Source' and Target' to V' - E' = empty set. - with each edge from U to V with min and max bound in E, add 3 edges to E': an edge from U to V with (max - min) bound, an edge from Source' to V with min bound, and edge from U to Target' with min bound. - Add an edge from Target (the old target in G) to Source (the old source in G) with infinity bound About flow with both lower and upper bound, you should read "Giải thuật và lập trình" (DSAP text book) by Mr Lê Minh Hoàng (I'm sorry, it's only available in Vietnamese) Now, find the maximum low in G'. Let's call F[U,V] is the flow in G' from U to V. F[U,V] + lower bound(U, V) is the flow in G we need to find. Another problem is the cost of edge. Here, each time we find a path to enlarge our flow, you need to find the shortest one. I often solve this by Ford Bellman. You can read more about minimum cost flow here: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow1 http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow2 http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=minimumCostFlow3 Đã lưu IP
Đã khóa chức năng gửi bài.
#6047
(Thành viên) Đã biết code đệ quy Bài viết: 11    Trả lời: [VM08] 12th round (final) - Solution 12 năm, 4 tháng trước (+0) Hi, I'd like to consult my approach to WIFI, if anybody can see any flaw in it, I would appreciate to hear it. So here we go: I use min-cost max-flow, with the network like this source -> computers -> access points -> sink With edges (capacity,cost) source -> computers : (1,0) computers -> access points : (1,corresponding distance) access points -> sink : (ceil(N/M),0) With this, I think it is secured that when the flow will be maximal, the rule about the number of computers assigned to an access point will hold. And the min-cost of max-matching will give us the required answer. I only got half of the points, so there is probably some mistake in it. Thanks for helping me out! Đã lưu IP
Đã khóa chức năng gửi bài.
#6048
(Thành viên)
gerrob+1 Biết code binary-indexed tree Bài viết: 47    Trả lời: [VM08] 12th round (final) - Solution 12 năm, 4 tháng trước (+0) supo viết: QUOTE:Hi, I'd like to consult my approach to WIFI, if anybody can see any flaw in it, I would appreciate to hear it. So here we go: I use min-cost max-flow, with the network like this source -> computers -> access points -> sink With edges (capacity,cost) source -> computers : (1,0) computers -> access points : (1,corresponding distance) access points -> sink : (ceil(N/M),0) With this, I think it is secured that when the flow will be maximal, the rule about the number of computers assigned to an access point will hold. And the min-cost of max-matching will give us the required answer. I only got half of the points, so there is probably some mistake in it. Thanks for helping me out! Hi! The problem with your solution that your method is not guarantee the second rule: "The number of computers connected to the access points are different by no more than one." Let x[i] be the number of connected computers to the i-th access point, then you find the optimal solution for the modified problem where all x[i]<=ceil(N/M), but this isn't imply that they are differ at most one: Let N=4 computers at (0,1),(0,-1),(2,1),(3,0) and M=3 access point at (0,0),(1,0),(2,0) from one access point to the sink you set up ceil(N/M)=2 upper limit. And in the optimal solution (0,1) and (0,-1) are connected to (0,0) (distance=1 in both cases). And (2,1),(3,0) are connected to the (2,0) access point. But this is not a solution for the original problem, because the number of connected computers to the points are 2,0,2. ps. I had also an error on the contest, but after the contest: by matching I've got full points. Đã lưu IP
Đã khóa chức năng gửi bài.
#6049
(Thành viên) Đã biết code đệ quy Bài viết: 11    Trả lời: [VM08] 12th round (final) - Solution 12 năm, 4 tháng trước (+0) Yeah I was pretty silly, thanks for pointing it out. Đã 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