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.

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

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!

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.

Yeah I was pretty silly, thanks for pointing it out.