UPD:Minor mistakes in grammar and expression fixed.

Disclaimer: This is not an official editorial.

If you have better or easy-to-understand solutions and thoughts, feel free to share your idea. Also welcome to point out mistakes so I can fix it.

160A - Twins

It's obvious that you should take the most valueable coins. so sort values in non-decreasing order, then take coins from the most valueable to the least, until you get strictly more than half of total value.

Time complexity depends on the sorting algorithm you use. O(n^2) is also acceptable, but if you use bogosort which runs in O(n!)...

160B - Unlucky Ticket

Deal with the situation that "first half is strictly less than second half" first. the other one can be solved accordingly.

You can use greedy here: sort digits in first and second half seperately. then if the i-th digit in first half is always less than i-th in second half for 1<=i<=n, answer is YES.

Time complexity is as same as problem A. Count sort may run faster in O(n+10), but it's not necessary .

160C - Find Pair

This is a tricky problem. When contest ends, I found there are 12 pages of accepted submissions while 60 pages of "WA on pretest 3" submissions.

First of all, sort a[].

A natural consideration is that the answer equals to (a[k/n] , a[k%n]). This algorithm will pass the sample and get "WA on pretest 3". In fact, it works only when all a[i] are distinct.

To get an AC, let's make elements distinct and weighted. For example, if there are ten 1s, we remain one of them and set its weight as 10. Now go over the whole array. for each element a[i], we can make weight[i]*n pairs using a[i] as first element. If k doesn't exceed that, go over the array again and find the second element, then print the answer. Otherwise, subtract it from K and go on.

Sort algorithm working in O(n log n) is acceptable. Java and Pascal users should beware of anti-quicksort tests.

160D - Edges in MST

Let's take a look at Kruskal Algorithm which solve MST in O(m log m) time. Sort the edges first in weight non-decreasing order, then process each edges. if the edge connects two different connected compoments, add this edge to MST then combine two compoments. We use disjoint-set union here to maintain connectivity.

The main point is that only those edges with same weight may replace each other in MST. First of all, sort edges as what Kruskal do. To get the answer, we construct MST in weight non-decreasing order, and process all edges with same weight together. Now on each step we are to face some edges with same weight x and a forest of connected compoments.

Note that for an edge, what points it connects does not matter, we only need to know what compoments it connects. Now build a new graph G', each point in G' is a connected compoment in the original forest,and edges are added to connect compoments that it connected before. Time complexity is O(|E|) here, with careful implementation.

Let's answer queries on these edges. First of all, if an edge in G' is a loop(connects the same compoment), this edge must not appear in any MSTs. If after deleting an edge V in G', G's connectivity is changed (A connected compoment in G' spilt into two. We call these edges bridge), V must be in any of MST. All edges left can appear in some MSTs, but not any.

What's left is to get all of V quickly. Maybe you hear about Tarjan before, he invented an algorithm based on DFS to get all bridges in an edge-undirected graph in O(|V|+|E|). Read this page on Wikipedia for detailed information: http://en.wikipedia.org/wiki/Bridge_(graph_theory)

Considering those compoments which don't have any edges connected don't need to be appear in G', we have |V|<=2|E|, so time complexity for Tarjan's DFS is O(|E|), where |E| is count of edges weighted x. Because each edge will be used exactly once in G', total time complexity except sorting is O(m).

160E - Buses and People

As what problem setter say, we sort the people and bus together with non-decreasing order of time first(if a bus and a person has same time, put the person first). Solving it by "For each person find which bus he should take" will become rather difficult, so let's take another idea: For each bus, find who it will take.

Abstract a person as a element in currently waiting list. Now, go over the sorted people and buses, we should apply two operations:

1. For a person, add it to the list.

2. For a bus, find all person in list satisfying sj ≤ li, ri ≤ fj ,remove them from the list and record the answer.(bi ≤ tj is hold, because we process these operation by time order.)

You will find it easy to solve this using any kind of balanced trees, like AVL or SBT. For each node i on balanced tree, we store r[i] as keyword and l[i] as value, then maintain the maxinum l[i] on every subtrees. Operating on a person is to add him to the tree. When dealing with a bus, we find the node i with maxinum l[i] in the range x<=f[j] (x is keyword), if l[i]>=s[j] is satisfied, delete the node i, set ans[i]=j, update the tree and search again until found l[i]<s[j].

If you are not familiar with balanced tree, discretize every r[i] and f[j], then use a segment tree to solve it.

Time complexity is O((n+m) log (n+m)) with balanced trees or segment tree.