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
Trả lời: [VM08] 12th round (final) - 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Ủ ĐỀ - Trả lời: [VM08] 12th round (final) - Solution
#6029
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] 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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#6037
khuebeo (Admin)
beo_chay_so+62
Admin
Bài viết: 294
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] 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=<V,E>, you should make the graph G'=<V',E'> (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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#6047
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] 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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#6048
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] 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 Đã lưu IP  
  Đã khóa chức năng gửi bài.
#6049
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] 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 Đã 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