Monday, December 15, 2014

USACO US Open 2013 Bronze - 'Photo' / SRM 432 Div.1 Hard

1. USACO US Open 2013 Bronze - 'Photo'

아이디어는 일단, A_i 와 B_i 중 B_i가 가장 작은 것에 대해서 1~B_i-1까지는 무조건 같은 그룹이 될 수 있고 답은 1 증가한다. 그리고 해당 B_i값에 대해서 다른 쿼리가 있다고 하더라도 답에는 영향을 주지 않는다. 왜냐하면 B_i보다 작은 A_k들에 대해서는 서로가 무관하고 A_i와 B_i에 의해 최소한 답은 1이 증가해야하기 때문이다. 따라서 B_i순으로 정렬해두고서 A_k가 B_i 이상이면 B_k를 새로운 Right-most값으로 보고서 답을 Right-most값이 바뀔 때마다 증가시켜주면 된다.

My Source Code

2. SRM 432 Div.1 Hard

한 개의 도시에 집을 다 짓는 경우에 필요한 비용, 두 개의 연결된 도시에서 집을 짓는 경우에 필요한 비용을 생각한다. 거기다가 도로를 이을 때 필요한 비용까지 모든 도시 pair에 대해 고려해서 mst를 구해주면 답.

My Source Code

아래는 위의 문제에 대한 탑코더 공식 해설
Like many other "hard" problems - this one relies on the smaller subproblems.
In the beginning, let's determine how much is paid to builders for building houses in the same city. In the i-th city, the first house costsbefore[i]*houseCost[i], the second (before[i]+1)*houseCost[i], ..., the last - (after[i]-1)*houseCost[i]. The total cost is houseCost[i]*(before[i]+after[i]-1)*(after[i]-before[i])/2. Now we will think about how to reduce "between cities" and road building payments.
Consider the second building phase for only two cities i and j connected by a road. When building after[i]-before[i] new houses in the i-th city, each of old before[j] builders int the j-th city will get houseCost[i] units of money, so this expense equals to (after[i]-before[i])*before[j]*houseCost[i]. Similarly, after building new houses in the j-th city, old i-th city builders are paid (after[j]-before[j])*before[i]*houseCost[j] units of money in total. What's left is how much money will new builders get.
Consider any new house x in the i-th city and new house y in the j-th city. If house x is built before house y, the builder from x will gethouseCost[j] units of money for (x,y) houses pair. If house is built before x, the builder from y will get houseCost[i] units for the same(x,y) pair.
Note that for each such (x,y) pair we will have to pay some amount - either houseCost[i] or houseCost[j], depending on which house is built before. We don't have any other expenses. From it we can conclude, that it's always better to build first all the houses in the city, which has more houseCost. So, the minimal total payment for new builder is Min(houseCost[i], houseCost[j])*(after[i] - before[i])*(after[j] - before[j]).
Now consider the second building phase for any number of cities. It's not hard to see that the same happens here: for any pair of housesx and y from the neighboring cities - we have to pay money to builder either from x or y (except the case when both x and y are old houses), depending on which one is built earlier. So, it's always profitable to build each time a new possible house in the city with maximal houseCost.
It's time to combine both phases of building. When building a new road between cities i and j, we have to pay not only roadCost*(before[i]+before[j]) units of money for constructing it, also we must consider that it adds to our expenses (after[i]-before[i])*before[j]*houseCost[i]+(after[j]-before[j])*before[i]*houseCost[j]+Min(houseCost[i],houseCost[j])*(after[i] - before[i])*(after[j] - before[j]) units. So, their sum is the actual cost of that road. If this road already exists, we only add that last amount to our answer.
The remaining part is clear - we must construct Minimal Spanning Tree (MST) from all existing and possible new roads (In fact it's not exactly spanning tree, there are some more edges). For it, you can use either Kruskal's or Prim's algorithm.
... and be careful - int overflow!

No comments:

Post a Comment